Disjunkte Wege im Netz verständlich erklärt

Zwischen zwei Orten eines Verbindungsnetzes können mehrere Wege führen. Wie viele davon sich unterwegs nirgends berühren (Fachleute sagen: disjunkte Wege), ist zugleich die Zahl der Standorte, die mindestens ausfallen müssen, um die beiden Orte zu trennen (solange sie nicht direkt verbunden sind). Diese Seite erklärt, warum das so ist und was es über die Robustheit eines Netzes sagt.

Zuletzt aktualisiert: 28. Oktober 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Zwei Werke und die Wege dazwischen

Stellen Sie sich zwei Werke vor, Werk Nord und Werk Süd. Dazwischen liegen Umschlagpunkte und Lager, die durch Straßen verbunden sind. Zusammen ergibt das ein Verbindungsnetz. Diese Seite nennt alle Punkte, auch die Werke, Standorte und die Straßen Leitungen. Zu dieser Seite gehört die Demo, ein Programm zum Ausprobieren solcher Netze im Browser.

Ein Lkw soll von Werk Nord nach Werk Süd. Dafür kann es mehrere Fahrtwege geben. Zwei Wege heißen disjunkt, also unabhängig voneinander, wenn sie außer Start und Ziel keinen Standort gemeinsam haben; gemeinsame Leitungen kommen weiter unten. Fällt ein Standort aus, trifft das höchstens einen dieser Wege. Wie viele disjunkte Wege gibt es höchstens?

Die Zahl der Wege ist die Zahl der nötigen Ausfälle

Dieselbe Zahl beantwortet noch eine zweite Frage: Wie viele Standorte müssen mindestens ausfallen, damit kein Lkw mehr von Werk Nord nach Werk Süd kommt? Die kleinste solche Gruppe von Standorten heißt Engstelle. Dass beides dieselbe Zahl ist, besagt der Satz von Menger, benannt nach dem Mathematiker, der ihn gefunden hat. Sind die Werke direkt durch eine Leitung verbunden, hilft der Ausfall eines Standorts nie; der Satz gilt für Werke ohne direkte Verbindung.

Eine Richtung ist leicht einzusehen. Jeder Zwischenstandort liegt auf höchstens einem der disjunkten Wege. Ein Ausfall blockiert also nur einen Weg, und für alle Wege braucht man mindestens so viele Ausfälle, wie es Wege gibt. Die andere Richtung ist die eigentliche Aussage: Ohne direkte Verbindung gibt es immer eine Gruppe, die genau so groß ist wie die Zahl der Wege.

Die Demo berechnet, wie viele Fahrten gleichzeitig durch das Netz passen, wenn jeder Standort nur eine verkraftet (ein Fluss), und zerlegt das Ergebnis in einzelne Wege. Danach markiert sie die Standorte der Engstelle.

Wo sich eine Engstelle verbergen kann

Die Demo hat ein von Hand gebautes Beispiel. Zwei Werke haben je vier Standorte, die untereinander alle verbunden sind. Zwischen den Werken gibt es nur zwei Leitungen, und beide beginnen am selben Standort A. Auf den ersten Blick sieht das nach zwei Verbindungen aus. Fällt aber der Standort A aus, sind beide Leitungen weg und die Werke getrennt.

Es kommt also darauf an, was ausfallen kann. Rechnet man mit Ausfällen einzelner Leitungen, gibt es in diesem Beispiel zwischen den Werken zwei unabhängige Wege. Rechnet man mit Ausfällen ganzer Standorte, gibt es von jedem Standort außer A zum anderen Werk nur einen. Die Demo lässt beides umschalten.

Eine naheliegende Abkürzung ist, an jedem Standort die Leitungen zu zählen; die geringste Leitungszahl pro Standort (Fachleute sagen Mindestgrad) ist eine Obergrenze dafür, wie robust das ganze Netz zusammenhängt, also für den schwächsten Fall über alle Paare von Standorten. Sie verrät die Engstelle aber nicht, wenn drei dichte Regionen nur durch wenige Leitungen verbunden sind: In der Demo hat dort bei zwei Leitungen zwischen den Regionen jeder Standort mehr Leitungen, als an der dünnen Stelle ausfallen müssten.

