Satz von Menger

mathematischer Satz

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]

Lokale Version

Bearbeiten

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

Fächersatz

Bearbeiten

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.

Globale Version

Bearbeiten

Mit der Definition des Kantenzusammenhangs und des k-Zusammenhangs folgt dann die globale Version:

  1.   ist genau dann  -zusammenhängend, wenn   zwischen je zwei Knoten   disjunkte Wege enthält.
  2.   ist genau dann  -fach kantenzusammenhängend, wenn   zwischen je zwei Knoten   kantendisjunkte Wege enthält.

Alternative Formulierung

Bearbeiten

Gelegentlich findet man den Satz in der Literatur auch in einer der folgenden Formulierungen: Sind   und   zwei verschiedene Knoten von  , so gilt:

  1. 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  .
  2. Die kleinste Mächtigkeit einer   von   trennenden Kantenmenge   ist gleich der größten Mächtigkeit einer Menge kantendisjunkter  - -Wege in  .

Verwendung

Bearbeiten

Der Satz von Menger wird häufig als alternative Definition der Begriffe Kantenzusammenhang sowie k-Zusammenhang genutzt. Des Weiteren gibt es eine Verallgemeinerung des Satzes, das Max-Flow-Min-Cut-Theorem, das eine zentrale Rolle in der Theorie der Flüsse und Schnitte in Netzwerken spielt.

Siehe auch

Bearbeiten

Literatur

Bearbeiten

Einzelnachweise

Bearbeiten
  1. Karl Menger: Zur allgemeinen Kurventheorie. In: Fund. Math. Band 10, 1927, S. 96–115 (edu.pl [PDF]).
  2. R. Aharoni, E. Berger, Menger’s theorem for infinite graphs, Inventiones Mathematicae, Band 176, 2009, S. 1–62