Ich lese über das Maximum Flow Problem Here. Ich konnte die Einleitung hinter dem Residuendiagramm nicht verstehen. Warum betrachten wir eine Hinterkante während der Berechnung des Flusses?
Kann mir jemand helfen, das Konzept der Residual Graph zu verstehen.
Wie sich der Algorithmus in ungerichtetem Diagramm ändertMaximaler Fluss in gerichteter Grafik
Ein Restdiagramm ist ein Diagramm, das anzeigt, ob Sie mehr Durchfluss haben können als Sie derzeit tun (da Sie mit 0 beginnen). Wenn Sie das Problem "gelöst" haben, sollten Sie nicht in der Lage sein, mit Ihrem Restgraphen von der Quelle zur Senke zu gelangen (da das Restdiagramm zeigt, ob mehr Strömung verfügbar ist).
Denken Sie an die normale Grafik als Geschwindigkeit und die Restkurve als Beschleunigung. Der Restgraph zeigt grundsätzlich die Geschwindigkeitsänderung.
Der Algorithmus sollte sich in einem ungerichteten Graphen nicht ändern. Ein ungerichteter Graph ist derselbe wie ein gerichteter Graph, bei dem die Pfeile in beide Richtungen statt in keine Richtung zeigen. Mehr dazu hier: https://math.stackexchange.com/questions/677743/finding-the-max-flow-of-an-undirected-graph-with-ford-fulkerson
Der Rest-Graph ist der Rest des Netzwerks, nachdem Sie den Fluss, den Sie bereits durchlaufen haben, entfernen. Angenommen, Sie haben eine Kante AB mit der Kapazität 10 und der aktuelle Fluss bewegt sich 7 Einheiten durch AB, dann sollten Sie im Restgraphen eine Kante AB mit der Kapazität 3 (was übrig ist) und eine Kante BA mit der Kapazität 7 haben (dies erscheint, weil Sie Wenn Sie einen Weg von der Quelle zu B und von A zur Senke finden, können Sie die vorherige Lösung umleiten, um die Kante AB nicht zu verwenden oder weniger davon zu verwenden.
Um es klarer zu machen, siehe dieses Bild 
. Sagen Sie, der erste Pfad, den Sie finden, ist s, u, v, t und Sie drücken 10 Fluss durch ihn. Jetzt können Sie im Restgraphen den Pfad s, v, u, t finden (auch wenn die vu-Kante nicht im ursprünglichen Graphen vorhanden ist) und den 5-Fluss durch ihn schieben. Was passiert ist, ist, dass 5 Flusseinheiten, die von "u" nach "v" gehen, jetzt umgeleitet werden, um nach t zu gehen, und die 5 Einheiten, die von "u" nach "v" kommen, kommen nun von s.
Wenn Sie eine ungerichtete Grafik haben, können Sie eine Kante AB durch eine gerichtete Kante AB und eine gerichtete Kante BA mit derselben Kapazität wie die ursprüngliche ungerichtete Kante ersetzen. Sie können nicht in beide Richtungen fließen, weil Sie die gleiche Lösung erhalten, indem Sie die kleinere aufheben. Es gibt nichts zu gewinnen, indem man den Fluss hin und her schickt.