Dinic: Schichtengraph == Vereinigung aller kürzesten Pfade?

Moderator: Effiziente Graphenalgorithmen

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

Dinic: Schichtengraph == Vereinigung aller kürzesten Pfade?

Beitrag von deadlock » 26. Mai 2017 12:02

Hallo,

Ich habe eine Frage zum Level-Graph bzw. Schichtengraph in Dinic. Im Wiki ist dieser wie folgt definiert:
Construct the acyclic subgraph G'=(V', A') of the residual network that contains an arc if, and only if, the arc is on at least one (s-t)-path with smallest number of arcs (and contains all nodes incident to these arcs).
in der englischen Wikipedia ist die Kantenmenge dieses Graphen definiert als:
E' = {(u, v) ∈ E: dist(v) = dist(u) + 1}
Wobei dist(v) definiert ist als die Distanz des kürzesten Pfades von s zu v.

Sind die beiden Definitionen miteinander äquivalent? Das Problem auf das ich stoße ist nämlich, dass ich versucht habe, den Level-Graph mit der Definition aus der englischen Wikipedia zu erstellen, dabei aber auch solche Kanten mit enthalten sind, die auf überhaupt keinem Pfad von s zu t enthalten sind. Im Wikipedia-Artikel ist auch ein Beispiel dazu zu sehen: (Zuerst der normale Graph, dann der Level-Graph bei dem die Knoten mit der Distanz zu s beschriftet sind):
Bild
Bild

Nur würde es mich wundern, wenn im Wiki dieser Veranstaltung eine andere Definition als in der englischen Wikipedia verwendet wird, außerdem fällt mir spontan keine effiziente Möglichkeit ein, diese Vereinigung der kürzesten Pfade zu ermitteln.

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

Re: Dinic: Schichtengraph == Vereinigung aller kürzesten Pfade?

Beitrag von Prof. Karsten Weihe » 26. Mai 2017 14:51

deadlock hat geschrieben:
26. Mai 2017 12:02
Sind die beiden Definitionen miteinander äquivalent?
Wenn ich in der Wikipedia nichts übersehen habe, dann sind die beiden Definitionen nicht identisch, aber äquivalent in dem Sinne, dass derselbe Blocking Flow auf denselben Kanten herauskommt.

Der Unterschied ist: Laut Definition in der Wikipedia können auch weitere Kanten dabei sein, die auf kürzesten Pfaden von s zu irgendwelchen Knoten, aber nicht zu t liegen. Diese Kanten machen natürlich keinen Unterschied, da man im Schichtgraphen nicht von diesen nach t kommt.

Ist Ihre Frage beantwortet?

KW

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

Re: Dinic: Schichtengraph == Vereinigung aller kürzesten Pfade?

Beitrag von deadlock » 26. Mai 2017 14:54

Danke für die Antwort. Heißt das, bei der Abnahme ist es auch in Ordnung, wenn in dem GUI noch die zusätzlichen Kanten zu sehen sind?

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

Re: Dinic: Schichtengraph == Vereinigung aller kürzesten Pfade?

Beitrag von Prof. Karsten Weihe » 26. Mai 2017 15:03

deadlock hat geschrieben:
26. Mai 2017 14:54
Danke für die Antwort. Heißt das, bei der Abnahme ist es auch in Ordnung, wenn in dem GUI noch die zusätzlichen Kanten zu sehen sind?
Um ehrlich zu sein: Das war schon bei vielen Abnahmen der Fall. 8)

KW

Antworten

Zurück zu „Effiziente Graphenalgorithmen“