Zykel bei Goldberg-Tarjan

Moderator: Effiziente Graphenalgorithmen

the D
Erstie
Erstie
Beiträge: 14
Registriert: 27. Nov 2009 12:43

Zykel bei Goldberg-Tarjan

Beitrag von the D » 1. Feb 2017 16:16

Hallo allerseits,

ich habe gerade Goldberg-Tarjan implementiert und mir fiel auf, dass der produzierte (zulässige) Fluss am Ende viele "unnötige" Zykel enthält, also solche, wo Fluss aus s (dem Startknoten) herausfließt und dann über einen Zykel wieder nach s zurückkommt.

Ich vermute es liegt daran, dass der "Überfluss" i.A. nicht auf dem selben Weg nach s zurück "gepusht" wird auf dem er s verlassen hat. Bei den anderen Algorithmen, die mittels DFS/BFS augmentierende Pfade suchen kann sowas aus naheliegenden gründen ja nicht passieren.

Ist das mit den Zykeln ein normaler Nebeneffekt von Goldberg-Tarjan oder habe ich irgendwo etwas falsch gemacht?

Grüße

Dominik

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

Re: Zykel bei Goldberg-Tarjan

Beitrag von Prof. Karsten Weihe » 12. Feb 2017 20:23

the D hat geschrieben: Ist das mit den Zykeln ein normaler Nebeneffekt von Goldberg-Tarjan oder habe ich irgendwo etwas falsch gemacht?
Ich denke, das ist absolut ok.

Man kann ja hinterher die Zykel wieder eliminieren (nicht gefordert).

KW

Antworten

Zurück zu „Effiziente Graphenalgorithmen“