imported>Aka: /* Sperrfluss finden */ Tippfehler entfernt

2018-07-08T11:11:29Z

Sperrfluss finden: Tippfehler entfernt

Neue Seite

Der '''Algorithmus von Dinic''' ist ein [[Algorithmus]] aus der [[Graphentheorie]] zur Bestimmung eines [[Flüsse und Schnitte in Netzwerken|maximalen Flusses in einem Netzwerk]]. Er wurde von [[E. A. Dinic]] (Jefim (Chaim) Dinic) entwickelt und 1970 publiziert. Er ist eine Weiterentwicklung des [[Algorithmus von Edmonds und Karp|Edmonds-Karp-Algorithmus]], den Dinic unabhängig von [[Jack Edmonds]] und [[Richard M. Karp]] entwickelte. Der Algorithmus von Dinic unterscheidet sich vom Edmonds-Karp-Algorithmus, indem in jedem Durchgang nicht nur an einem einzelnen kürzesten s-t-Weg augmentiert wird, sondern mitunter an größeren s-t-Flüssen, die sich aus mehreren kürzesten s-t-Wegen zusammensetzen.

== 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> und <math>E(G)</math> die Kantenmenge. Zu einem Fluss <math>f</math> bezeichnet <math>G_f</math> den [[Residualgraph]]en und <math>G_f^L</math> den [[Flüsse und Schnitte in Netzwerken#Schichtnetzwerk|Schichtgraphen]], also den Graphen, der sich mit <math>G</math> die Knotenmenge teilt und aus genau den Kanten <math>(u,v)\in E(G_f)</math> besteht, die für beliebige Knoten <math>u</math> und <math>v</math> zu einem kürzesten s-v-Weg von <math>G_f</math> gehören. Insbesondere enthält <math>G_f^L</math> auch alle Kanten, die zu einem kürzesten s-t-Weg in <math>G_f</math> gehören. <math>u_f</math> bezeichnet die zum Residualgraph gehörige Residualkapazität. Ein Sperrfluss (auch blockierender Fluss genannt) in <math>G_f^L</math> ist ein s-t-Fluss, der in jedem s-t-Weg in <math>G_f^L</math> mindestens eine Kante auslastet. Zu einer Kante <math>e\in E(G)</math> bezeichnet <math>\overleftarrow{e}</math> die zugehörige Rückkante des Residualgraphen.

Der Algorithmus arbeitet wie folgt:

# Setze <math>f(e):=0</math> für jede Kante <math>e\in E(G)</math>.
# Bestimme den Schichtgraphen <math>G_f^L</math>.
# Bestimme einen Sperrfluss <math>g</math> in <math>G_f^L</math>.
# Falls <math>g</math> der Nullfluss ist, sind wir fertig, ansonsten augmentiere <math>f</math> entlang <math>g</math> (d. h. für jede Kante <math>e\in E(G)</math> setze: <math>f(e):=f(e)+g(e)-g(\overleftarrow{e})</math> (mit <math>g(e):=0</math>, falls <math>e\notin E(G_f^L)</math>)) und springe zu 2.

Am Ende ist <math>f</math> ein maximaler s-t-Fluss, da es im Residualgraphen <math>G_f</math> keinen s-t-Weg mehr gibt.

=== Sperrfluss finden ===
Für Schritt 3 des Algorithmus kann ein Sperrfluss <math>g</math> in <math>G_f^L</math> beispielsweise wie folgt berechnet werden:

# Setze <math>g(e):=0</math> für jede Kante <math>e\in G_f^L</math>.
# Setze <math>H:=G_f^L</math>.
# START
#*<math>P:=[s]</math> (Weg aus nur einem Knoten ohne Kanten)
#*<math>v:=s</math>
#* springe zu VOR.
# VOR
#* Falls in <math>H</math> keine Kante den Knoten <math>v</math> verlässt, springe zu ZURÜCK.
#* Anderenfalls
#** Wähle eine Kante <math>(v,w)</math> aus <math>H</math>.
#** Verlängere <math>P</math> um <math>(v,w)</math>.
#**<math>v:=w</math>
#** Falls <math>v\neq t</math>, springe zu VOR.
#** Falls <math>v=t</math>, springe zu AUGMENTIEREN.
# AUGMENTIEREN
#* Augmentiere <math>g</math> längs <math>P</math> um so viel wie möglich (d. h. für <math>\gamma := \min_{e\in E(P)}u_f(e)</math> setze <math>g(e):=g(e)+\gamma\!\,</math> für jedes <math>e\in E(P)</math>).
#* Entferne die Kanten aus <math>H</math>, die dadurch ausgelastet werden.
#* Springe zu START.
# ZURÜCK
#* Falls <math>v=s</math>, ist <math>g</math> Sperrfluss, also STOP.
#* Anderenfalls
#** Sei <math>(u,v)</math> letzte Kante auf <math>P</math>.
#** Verkürze <math>P</math> um <math>(u,v)</math>.
#** Entferne <math>v</math> und alle mit ihm inzidenten Kanten aus <math>H</math>.
#**<math>v:=u</math>
#** Springe zu VOR.

Am Ende dieses Verfahrens ist <math>g</math> Sperrfluss in <math>G_f^L</math>. Sei <math>m=|E(G)|</math> und <math>n=|V(G)|</math>. Dieses Verfahren benötigt für die Berechnung eines Sperrflusses eine Laufzeit von <math>\mathcal{O}(n m)</math>. Denn jeder Aufruf von AUGMENTIEREN benötigt Laufzeit <math>\mathcal{O}(n)</math> und jeder dieser Aufrufe nimmt eine Kante aus dem Graphen, also gibt es höchstens <math>m</math> dieser Aufrufe (denn der Schichtgraph <math>G_f^L</math> hat höchstens <math>m</math> Kanten). Weil der Schichtgraph <math>G_f^L</math> keine gerichteten Kreise enthält, kann zwischen zwei AUGMENTIEREN-Aufrufen jeder Knoten höchstens einmal durch eine VOR-Operation erreicht werden, also werden insgesamt höchstens <math>\mathcal{O}(n m)</math> solche durchgeführt; eine VOR-Operation kann in konstanter Laufzeit ausgeführt werden. In den ZURÜCK-Operationen wird jedes Mal ein Knoten entfernt, also werden sie höchstens <math>n</math>-mal durchgeführt, alle ZURÜCK-Operationen zusammen haben eine Laufzeit von <math>\mathcal{O}(n+m)</math>.

=== Anmerkung ===
E. A. Dinic arbeitete statt mit dem Schichtgraphen mit einem Teilgraphen, der genau aus den Knoten und Kanten besteht, die auf kürzesten s-t-Wegen liegen. Die Verwendung des Schichtgraphen funktioniert analog, vereinfacht aber die Beschreibung des Algorithmus.

== Laufzeit ==
Sei <math>m=|E(G)|</math> und <math>n=|V(G)|</math>. Der Algorithmus von Dinic benötigt höchstens <math>n-1</math> Durchläufe. Der Schichtgraph <math>G_f^L</math> kann mit [[Breitensuche]] in Laufzeit <math>\mathcal{O}(m)</math> berechnet werden. Ein Sperrfluss in <math>G_f^L</math> kann mit der oben angegebenen Methode in Laufzeit <math>\mathcal{O}(n m)</math> berechnet werden. Damit ergibt sich eine Gesamtlaufzeit von <math>\mathcal{O}(n^2 m)</math>. Dies ist auch die Laufzeit, die von Dinic 1970 bewiesen wurde. Allerdings arbeitet der [[Goldberg-Tarjan-Algorithmus]] schneller.

Mit einer Verbesserung von [[Alexander Karzanov]] von 1974 lässt sich für den Algorithmus von Dinic auch eine Laufzeit von <math>\mathcal{O}(n^3 + nm)</math> erreichen.

== Quellen ==
* [[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
* Helmut Alt: [http://www.inf.fu-berlin.de/lehre/WS06/HA/skript/skript.pdf Vorlesungsskript ''Höhere Algorithmik'', Wintersemester 2006/2007, Freie Universität Berlin.] (PDF; 2,5 MB)

== Weblinks ==
* E. A. Dinic: [http://www.cs.bgu.ac.il/~dinitz/D70.pdf ''Algorithm for solution of a problem of maximum flow in a network with power estimaton'', 1970] (PDF; 428 kB) – E. A. Dinics Veröffentlichung des Algorithmus

[[Kategorie:Algorithmus (Graphentheorie)|Dinic]]
[[Kategorie:Optimierungsalgorithmus|Dinic]]

Algorithmus von Dinic - Versionsgeschichte

imported>Aka: /* Sperrfluss finden */ Tippfehler entfernt