Seite 1 von 1

Preflow-push: target als aktiver Knoten

Verfasst: 9. Jun 2017 16:06
von deadlock
Hallo,

Laut Wiki wird die Invariante eingehalten, dass S alle aktiven Knoten enthält. Laut diesem Wiki-Eintrag gehört t (der Target-Knoten) per Definition nicht zu den aktiven Knoten, sodass t niemals zur Menge der aktiven Knoten S hinzugefügt werden darf. Beim Hinzufügen eines Knotens w in S wird allerdings nicht explizit ausgeschlossen, dass w = t (nur w = s), deshalb frage ich mich: Fehlt das im Wiki, oder kann man irgendwie von vornherein ausschließen, dass im Induktionsschritt 3.1 der Fall w = t eintritt?

In meiner Implementierung ist es nämlich so, dass w = t sehr wohl eintritt, und mir ist auch nicht klar, wie man diesen Fall von vornherein ausschließen könnte. Falls das also kein Fehler im Wiki ist, fände ich eine Erklärung, warum man hier nicht explizit w ≠ t prüfen muss, sehr hilfreich.

Re: Preflow-push: target als aktiver Knoten

Verfasst: 12. Jun 2017 10:36
von Prof. Karsten Weihe
Ja, auch der Fall w=t muss abgefangen werden so wie der Fall w=s. Leider habe ich momentan ein Problem mit dem Edieren, sobald das behoben ist, korrigiere ich diesen Punkt.

KW

Re: Preflow-push: target als aktiver Knoten

Verfasst: 20. Jun 2017 05:53
von Prof. Karsten Weihe
Ok, funktioniert wieder und ist korrigiert.

KW