Der Satz von Menger ist eines der klassischen Ergebnisse der Graphentheorie. Er wurde von 1927 von Karl Menger bewiesen und stellt einen Zusammenhang zwischen der Anzahl disjunkter Wege und der Größe von Trennern in einem Graphen her.[1] Insbesondere die globale Variante des Satzes trifft auch Aussagen über den K-Zusammenhang und den Kantenzusammenhang eines Graphen. Der Satz ist eine Verallgemeinerung des Satzes von König (1916), wonach in bipartiten Graphen die Paarungszahl der Knotenüberdeckungszahl entspricht.
Er lässt sich wie der Satz von König auch auf unendliche Graphen übertragen (Ron Aharoni, Eli Berger 2009).[2]
Ist
ein ungerichteter Graph und sind
und
Teilmengen von
, so ist die kleinste Mächtigkeit einer
von
trennenden Knotenmenge gleich der größten Mächtigkeit einer Menge disjunkter
-
-Wege
Nimmt man die Menge
als einelementig an, so folgt sofort der sogenannte Fächersatz: Ist
eine Teilmenge von
und
ein Element von
, so ist die kleinste Mächtigkeit einer
von
trennenden Teilmenge
gleich der größten Mächtigkeit eines
-
-Fächers.
Mit der Definition des Kantenzusammenhangs und des k-Zusammenhangs folgt dann die globale Version:
ist genau dann
-zusammenhängend, wenn
zwischen je zwei Knoten
disjunkte Wege enthält.
ist genau dann
-fach kantenzusammenhängend, wenn
zwischen je zwei Knoten
kantendisjunkte Wege enthält.
Gelegentlich findet man den Satz in der Literatur auch in einer der folgenden Formulierungen:
Sind
und
zwei verschiedene Knoten von
, so gilt:
- Sind
und
nicht benachbart, so ist die kleinste Mächtigkeit einer
von
trennenden Teilmenge von
gleich der größten Mächtigkeit einer Menge disjunkter
-
-Wege in
.
- Die kleinste Mächtigkeit einer
von
trennenden Kantenmenge
ist gleich der größten Mächtigkeit einer Menge kantendisjunkter
-
-Wege in
.
Der Satz von Menger wird häufig als alternative Definition der Begriffe Kantenzusammenhang sowie k-Zusammenhang genutzt. Des Weiteren leitet sich das Max-Flow-Min-Cut-Theorem aus dem Satz ab, welches eine zentrale Rolle in der Theorie von Flüsse und Schnitte in Netzwerken spielt.
- ↑ Karl Menger: Zur allgemeinen Kurventheorie. In: Fund. Math. Band 10, 1927, S. 96–115 (edu.pl [PDF]).
- ↑ R. Aharoni, E. Berger, Menger’s theorem for infinite graphs, Inventiones Mathematicae, Band 176, 2009, S. 1–62