Was Sie daraus mitnehmen

Fragen Sie bei einem Verbindungsnetz nicht nur, wie viele Leitungen jeder Standort hat, sondern: Wie viele disjunkte Wege gibt es zwischen zwei wichtigen Orten, und welche kleinste Gruppe von Standorten oder Leitungen müsste ausfallen, um sie zu trennen? Ein Merkmal im eigenen Betrieb: Laufen mehrere scheinbar getrennte Ausweichrouten an derselben Stelle zusammen, etwa an einem Umschlagpunkt oder einer einzigen Zufahrt, dann ist das die Engstelle. Das gilt, solange nur zählt, ob eine Verbindung besteht; Fahrzeiten, Umwege und Kapazitäten, also wie viel eine Leitung bewältigt, bewertet die Zahl nicht.

Wie ernst ist das Modell zu nehmen?

Die Netze der Demo sind erzeugt, und alle Leitungen gelten als gleich. Die Demo fragt nach dem schlimmsten Fall, dem kleinsten Ausfall, der das Netz trennt, nicht nach zufälligen Ausfällen, und zeigt, wie man Engstellen findet, nicht wie ein echtes Betriebsnetz aussieht.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er fasst die formale Beschreibung der Demo zusammen; die vollständige Fassung steht im Expander „📐 Mathematische Formulierung“ der Demo.

• Netz: einfacher, ungerichteter Graph \(G = (V, E)\) mit \(n\) Standorten, synthetisch und mit festem Zufalls-Seed (der Zufall kommt nur aus random.Random(seed) mit random()). Netztypen: Zufallsnetz (Zufallsbaum plus Leitungen bis zum mittleren Grad), Gitter, Ring mit Abkürzungen, skalenfreies Netz (bevorzugte Anbindung), Verbundnetz (drei Regionen mit dem mittleren Grad im Inneren und genau der gewählten Zahl von Leitungen zwischen je zwei Regionen) und ein handgebautes Lehrbeispiel mit zwei Werken.
• Disjunkte Wege: \(\kappa(s,t)\) ist die größte Zahl innen knotendisjunkter Wege, \(\lambda(s,t)\) die größte Zahl kantendisjunkter Wege. \(\kappa(s,t)\) ist nur für nicht benachbarte \(s, t\) definiert, denn eine Leitung ist ein Weg ohne Zwischenstandort; für benachbarte Paare zeigt die Demo nur \(\lambda\). Der Knotenzusammenhang des Netzes \(\kappa(G)\) ist der kleinste Wert über alle nicht benachbarten Paare, beim vollständigen Netz \(n - 1\).
• Rechnung: ein Fluss mit Einheitskapazitäten (Edmonds–Karp, ein Weg je Durchlauf). Für knotendisjunkte Wege wird jeder Standort in einen Eingang und einen Ausgang gespalten (Pfeil mit Kapazität 1), jede Leitung wird zu zwei Pfeilen mit großer Kapazität; kantendisjunkt ist jede Leitung ein Paar gegenläufiger Pfeile mit Kapazität 1. Die Wege werden aus dem Fluss zerlegt, die trennende Menge aus dem Restnetz gelesen.
• Aufwand: gezählt in Flüssen (ein Fluss je Paar), Erweiterungen und Besuchen (abgearbeitete Knoten der Breitensuchen), nie in Sekunden.

Die Formeln

Der Satz von Menger in der Knotenversion gilt für nicht benachbarte \(s, t\): Die größte Zahl innen knotendisjunkter Wege ist gleich der kleinsten Zahl von Standorten außer \(s\) und \(t\), deren Ausfall \(s\) von \(t\) trennt.

\[\kappa(s,t) = \min \{\, |S| : S \subseteq V \setminus \{s,t\},\ S \text{ trennt } s \text{ von } t \,\}\]

In der Kantenversion gilt der Satz für alle \(s \neq t\), auch für benachbarte, mit Leitungsmengen \(F\):

