Ich habe eine Frage zum Level-Graph bzw. Schichtengraph in Dinic. Im Wiki ist dieser wie folgt definiert:
in der englischen Wikipedia ist die Kantenmenge dieses Graphen definiert als: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).
Wobei dist(v) definiert ist als die Distanz des kürzesten Pfades von s zu v.E' = {(u, v) ∈ E: dist(v) = dist(u) + 1}
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):
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.
