Minimaler Schnitt Rechner

Pseudocode

Der minimale Schnitt wird nicht direkt berechnet. Man berechnet einen maximalen Fluss und liest den Schnitt anschließend in einem einzigen Durchlauf aus dem Residualgraphen ab.

MinSchnitt(graph, s, t):
    beliebigen Max-Fluss-Algorithmus bis zur Sättigung laufen lassen

    // S = alles, was von s aus im RESIDUALGRAPHEN
    // noch erreichbar ist
    S = BFS/DFS von s, nur über Kanten mit
        Restkapazität > 0
    T = alle übrigen Knoten

    schnitt = { (u,v) aus den Originalkanten :
                u in S und v in T }
    gib schnitt und die Summe der Originalkapazitäten zurück

Zwei Tatsachen lassen das funktionieren. Jede Kante, die von S nach T führt, muss gesättigt sein, denn sonst wäre ihre Restkapazität positiv und ihr Endpunkt wäre erreichbar gewesen und läge damit in S. Und jede Kante von T zurück nach S führt keinerlei Fluss. Der Fluss über den Schnitt entspricht damit exakt der Schnittkapazität, und da kein Fluss irgendeinen Schnitt übersteigen kann, müssen beide optimal sein.

Durchgerechnetes Beispiel, Schritt für Schritt

Bestimme den minimalen Schnitt auf demselben Netzwerk wie beim Maximalfluss, indem du den Residualgraphen nach der Sättigung ausliest.

Beispielgraph: Gerichtete Kapazitäten S nach A (10), S nach B (10), A nach B (2), A nach T (4), B nach T (9).

1. Den Maximalfluss berechnen. Augmentieren entlang S nach A nach T schiebt 4, entlang S nach B nach T schiebt 9. Der Gesamtfluss beträgt 13 und es bleibt kein augmentierender Pfad übrig.
2. Den Residualgraphen betrachten. S-A hat 10 - 4 = 6 Restkapazität. S-B hat 10 - 9 = 1. A-B ist unberührt, es bleiben also alle 2. A-T und B-T sind beide voll gesättigt mit 0 Rest.
3. S per Durchlauf bestimmen. Beginne bei S. Die Kante S-A hat Restkapazität, also gehört A zu S. Von A aus hat die Kante A-B Restkapazität, also gehört B zu S. Von B aus ist die einzige ausgehende Kante B-T gesättigt. Weiter ist nichts erreichbar, S ist also die Menge {S, A, B}.
4. Den Schnitt ablesen. T ist die verbleibende Knotenmenge, nämlich nur {T}. Die Originalkanten von S nach T sind A-T mit Kapazität 4 und B-T mit Kapazität 9.
5. Überprüfen. Die Schnittkapazität beträgt 4 + 9 = 13, also genau so viel wie der Maximalfluss. Entfernt man diese beiden Kanten, ist T von S aus unerreichbar, womit es sich um einen echten Schnitt handelt.

Der minimale Schnitt ist das Kantenpaar A-T und B-T mit Gesamtkapazität 13 und stimmt damit mit dem Maximalfluss von 13 überein. Beachte, dass S-A und S-B zusammen eine Kapazität von 20 haben und ebenfalls einen Schnitt bilden, allerdings einen teureren. Der Engpass liegt auf der Senkenseite, und der Residualdurchlauf findet ihn, ohne mögliche Schnitte durchsuchen zu müssen.

Komplexität und woher sie kommt

Zeit: wie der verwendete Max-Fluss-Algorithmus · Speicher: O(V + E)

Das Auslesen des Schnitts selbst ist ein einzelner Graphdurchlauf mit O(V + E) und damit vernachlässigbar. Der gesamte Aufwand steckt in der vorausgehenden Maximalflussberechnung: O(V mal E hoch 2) mit Edmonds-Karp oder O(V hoch 2 mal E) mit Dinic. Das gehört klar gesagt, denn es erklärt, warum der minimale Schnitt nicht als eigenes Problem behandelt wird. Es ist kein Weg bekannt, den minimalen s-t-Schnitt asymptotisch schneller zu finden als über die Berechnung des Maximalflusses, denn nach dem Max-Flow-Min-Cut-Satz sind beide dieselbe Rechnung von entgegengesetzten Seiten betrachtet.

Wann Minimaler Schnitt passt und wann nicht

