Goldberg-Tarjan-Algorithmus

Der Goldberg-Tarjan-Algorithmus, auch Push-Relabel-Algorithmus genannt, ist ein Algorithmus aus der Graphentheorie zur Berechnung eines maximalen Flusses in einem Netzwerk. Er wurde von Andrew Goldberg und Robert Endre Tarjan entwickelt und 1988 publiziert.^[1]

Der Algorithmus

Im Folgenden bezeichnet im Netzwerk $(G,u,s,t)$ $G$ den gerichteten Graphen, $u\colon E(G)\rightarrow \mathbb {R} _{+}$ die Kapazitätsfunktion (wobei $u(e)$ die Kapazität einer Kante $e$ angibt), $s$ den Knoten, von dem der Fluss startet, und $t$ den Zielknoten des Flusses. $V(G)$ bezeichnet die Knotenmenge des Graphen $G$ , $E(G)$ die Kantenmenge und $\delta ^{+}(v)$ die Menge der Kanten, die den Knoten $v$ verlassen.

Der Algorithmus berechnet einen maximalen s-t-Fluss, indem er einen s-t-Präfluss $f$ so lange modifiziert, bis er ein s-t-Fluss ist. Tritt dies ein, ist der erhaltene s-t-Fluss auch maximal. Der Algorithmus arbeitet des Weiteren mit einer Distanzmarkierung, d. h. mit einer Funktion $\psi \colon V(G)\rightarrow \mathbb {N} _{0}$ mit $\psi (s)=|V(G)|$ , $\psi (t)=0$ und für alle Kanten $e=(v,w)\in G_{f}:\ \psi (v)\leq \psi (w)+1$ . Eine Kante $(v,w)\in E(G_{f})$ des Residualgraphen $G_{f}$ heißt erlaubt, wenn sie $\psi (v)=\psi (w)+1$ erfüllt.

Der Algorithmus arbeitet wie folgt:

Setze für alle Kanten $e\in \delta ^{+}(s)$ : $f(e):=u(e)$ , und für alle anderen Kanten $e$ : $f(e):=0$ .
Setze $\psi (s):=|V(G)|$ und für alle anderen Knoten $v$ : $\psi (v):=0$ .
Solange es einen aktiven Knoten $v\in V(G)$ gibt (d. h. einen Knoten $v\in V(G)\setminus \{s,t\}$ , auf dem mehr Fluss ankommt als abfließt), wähle so einen Knoten $v$ und führe aus:
Wenn im Residualgraphen $G_{f}$ keine erlaubte Kante den Knoten $v$ verlässt, setze $\psi (v):=\min\{\psi (w)+1\mid \exists e\in E(G_{f}):e=(v,w)\}$

Ansonsten augmentiere $f$ entlang einer erlaubten Kante $e$ , die $v$ verlässt (d. h.: Falls $e\in E(G)$ ist, setze $f(e):=f(e)+\min\{u_{f}(e),\operatorname {ex} (v)\}$ ; andernfalls ist $e\in E(G_{f})\setminus E(G)$ , und somit $e={\overleftarrow {g}}$ Rückkante einer Kante $g\in E(G)$ , dann setze $f(g):=f(g)-\min\{u_{f}(e),\operatorname {ex} (v)\}$ . Hierbei bezeichnen $u_{f}$ die Residualkapazitäten und $\operatorname {ex} (v)$ den Überschuss am Knoten $v$ , also die Differenz des an $v$ ankommenden und des abfließenden Flusses.).

Eine Modifikation des Flusses $f$ in Schritt 3 wird auch „Push“ genannt, eine Modifikation der Distanzmarkierung $\psi$ „Relabel“. Daher rührt der Name Push-Relabel-Algorithmus.

Am Ende ist $f$ ein maximaler s-t-Fluss. Denn zu jedem Zeitpunkt ist der Knoten $s$ die einzige Quelle und der Algorithmus hält erst an, wenn der Knoten $t$ die einzige Senke ist. Da $\psi$ stets eine Distanzmarkierung bleibt und damit die oben beschriebenen Eigenschaften erfüllt, ist gewährleistet, dass im Residualgraphen $G_{f}$ der Knoten $t$ niemals von der Quelle $s$ aus erreichbar ist. Damit ist sichergestellt, dass der vom Algorithmus berechnete s-t-Fluss tatsächlich ein maximaler s-t-Fluss ist.

Laufzeit

So allgemein wie oben angegeben hat der Algorithmus eine Laufzeit von ${\mathcal {O}}(|V(G)|^{2}\ |E(G)|)$ .

Wählt man in Schritt 3 des Algorithmus immer einen aktiven Knoten $v$ , für den unter allen aktiven Knoten die Distanzmarkierung $\psi$ maximalen Wert hat (also ein $v$ mit $\psi (v)=\max\{\psi (x)\mid x{\text{ ist aktiver Knoten}}\}$ ), lässt sich eine Laufzeit von ${\mathcal {O}}(|V(G)|^{2}{\sqrt {|E(G)|}})$ beweisen. Bei der Implementierung erfordert dies jedoch, dass für jeden Wert $i$ von $0$ bis $2{\mathopen {|}}V(G){\mathclose {|}}-2$ jeweils eine Liste aller aktiven Knoten $v$ mit $\psi (v)=i$ geführt wird (also für jeden Wert, den $\psi$ theoretisch annehmen kann), zusätzlich muss das jeweils aktuelle Maximum von $\psi$ auf der Menge der aktiven Knoten nachgehalten werden. Dies ist erforderlich, damit in jedem Durchlauf der Schleife ein aktiver Knoten $v$ mit maximalen $\psi (v)$ ohne Laufzeitverlust gewählt werden kann.

Mit ausgeklügelteren Implementierungen lassen sich auch Laufzeiten von

${\mathcal {O}}(|V(G)|\ |E(G)|\ \log _{2+{\frac {|E(G)|}{|V(G)|\log(|V(G)|)}}}(|V(G)|))$

und

${\mathcal {O}}(\min\{{\sqrt {|E(G)|}},{\sqrt[{3}]{|V(G)|^{2}}}\}\ |E(G)|\ \log \left({\frac {|V(G)|^{2}}{|E(G)|}}\right)\ \log(u_{\max }))$

erreichen^[2]. Hierbei bezeichnet $u_{\max }$ den maximalen Wert der Kapazitätsfunktion $u$ .

Quellen

Dieter Jungnickel: Graphs, Networks and Algorithms, Springer (1998) ISBN 978-3-540-72779-8
Bernhard Korte, Jens Vygen: Kombinatorische Optimierung: Theorie und Algorithmen. Aus dem Englischen von Rabe von Randow. Springer-Verlag, Berlin / Heidelberg 2008, ISBN 978-3-540-76918-7
Alexander Schrijver: Combinatorial Optimization: Polyhedra and Efficiency, Springer-Verlag, 2003, ISBN 3-540-44389-4

Einzelnachweise

↑ Andrew Goldberg, Robert Tarjan: A new approach to the maximum flow problem. In: Journal of the ACM. Band 35, 1988, S. 921–940.
↑ Bernhard Korte, Jens Vygen: Combinatorial Optimization. 3. Auflage. 2006, S. 168.

Basierend auf einem Artikel in:

Wikipedia.de