89.1.213.130: /* Quellen */ Typo

2025-04-11T23:58:33Z

Quellen: Typo

Neue Seite

Der '''Goldberg-Tarjan-Algorithmus''', auch '''Push-Relabel-Algorithmus''' genannt, ist ein Algorithmus aus der [[Graphentheorie]] zur Berechnung eines [[Flüsse und Schnitte in Netzwerken|maximalen Flusses in einem Netzwerk]]. Er wurde von Andrew Goldberg und [[Robert Tarjan|Robert Endre Tarjan]] entwickelt und 1988 publiziert.<ref>{{Literatur |Autor=Andrew Goldberg, Robert Tarjan |Titel=A new approach to the maximum flow problem |Sammelwerk=[[Journal of the ACM]] |Band=35 |Jahr=1988 |Seiten=921–940}}</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 [[Residualgraph]]en <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 [[Residualgraph]]en <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>{{Literatur|Autor=Bernhard Korte, Jens Vygen|Titel=Combinatorial Optimization|Jahr=2006|Seiten=168|Auflage=3.}}</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 ==
<references />

[[Kategorie:Netzwerktheorie]]
[[Kategorie:Algorithmus]]
[[Kategorie:Algorithmus (Graphentheorie)]]
[[Kategorie:Optimierungsalgorithmus]]

Goldberg-Tarjan-Algorithmus - Versionsgeschichte

89.1.213.130: /* Quellen */ Typo