\[\lambda(s,t) = \min \{\, |F| : F \subseteq E,\ F \text{ trennt } s \text{ von } t \,\}\]

Für das ganze Netz zählt der schwächste Fall. \(\kappa(G)\) ist das Minimum über alle nicht benachbarten Paare; \(\lambda(G)\) braucht nur \(n - 1\) Flüsse von einem festen Standort \(s_0\):

\[\kappa(G) = \min_{s,t \text{ nicht benachbart}} \kappa(s,t), \qquad \lambda(G) = \min_{t \neq s_0} \lambda(s_0, t)\]

Mit dem Mindestgrad \(\delta(G)\) gilt die Kette von Whitney, und \(\delta\) ist damit eine obere Schranke für beide Zusammenhänge:

\[\kappa(G) \le \lambda(G) \le \delta(G)\]

Algorithmus von Even für \(\kappa(G)\): Mit dem bisher besten Wert \(k\) (anfangs \(\delta\)) genügen die ersten \(k+1\) Standorte als Start, jeder gegen alle späteren, denn eine trennende Menge mit höchstens \(k\) Standorten enthält nicht alle \(k+1\). Das spart gegenüber allen Paaren einzeln viele Flüsse (Befunde).

Befunde

Alle Zahlen stammen aus den Experimenten der Demo (jede steht in deren Tests, tests/test_claims.py). Es sind Zähler über feste Netze (je Netztyp zehn bzw. zwölf, feste Zufalls-Seeds), nie ein einzelner Zufalls-Seed. Netztypen: Zufallsnetz mit mittlerem Grad 3, 5, 8, Gitter, Ring mit Abkürzungen, skalenfreies Netz, Verbundnetz (mittlerer Grad 8, zwei Leitungen zwischen je zwei Regionen). Ausnahmen sind genannt.

Frage	Befund
Stimmen alle Verfahren mit der Aufzählung aller Trennmengen überein?	Auf 84 Netzen mit 12 Standorten (sieben Netztypen, je zwölf Netze) stimmen 6.540 Prüfungen überein: Zusammenhang des Netzes nach beiden Verfahren, Zeugen und jedes der 3.060 nicht benachbarten Standortpaare mit seinen disjunkten Wegen und der trennenden Menge. Abweichungen: 0.
Sagt der Mindestgrad den Zusammenhang?	Bei etwa 30 Standorten und je Netztyp zehn Netzen gilt κ = λ = Mindestgrad in 59 von 70 Netzen (84 %); ohne das Verbundnetz in 59 von 60, die einzige Ausnahme ist ein Ring mit Abkürzungen (κ < λ). Im Verbundnetz in 0 von 10: κ < λ in 9, λ < Mindestgrad in 10; Mindestgrad im Mittel 6,2, λ 4, κ 3. Die Kette κ ≤ λ ≤ Mindestgrad ist in 0 Netzen verletzt.
Wie viele Paare hängen an einer Engstelle?	Anteil der nicht benachbarten Paare mit κ(s, t) kleiner als der kleinere Grad: 0 % (Gitter, Zufallsnetz Grad 8), 4 % (Zufallsnetz Grad 5), 15 % (Zufallsnetz Grad 3), 8 % (skalenfreies Netz), 28 % (Ring mit Abkürzungen, in 10 von 10 Netzen mindestens ein Paar), 96 % (Verbundnetz); gezählt über 23.870 Paare.
Wie viele Flüsse spart der Algorithmus von Even?	Im Mittel über die sieben Netztypen das 3,1-Fache (20 Standorte), 6,6-Fache (40) und 13,8-Fache (80) der Flüsse gegenüber allen nicht benachbarten Paaren (auf diesen dünnen Modellnetzen mit kleinem Mindestgrad; Quotient der Summen, bei 80 Standorten nur 4 Netze je Typ); bei 80 Standorten je nach Netztyp das 9,5- bis 20-Fache (Zufallsnetz Grad 5: 2.960 Flüsse gegen 148). Bei 20, 40 und 80 Standorten braucht Even in allen Fällen weniger Flüsse.
Wie verschiebt sich die Engstelle mit der Verbundstärke?	Bei 45 Standorten, mittlerem Grad 8 und zehn Netzen je Zeile: Bei 1 / 2 / 3 / 5 Leitungen zwischen je zwei Regionen liegt κ im Mittel bei 1,8 / 2,8 / 3,9 / 4,8, λ bei 2 / 4 / 4,5 / 4,8 und der Mindestgrad bei 4,4 / 4,4 / 4,5 / 4,8. κ < λ gilt in 2 / 10 / 4 / 0 von 10 Netzen; bei 5 Leitungen gilt κ = λ = Mindestgrad in allen 10 gemessenen Netzen (45 Standorte) und auf 100 weiteren Zufalls-Seeds (200000 bis 200099) in 98; die Zahl gilt für diesen Bereich.
Das Lehrbeispiel von Hand?	Zwei Werke, 8 Standorte, 14 Leitungen: Mindestgrad 3, λ 2, κ 1. Alle 14 nicht benachbarten Paare haben eine Engstelle; alle Paare einzeln brauchen 14 Flüsse, Even 6.
Ist die Rechnung korrekt?	κ nach Even und nach allen Paaren gleich networkx.node_connectivity, λ gleich networkx.edge_connectivity auf 48 festen Netzen; jedes nicht benachbarte Paar gleich local_node_connectivity, minimum_node_cut und node_disjoint_paths (18 Netze); bei kleinen Netzen gleich der Aufzählung aller Trennmengen (40 Netze); invariant gegen Umnummerieren; eine zusätzliche Leitung senkt den Zusammenhang nie.

