www.wikidata.de-de.nina.az

Satz von Berge In der Graphentheorie einem der Teilgebiete der Mathematik ist der einer von mehreren Sätzen die auf den

Satz von Berge

In der Graphentheorie, einem der Teilgebiete der Mathematik, ist der Satz von Berge einer von mehreren Sätzen, die auf den französischen Mathematiker Claude Berge (1926–2002) zurückgehen. Berge publizierte den Satz im Jahre 1957 und gab damit eine Charakterisierung größtmöglicher Matchings in endlichen Graphen. In dieser Publikation gab Berge auch einen Algorithmus zur Bestimmung eines solchen Matchings.

Formulierung des Satzes Bearbeiten

Der Satz lässt sich angeben wie folgt:

Erklärungen Bearbeiten

  • In einem endlichen Graphen ist ein Matching von maximaler Mächtigkeit genau dann, wenn in kein anderes Matching existiert mit . Die Mächtigkeit eines solchen größtmöglichen Matchings nennt man die Matchingzahl von und bezeichnet sie mit .
  • Ist ein Weg in gegeben, so wird als -alternierend bezeichnet, falls die in vorkommenden Kanten abwechselnd zu und zu gehören.
  • Inzidieren die durch einen -alternierenden Weg verbundenen Endknoten mit keiner der in vorkommenden Kanten, so wird als -erweiternd (oder als -zunehmend) bezeichnet.

Anmerkungen Bearbeiten

  • In der englischsprachigen Graphentheorieliteratur spricht man von einem augmenting path. Daher ist der Satz von Berge hier auch als augmenting path theorem bekannt.
  • Der Satz tritt auch schon in der Pionierarbeit Die Theorie der regulären Graphs des dänischen Mathematikers Julius Petersen aus dem Jahre 1891 auf.
  • Oft wird (so etwa im Bronstein) ein Matching von maximaler Mächtigkeit auch kurz ein maximales Matching genannt, obwohl diese Benennung nicht dem sonst üblichen – von der Ordnungstheorie herrührenden – Maximalitätsbegriff entspricht.

Weblinks Bearbeiten

Wikiversity: Ein Beweis des Satzes im Rahmen eines Kurses zur diskreten Mathematik – Kursmaterialien

Literatur Bearbeiten

  • Claude Berge: Two theorems in graph theory. In: Proceedings of the National Academy of Sciences. Band 43, 1957, S. 842–844 (MR0094811).
  • Claude Berge: Graphs and Hypergraphs. Translated [from the French] by Edward Minieka (= North-Holland Mathematical Library. Band 6). North-Holland Publishing Company, Amsterdam, London 1973 (MR0357172).
  • I. N. Bronstein, K. A. Semendjajew, G. Musiol, H. Mühlig (Hrsg.): Taschenbuch der Mathematik. 10., überarbeitete Auflage. Europa-Lehrmittel, Haan-Gruiten 2016, ISBN 978-3-8085-5790-7.
  • John Clark, Derek Allan Holton: Graphentheorie. Grundlagen und Anwendungen. Spektrum Akademischer Verlag, Heidelberg, Berlin, Oxford 1994, ISBN 3-86025-331-X.
  • Jonathan L. Gross, Jay Yellen (Hrsg.): Handbook of Graph Theory (= Discrete Mathematics and its Applications). CRC Press, Boca Raton u. a. 2004, ISBN 1-58488-090-2.
  • Dieter Jungnickel: Graphs, Networks and Algorithms. With 209 Figures and 9 Tables (= Algorithms and Computation in Mathematics. Band 5). 3. Auflage. Springer Verlag, Berlin / Heidelberg / New York 2008, ISBN 978-3-540-72779-8 (MR2363884).
  • Julius Petersen: Die Theorie der regulären Graphs. In: Acta Mathematica. Band 15, 1891, S. 193–220 (PDF).
  • Lutz Volkmann: Fundamente der Graphentheorie. Springer Verlag, Wien / New York 1996, ISBN 3-211-82774-9 (MR1392955).

Einzelnachweise Bearbeiten

  1. Claude Berge: Graphs and Hypergraphs. 1973, S. 124.
  2. John Clark, Derek Allan Holton: Graphentheorie. 1994, S. 137.
  3. Lutz Volkmann: Fundamente der Graphentheorie. 1996, S. 117.
  4. ↑ I. N. Bronstein, K. A. Semendjajev u. a.: Taschenbuch der Mathematik. 2016, S. 420.
  5. Dieter Jungnickel: Graphs, Networks and Algorithms. 2008, S. 390 ff.
  6. ↑ Jonathan L. Gross, Jay Yellen (Hrsg.): Handbook of Graph Theory. 2004, S. 1105.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
