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.<ref>{{#invoke:Vorlage:Literatur|f}}</ref>

Der Algorithmus

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

Der Algorithmus berechnet einen maximalen s-t-Fluss, indem er einen s-t-Präfluss <math>f</math> 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 <math>\psi\colon V(G) \rightarrow \mathbb{N}_0</math> mit <math>\psi(s)=|V(G)|</math>, <math>\psi(t)=0</math> und für alle Kanten <math>e=(v,w)\in G_f: \ \psi(v) \leq \psi(w) +1</math>. Eine Kante <math>(v, w) \in E(G_f)</math> des Residualgraphen <math>G_f</math> heißt erlaubt, wenn sie <math>\psi(v) = \psi(w) +1</math> erfüllt.

Der Algorithmus arbeitet wie folgt:

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

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

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

Am Ende ist <math>f</math> ein maximaler s-t-Fluss. Denn zu jedem Zeitpunkt ist der Knoten <math>s</math> die einzige Quelle und der Algorithmus hält erst an, wenn der Knoten <math>t</math> die einzige Senke ist. Da <math>\psi</math> stets eine Distanzmarkierung bleibt und damit die oben beschriebenen Eigenschaften erfüllt, ist gewährleistet, dass im Residualgraphen <math>G_f</math> der Knoten <math>t</math> niemals von der Quelle <math>s</math> 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 <math>\mathcal{O}(|V(G)|^2 \ |E(G)|)</math>.

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

Mit ausgeklügelteren Implementierungen lassen sich auch Laufzeiten von

<math>\mathcal{O}(|V(G)| \ |E(G)| \ \log_{2+\frac{|E(G)|}{|V(G)| \log (|V(G)|)}}(|V(G)|))</math>

und

<math>\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}))</math>

erreichen<ref>{{#invoke:Vorlage:Literatur|f}}</ref>. Hierbei bezeichnet <math>u_{\max}</math> den maximalen Wert der Kapazitätsfunktion <math>u</math>.

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