Jedes Ergebnis prüft die Demo vor der Anzeige: Even gleich alle Paare, die Kette κ ≤ λ ≤ Mindestgrad, jede trennende Menge trennt und hat die richtige Größe, jede Weg-Menge ist disjunkt und hat die richtige Zahl.

Grenzen

• Dünne Zufallsnetze: Ein Zufallsbaum plus Zusatzleitungen hat einen kleinen Mindestgrad (bei mittlerem Grad 5 ist er 1 oder 2, in je fünf von zehn Netzen), und der begrenzt dann alles. Dass der Mindestgrad fast alles sagt, gilt für diese Netze; auf dichten, regelmäßigen Netzen mit hohem Mindestgrad wäre die Engstelle öfter die Ausnahme (nicht gemessen).
• Verbundnetz gebaut, nicht gefunden: Drei dichte Regionen mit wenigen Leitungen dazwischen sind absichtlich so gewählt, dass die Engstelle sichtbar wird. Wie oft reale Netze so gebaut sind, zeigt die Demo nicht.
• Alle Leitungen gleich: Mit Kapazitäten und Kosten ist Max-Flow gleich Min-Cut die allgemeinere Rechnung.
• Gezählt, nicht verstärkt: Die Engstelle wird benannt, nicht behoben.
• Gezielter Ausfall, kein Zufall: Die Demo fragt nach der kleinsten Trennmenge, nicht nach der Wahrscheinlichkeit zufälliger Ausfälle.
• Ungerichtetes Netz: In gerichteten Netzen gilt der Satz von Menger ebenfalls, die Kette κ ≤ λ ≤ Mindestgrad aber nur mit Ein- und Ausgrad.
• Größe: bis 80 Standorte (das Gitter bis 81); der Aufwand ist in Flüssen und Besuchen gezählt, nicht in Sekunden.

Quellen

• Menger, K. (1927): Zur allgemeinen Kurventheorie. Fundamenta Mathematicae 10, 96–115.
• Whitney, H. (1932): Congruent graphs and the connectivity of graphs. American Journal of Mathematics 54, 150–168.
• Even, S. (1975): An algorithm for determining whether the connectivity of a graph is at least k. SIAM Journal on Computing 4, 393–396.
• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/menger-demo.

Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen; die Literaturhinweise stammen aus dem Expander „📐 Mathematische Formulierung“ und der README der Demo. Der Satz von Menger und die Kette von Whitney sind Standardwissen der Graphentheorie; die Erklärung der leichten Richtung des Satzes im ersten Teil ist keine Aussage der README.