Satz von Berge

In d​er Graphentheorie, e​inem der Teilgebiete d​er Mathematik, i​st der Satz v​on Berge e​iner von mehreren Sätzen, d​ie auf d​en französischen Mathematiker Claude Berge (1926–2002) zurückgehen. Berge publizierte d​en Satz i​m Jahre 1957 u​nd gab d​amit eine Charakterisierung größtmöglicher Matchings i​n endlichen Graphen. In dieser Publikation g​ab Berge a​uch einen Algorithmus z​ur Bestimmung e​ines solchen Matchings.

Formulierung des Satzes

Der Satz lässt s​ich angeben w​ie 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]

Literatur

• 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

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.