Goldberg-Tarjan-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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 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:

  1. Setze für alle Kanten e\in \delta^+(s): f(e):=u(e), und für alle anderen Kanten e: f(e):=0.
  2. Setze \psi(s):=|V(G)| und für alle anderen Knoten v: \psi(v):=0.
  3. 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 tue:
    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[Bearbeiten]

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[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1.  Andrew Goldberg, Robert Tarjan: A new approach to the maximum flow problem. In: Journal of the ACM. 35, 1988, S. 921-940.
  2.  Bernhard Korten, Jens Vygen: Combinatorial Optimization. 2006, S. 168.