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

Der Satz lässt sich angeben wie folgt:^[1][2][3][4]

Ein Matching ${\displaystyle M}$ in einem endlichen Graphen ${\displaystyle G}$ ist von maximaler Mächtigkeit (und besteht damit aus genau ${\displaystyle \nu (G)}$ Kanten) dann und nur dann, wenn es in ${\displaystyle G}$ keinen ${\displaystyle M}$-erweiternden Weg gibt.

Erklärungen

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

Anmerkungen

• In 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 regulären Graphs des dänischen Mathematikers Julius Petersen aus dem Jahre 1891 auf.^[6]
• 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.^[4]

Weblinks

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

Literatur

• Lutz Volkmann: Fundamente der Graphentheorie. Springer Verlag, Wien / New York 1996, ISBN 3-211-82774-9 (MR1392955). 
• 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). 
• 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. 
• Julius Petersen: Die Theorie der regulären Graphs. In: Acta Mathematica. Band 15, 1891, S. 193–220 (PDF). 
• 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). 
• Claude Berge: Two theorems in graph theory. In: Proceedings of the National Academy of Sciences. Band 43, 1957, S. 842–844 (MR0094811). 

Einzelnachweise

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. ↑ ^{a b} 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. ↑ ^{a b} Jonathan L. Gross, Jay Yellen (Hrsg.): Handbook of Graph Theory. 2004, S. 1105.