Preflow-push: target als aktiver Knoten

Moderator: Effiziente Graphenalgorithmen

deadlock
Neuling
Neuling
Beiträge: 10
Registriert: 12. Apr 2012 16:38

Preflow-push: target als aktiver Knoten

Beitrag von deadlock » 9. Jun 2017 16:06

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.

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Preflow-push: target als aktiver Knoten

Beitrag von Prof. Karsten Weihe » 12. Jun 2017 10:36

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

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Preflow-push: target als aktiver Knoten

Beitrag von Prof. Karsten Weihe » 20. Jun 2017 05:53

Ok, funktioniert wieder und ist korrigiert.

KW

Antworten

Zurück zu „Effiziente Graphenalgorithmen“