webentwicklung-frage-antwort-db.com.de

Wie kann ich mithilfe eines Maximalflussalgorithmus den Minimalschnitt in einem Diagramm ermitteln?

Ich muss den Mindestschnitt in einer Grafik finden. Ich habe über Flussnetzwerke gelesen, aber alles, was ich finden kann, sind Maximalflussalgorithmen wie Ford-Fulkerson, Push-Relabel usw. Angesichts des Maximaldurchfluss-Minimalsatz-Theorems ist es möglich, einen dieser Algorithmen zu verwenden, um zu finden der minimale Schnitt in einem Graphen mit einem Maximalflussalgorithmus? Wie?

Die beste Information, die ich bisher gefunden habe, ist, dass wenn ich "gesättigte" Kanten finde, d. H. Kanten, bei denen der Fluss gleich der Kapazität ist, diese Kanten dem minimalen Schnitt entsprechen. Ist das wahr? Es klingt nicht 100% richtig für mich. Es ist wahr, dass alle Kanten auf dem Minimalschnitt gesättigt sind, aber ich glaube, dass es auch gesättigte Kanten geben kann, die außerhalb des Minimalschnitt- "Pfades" liegen.

54
cesarbs

Führen Sie vom Quellscheitelpunkt aus eine Tiefensuche entlang der Kanten im verbleibenden Netzwerk durch (d. H. Nicht gesättigte Kanten und hintere Kanten von Kanten, die einen Fluss aufweisen), und markieren Sie alle Scheitelpunkte, die auf diese Weise erreicht werden können. Der Schnitt besteht aus allen Kanten, die von einem markierten zu einem nicht markierten Scheitelpunkt führen. Offensichtlich sind diese Kanten gesättigt und wurden daher nicht überquert. Wie Sie bereits bemerkt haben, gibt es möglicherweise andere gesättigte Kanten, die nicht zum Mindestschnitt gehören.

45
Falk Hüffner

Ich möchte nicht wählerisch sein, aber die vorgeschlagene Lösung ist nicht ganz richtig.

Richtige Lösung : Was Sie eigentlich tun sollten, ist bfs/dfs auf dem Residual-Network Gf ( lies es auf Wikipedia nach ) und markiere die Eckpunkte. Und dann können Sie diejenigen mit markiertem Von-Scheitelpunkt und nicht markiertem Bis-Scheitelpunkt auswählen.

Warum 'Ungesättigten Kanten folgen' nicht ausreicht : Beachten Sie, dass der Flussalgorithmus die Kanten wie in der Abbildung dargestellt sättigt. Ich habe die Eckpunkte, die ich besuche, mit dem Ansatz "nur ungesättigten Kanten folgen" mit Grün markiert. Offensichtlich ist der einzig richtige Min-Cut der Edge von E-F, während die vorgeschlagene Lösung auch A-D (und vielleicht sogar D-E) zurückgeben würde.

enter image description here Beachten Sie, dass der Scheitelpunkt D vom dfs/bfs besucht würde, wenn wir stattdessen das verbleibende Netzwerk betrachten würden, da es eine Kante von E nach D geben würde, wodurch die Kante EF die einzige mit einem markierten Von-Scheitelpunkt wird und ein nicht markierter Scheitelpunkt.

26
dingalapadum

Hinweis: Falks Algorithmus kann verwendet werden, um sowohl einen minimalen Schnitt mit minimalen als auch mit maximalen Scheitelpunkten zu finden. Für letztere sollte der Algorythmus umgekehrt werden, d.h. Suche von der Senke Vertex anstelle der Quelle. Siehe eine verwandte Frage: Netzwerkfluss: Hinzufügen eines neuen Edges

1
Gyula

Zum besseren Verständnis definieren wir einen Schnitt als zwei Mengen S und T, die s bzw. t enthalten.

