Satz von Menger

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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.

Lokale Version[Bearbeiten | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext bearbeiten]

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.

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Literatur[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Karl Menger: Zur allgemeinen Kurventheorie. In: Fund. Math.. 10, 1927, S. 96–115.