Um den maximalen Fluss in einem Graph zu finden, warum reicht es nicht aus, nur alle augmentierenden Pfade mit der minimalen Kantenkapazität in diesem Pfad zu sättigen, ohne die hinteren Kanten zu berücksichtigen? Ich meine, was ist der Punkt, der es einen hinteren Rand nennt, wenn wir davon ausgehen, dass es fließt?Warum sind Rückkanten im Ford-Fulkerson-Algorithmus erforderlich?
Rückkanten sind notwendig, wenn Sie den Ford-Fulkerson-Algorithmus ausführen, falls der ausgewählte Pfad nicht Teil des Gesamtflusses ist.
Als ein Beispiel, wo Hinterkanten erforderlich sind, sollten diese Strömung Netzwerk:
s
/\
a b
\/\
c d
\/
t
wird angenommen, dass alle Kanten nach unten zeigen und dass alle Kanten haben eine Kapazität 1 und dass Sie einen Fluss von s finden bis t . Angenommen, in der ersten Iteration von Ford-Fulkerson nehmen Sie den Weg s -> b -> c -> t. An dieser Stelle haben Sie eine Flusseinheit von s nach t geschoben. Wenn Sie nicht in irgendwelchen Hinterkanten hinzufügen, sind Sie mit dieser links:
s
/
a b
\ \
c d
/
t
Es gibt nicht mehr s-t Pfade, aber das bedeutet nicht, dass Sie einen maximalen Durchfluss haben. Sie können zwei Flusseinheiten von s nach t schieben, indem Sie eine entlang des Pfades s -> a -> c -> t und die andere entlang des Pfades s -> b -> d -> t senden. Ohne Rückflanken im Restflussnetzwerk würden Sie diesen anderen Pfad nie finden.
Hoffe, das hilft!
Können Sie bitte näher darauf eingehen, was die Backedges in Ihrem speziellen Fall ausmacht? Vielen Dank! – bluejamesbond
@bluejamesbond Hier würden die hinteren Kanten von b nach s zeigen, von c nach b und von t nach c (es ist die Umkehrung der Kanten entlang des Weges). Diese Kanten ergeben dann einen augmentierenden Pfad von s nach t, der anzeigt, dass der Fluss nicht maximal ist. – templatetypedef
Wann wird es diese Wege jedoch nehmen? – bluejamesbond