Fügen Sie nun alle Eckpunkte in S hinzu, die von s im Restnetz erreichbar sind, und setzen Sie die restlichen Kanten in T. Dies wird ein Schnitt sein.

Zweitens kann ein Schnitt gebildet werden, indem alle Scheitelpunkte in T, die von t aus erreichbar sind, in das verbleibende Netzwerk und die verbleibenden Scheitelpunkte in S gesetzt werden.

Schauen Sie sich dieses Video an, um herauszufinden, wie wir die Eckpunkte finden, die von s und t aus erreichbar sind.

https://www.youtube.com/watch?v=FIJaXfUIXJA&index=4&list=PLe-ggMe31CTduQ68XQ-sVj32wYJIspTma

1
Sahil Jain

So geben Sie die genaue Vorgehensweise an, wie Sie den minimalen Schnitt erhalten:

  1. Führen Sie den Ford-Fulkerson-Algorithmus aus, um den maximalen Durchfluss zu ermitteln und das Restdiagramm zu erhalten1.
  2. Führen Sie BFS für das Residuendiagramm aus, um die Scheitelpunkte zu ermitteln, die von der Quelle im Residuendiagramm aus erreichbar sind (wobei zu beachten ist, dass Sie keine Kanten mit verwenden können 0 Kapazität im Residuendiagramm) WICHTIG: Sie müssen im Residuendiagramm umgekehrte Kanten verwenden, um den richtigen Satz erreichbarer Scheitelpunkte zu finden !!! (Siehe diesen Algorithmus)
  3. Alle Kanten im Originaldiagramm , die von einem erreichbaren bis zu einem nicht erreichbaren Scheitelpunkt reichen, sind minimale Schnittkanten. Drucken Sie alle diese Kanten.

1 Diagramm, in dem die Kapazität eines Edges wie die ursprüngliche Kapazität abzüglich seines Durchflusses (Durchfluss aus dem maximalen Durchflussnetzwerk) definiert ist.

1
MichalH

Ich denke, das ist, was andere Leute sagen, aber ich fand es unklar, deshalb hier meine Erklärung:

Führen Sie vom Quellknoten aus eine Überflutung des Diagramms durch, wobei Sie sich nur entlang der Kanten mit verbleibender Kapazität bewegen und jeden besuchten Scheitelpunkt markieren. Sie können dafür ein DFS verwenden. Denken Sie daran, dass die hinteren Kanten eines Scheitelpunkts eine Restkapazität haben - gleich der Strömung entlang der vorderen Kante (dh r (u, v) = verbleibende Kapazität für Kante (u, v), r (v, u) = Strömung (u , v)).

Tatsächlich bestimmt dies den S-Teil des S-T-Schnitts des Graphen.

Der minimale Schnitt ist jetzt die Menge der Kanten, sodass ein Scheitelpunkt von Ihrer Überflutungsfüllung oben markiert ist und der andere Scheitelpunkt nicht markiert ist. Dies sind Kanten ohne Restkapazität (andernfalls hätten Sie sie in Ihrer DFS überquert) und bilden zusammen den Mindestschnitt.

Nach dem Entfernen dieser Kanten bildet der Satz nicht markierter Scheitelpunkte den T-Abschnitt des Schnitts.

0
mindvirus

Nachdem der maximale Durchfluss berechnet wurde, können wir nach Kanten (u,v) Suchen, sodass im Residuendiagramm eine Kante im Residuendiagramm von v bis u und f(v,u) = c(u,v) [was bedeutet, dass die Kante gesättigt ist]

Nachdem wir solche Kanten in die engere Wahl gezogen haben, können wir diese Kanten (u,v) Anhand der Kriterien auswählen, nach denen im Restgraphen kein Pfad von u nach sink t existiert. Wenn diese Bedingung erfüllt ist, bilden solche Kanten einen Teil von (S,T) Cut

Die Laufzeit dieses Algorithmus kann O(E) * O( V + E ) = O( E^2 ) sein.

0
SPV