In der Graphentheorie einem der Teilgebiete der Mathematik ist der Satz von Berge einer von mehreren Satzen die auf den franzosischen Mathematiker Claude Berge 1926 2002 zuruckgehen Berge publizierte den Satz im Jahre 1957 und gab damit eine Charakterisierung grosstmoglicher Matchings in endlichen Graphen In dieser Publikation gab Berge auch einen Algorithmus zur Bestimmung eines solchen Matchings Inhaltsverzeichnis 1 Formulierung des Satzes 1 1 Erklarungen 2 Anmerkungen 3 Weblinks 4 Literatur 5 EinzelnachweiseFormulierung des Satzes BearbeitenDer Satz lasst sich angeben wie folgt 1 2 3 4 Ein Matching M displaystyle M nbsp in einem endlichen Graphen G displaystyle G nbsp ist von maximaler Machtigkeit und besteht damit aus genau n G displaystyle nu G nbsp Kanten dann und nur dann wenn es in G displaystyle G nbsp keinen M displaystyle M nbsp erweiternden Weg gibt Erklarungen Bearbeiten In einem endlichen Graphen G displaystyle G nbsp ist ein Matching M E G displaystyle M subseteq E G nbsp von maximaler Machtigkeit genau dann wenn in G displaystyle G nbsp kein anderes Matching M displaystyle M nbsp existiert mit M gt M displaystyle M gt M nbsp Die Machtigkeit eines solchen grosstmoglichen Matchings nennt man die Matchingzahl von G displaystyle G nbsp und bezeichnet sie mit n G displaystyle nu G nbsp Ist ein Weg in G displaystyle G nbsp gegeben so wird W displaystyle W nbsp als M displaystyle M nbsp alternierend bezeichnet falls die in W displaystyle W nbsp vorkommenden Kanten abwechselnd zu M displaystyle M nbsp und zu E G M displaystyle E G setminus M nbsp gehoren Inzidieren die durch einen M displaystyle M nbsp alternierenden Weg W displaystyle W nbsp verbundenen Endknoten mit keiner der in M displaystyle M nbsp vorkommenden Kanten so wird W displaystyle W nbsp als M displaystyle M nbsp erweiternd oder als M displaystyle M nbsp zunehmend bezeichnet Anmerkungen BearbeitenIn der englischsprachigen Graphentheorieliteratur spricht man von einem augmenting path Daher ist der Satz von Berge hier auch als augmenting path theorem bekannt 5 6 Der Satz tritt auch schon in der Pionierarbeit Die Theorie der regularen Graphs des danischen Mathematikers Julius Petersen aus dem Jahre 1891 auf 6 Oft wird so etwa im Bronstein ein Matching von maximaler Machtigkeit auch kurz ein maximales Matching genannt obwohl diese Benennung nicht dem sonst ublichen von der Ordnungstheorie herruhrenden Maximalitatsbegriff entspricht 4 Weblinks Bearbeiten nbsp Wikiversity Ein Beweis des Satzes im Rahmen eines Kurses zur diskreten Mathematik KursmaterialienLiteratur BearbeitenClaude Berge Two theorems in graph theory In Proceedings of the National Academy of Sciences Band 43 1957 S 842 844 MR0094811 Claude Berge Graphs and Hypergraphs Translated from the French by Edward Minieka North Holland Mathematical Library Band 6 North Holland Publishing Company Amsterdam London 1973 MR0357172 I N Bronstein K A Semendjajew G Musiol H Muhlig Hrsg Taschenbuch der Mathematik 10 uberarbeitete Auflage Europa Lehrmittel Haan Gruiten 2016 ISBN 978 3 8085 5790 7 John Clark Derek Allan Holton Graphentheorie Grundlagen und Anwendungen Spektrum Akademischer Verlag Heidelberg Berlin Oxford 1994 ISBN 3 86025 331 X Jonathan L Gross Jay Yellen Hrsg Handbook of Graph Theory Discrete Mathematics and its Applications CRC Press Boca Raton u a 2004 ISBN 1 58488 090 2 Dieter Jungnickel Graphs Networks and Algorithms With 209 Figures and 9 Tables Algorithms and Computation in Mathematics Band 5 3 Auflage Springer Verlag Berlin Heidelberg New York 2008 ISBN 978 3 540 72779 8 MR2363884 Julius Petersen Die Theorie der regularen Graphs In Acta Mathematica Band 15 1891 S 193 220 PDF Lutz Volkmann Fundamente der Graphentheorie Springer Verlag Wien New York 1996 ISBN 3 211 82774 9 MR1392955 Einzelnachweise Bearbeiten Claude Berge Graphs and Hypergraphs 1973 S 124 John Clark Derek Allan Holton Graphentheorie 1994 S 137 Lutz Volkmann Fundamente der Graphentheorie 1996 S 117 a b I N Bronstein K A Semendjajev u a Taschenbuch der Mathematik 2016 S 420 Dieter Jungnickel Graphs Networks and Algorithms 2008 S 390 ff a b Jonathan L Gross Jay Yellen Hrsg Handbook of Graph Theory 2004 S 1105 Abgerufen von https de wikipedia org w index php title Satz von Berge amp oldid 201938245