Das Wort Schnitt umfasst mehrere wirklich verschiedene Probleme. Das falsche zu wählen ist hier der häufigste Fehler.

Häufige Fehler

• Den Originalgraphen statt des Residualgraphen durchlaufen. Der Schnitt ist dadurch definiert, was über verbliebene Kapazität erreichbar ist, nicht über die Originalkanten. Führt man den Durchlauf auf dem Originalgraphen aus, erreicht man typischerweise die Senke und erhält gar keinen Schnitt. Das ist der häufigste Implementierungsfehler.
• Den minimalen s-t-Schnitt mit dem globalen minimalen Schnitt verwechseln. Der s-t-Schnitt trennt zwei gewählte Knoten. Der globale minimale Schnitt zerlegt den Graphen in zwei beliebige nichtleere Teile und erfordert Stoer-Wagner oder Karger. Das falsche Problem zu lösen liefert eine gültige Antwort auf eine Frage, die niemand gestellt hat.
• Annehmen, der minimale Schnitt sei eindeutig. Seine Kapazität ist eindeutig, die Kantenmenge häufig nicht. Mehrere verschiedene Schnitte können dieselbe minimale Kapazität haben, und welchen du erhältst, hängt vom gefundenen Fluss ab. Tests sollten die Kapazität prüfen, nicht eine bestimmte Kantenliste.
• Kanten von T zurück nach S mitzählen. Nur Kanten von der S-Seite zur T-Seite zählen zur Schnittkapazität. Rückwärtskanten führen keinen Fluss über den Schnitt und tragen nichts bei. Sie mitzuzählen treibt die Antwort über den Maximalfluss hinaus und bricht den Satz.
• Vergessen, dass Kapazitäten nichtnegativ sein müssen. Die Entsprechung von Maximalfluss und minimalem Schnitt setzt nichtnegative Kapazitäten voraus. Eine negative Kapazität ist kein sinnvoller Durchsatzbegriff, und die Residualargumentation bricht ohne sie zusammen.

Häufig gestellte Fragen

Was ist ein minimaler Schnitt in einem Graphen?

Ein Schnitt ist eine Aufteilung der Knoten in zwei Mengen, eine mit der Quelle und eine mit der Senke, und seine Kapazität ist die Gesamtkapazität der Kanten, die von der Quellseite zur Senkenseite führen. Der minimale Schnitt ist die günstigste solche Aufteilung und benennt damit den Engpass: die billigste Kantenmenge, deren Entfernen Quelle und Senke trennt.

Wie findet man den minimalen Schnitt?

Berechne den maximalen Fluss und führe dann von der Quelle aus eine BFS oder DFS im Residualgraphen durch, wobei nur Kanten mit verbliebener Kapazität benutzt werden. Die erreichten Knoten bilden die eine Seite des Schnitts, alle übrigen die andere, und die Originalkanten dazwischen sind der minimale Schnitt.

Was besagt der Max-Flow-Min-Cut-Satz?

Er besagt, dass der maximale Fluss von der Quelle zur Senke stets der Kapazität des minimalen trennenden Schnitts entspricht. Kein Fluss kann einen Schnitt übersteigen, da alles ihn queren muss, und wenn kein augmentierender Pfad mehr bleibt, definiert die im Residualgraphen erreichbare Menge einen Schnitt, dessen Kapazität der Fluss genau erreicht, sodass beide Werte übereinstimmen.

Was ist der Unterschied zwischen minimalem Schnitt und globalem minimalem Schnitt?

Ein minimaler s-t-Schnitt trennt zwei festgelegte Knoten und wird über den Maximalfluss gefunden. Ein globaler minimaler Schnitt zerlegt den Graphen in zwei beliebige nichtleere Teile, ohne dass Knoten vorab bestimmt werden, und wird mit Stoer-Wagner oder Karger gefunden. Ein globaler Schnitt kann deutlich billiger sein als jeder bestimmte s-t-Schnitt.

Wofür wird der minimale Schnitt verwendet?

Zum Erkennen von Netzwerkschwachstellen und einzelnen Ausfallpunkten, zur Bildsegmentierung, bei der Pixel Knoten sind und der Schnitt Vordergrund von Hintergrund trennt, für Clustering und Community-Erkennung, für Projektauswahlprobleme und für die Zuverlässigkeitsanalyse von Kommunikations- und Verkehrsinfrastruktur.