Ford-Fulkerson Max Flow-Algorithmus Analyse

Question

Ich lese Ford-Fulkerson Maxflow-Algorithmus in Buch-Algorithmen von Robert Sedgewick geschrieben. Hier Autor erwähnt, wie unten

Die Anzahl der Vermehrung Pfade benötigten in der kürzest-Vermehrung Pfad Umsetzung der Ford-Fulkerson maxflow Algorithmus für eine Strömungs Netzwerk mit V Eckpunkten und E Kanten höchstens EV/2 .

Proof Skizze: Jede Vermehrung Pfad hat eine kritische kanten eine Kante, die aus dem Rest Netzwerk gelöscht wird, weil sie entweder zu eine Vorderkante entspricht, um die Kapazität oder einer hinteren Kante gefüllt wird, dass entleert wird. Jedes Mal, wenn eine Kante eine kritische Kante ist, muss die Länge des Augmentationspfades um 2 erhöht werden. Da ein erweiterter Pfad eine Länge von höchstens V hat, kann jede Kante auf höchstens V/2 erweiternden Pfaden sein, und die die Gesamtzahl der Augmentationswege beträgt höchstens EV/2.

Meine Fragen auf obigen Text sind

1. Wie wir sagen bekamen, wenn augumenting Pfadlänge atmost V ist, kann jede Kante in seinem atmost V/2 augumenting Wegen?

Anfrage, um oben mit einfachen Beispiel zu erklären, wenn möglich.

Answer 1

müssen Sie zuerst die vorherige Anweisung

Jedes Mal, wenn eine Kante ist eine kritische Kante, die Länge des zunehmenden Weg zu beweisen, durch sie durch 2.

Eine Pfadlänge erhöhen müssen höchstens V, weil es keinen Sinn macht, einen Eckpunkt zweimal zu durchlaufen (alle Kanten zwischen den beiden Vorkommen eines Eckpunkts x auf einem solchen Pfad zu entfernen), und Sie haben immer noch einen guten Pfad mit mindestens der Kapazität des Originals Pfad).

Wenn also die Pfadlänge höchstens V beträgt und jedes Mal, wenn eine Kante kritisch ist, die Länge des Pfads um 2 zunimmt, dann kann eine Kante höchstens V/2-mal kritisch sein.