Netzwerk

Ein Netzwerk (engl. network) ${\displaystyle N=(G,u,s,t)}$ besteht aus einem gerichteten Graphen ${\displaystyle G=(V,E)}$ mit zwei ausgezeichneten Knoten (engl. vertex/vertices), einer Quelle (engl. source) ${\displaystyle s}$ und einer Senke (engl. target) ${\displaystyle t}$ aus ${\displaystyle V}$, sowie einer Kapazitätsfunktion ${\displaystyle u\colon E\rightarrow \mathbb {R} _{+}}$, die jeder Kante ${\displaystyle e\in E}$ eine nichtnegative Kapazität zuweist, ${\displaystyle e\mapsto u(e)}$. Hat die Kapazitätsfunktion ausschließlich ganzzahlige Werte, so existiert eine maximale Flussfunktion (siehe folgende Definition), die ebenfalls nur ganzzahlige Werte hat.

Fluss

• Beispiel für einen Fluss. Die Belegung steht zusammen mit der Kapazität an den einzelnen Kanten. Der Wert des ${\displaystyle s}$-${\displaystyle t}$-Flusses ist 2.
• Beispiel für ein Residualnetzwerk. Auf dem Pfad ${\displaystyle s}$, ${\displaystyle a}$, ${\displaystyle b}$, ${\displaystyle t}$ lässt sich der Fluss um den Wert 2 augmentieren.

Ein Fluss ist eine Funktion ${\displaystyle f\colon E\rightarrow \mathbb {R} _{+}}$, die jeder Kante ${\displaystyle e\in E}$ im Netzwerk einen nichtnegativen Flusswert ${\displaystyle f(e)\in \mathbb {R} _{+}}$ zuweist. Dabei muss folgende Bedingung erfüllt sein:

Kapazitätskonformität:

Der Flusswert auf einer Kante ist höchstens so groß wie die Kapazität der Kante, das heißt, es gilt:

${\displaystyle \forall e\in E:f(e)\leq u(e)}$.

Ist zusätzlich die folgende Bedingung erfüllt, heißt der Fluss ${\displaystyle s}$-${\displaystyle t}$-Fluss:

Flusserhalt:

Abgesehen von der Quelle s und der Senke t muss in jeden Knoten genau so viel hineinfließen wie herausfließt, das heißt:

${\displaystyle \forall v\in V\setminus \{s,t\}:\sum _{e\in \operatorname {\delta ^{-}} (v)}f(e)=\sum _{e\in \operatorname {\delta ^{+}} (v)}f(e)}$

Dabei ist

${\displaystyle \operatorname {\delta ^{-}} (v){\overset {\underset {\mathrm {def} }{}}{=}}\{e=(x,v)\in E\mid x\in V\}}$

die Menge der in ${\displaystyle v}$ hineinführenden und

${\displaystyle \operatorname {\delta ^{+}} (v){\overset {\underset {\mathrm {def} }{}}{=}}\{e=(v,x)\in E\mid x\in V\}}$

die Menge der aus ${\displaystyle v}$ hinausführenden Kanten.

Gilt zudem Flusserhalt auch in ${\displaystyle s}$ und ${\displaystyle t}$, hat man eine Strömung oder Zirkulation. Man kann zeigen, dass Inzidenzvektoren einer Zirkulation entsprechen, wenn sie im Zyklenraum ${\displaystyle Z(G)}$ von ${\displaystyle G}$ liegen.

Schnitt

Eine echte Teilmenge ${\displaystyle S}$ der Knoten in einem Netzwerk, die ${\displaystyle s}$, aber nicht ${\displaystyle t}$ enthält, nennt man einen ${\displaystyle s}$-${\displaystyle t}$-Schnitt. Oft wird unter einem Schnitt auch die Menge aller Kanten verstanden, die zwischen den Partitionen ${\displaystyle S}$ und ${\displaystyle V\setminus S}$ verlaufen. Die Kapazität eines Schnittes ist die Summe der Kapazitäten der von ${\displaystyle S}$ nach ${\displaystyle V\setminus S}$ verlaufenden Kanten.

Schnitte geben eine obere Schranke für den Wert der ${\displaystyle s}$-${\displaystyle t}$-Flüsse. Das Max-Flow-Min-Cut-Theorem besagt, dass auch umgekehrt Flusswerte eine Untere Schranke für Schnittkapazitäten sind. Beide Konzepte entsprechen also einander auf eine natürliche Art und Weise.

Ferner entspricht der Fluss im gesamten Netzwerk dem Fluss durch einen beliebigen Schnitt. Zusammen mit der Kapazität des Schnittes gilt daher ${\displaystyle f(S,T)=|f|\leq c(S,T)}$. Handelt es sich um einen minimalen Schnitt, entspricht der Fluss der Kapazität des Schnittes.

Residualnetzwerk

Das Residualnetzwerk ${\displaystyle N_{f}}$, oder auch Restnetzwerk, zum Fluss ${\displaystyle f}$ mit Residualgraphen ${\displaystyle G_{f}}$ und Residualkapazitäten ${\displaystyle u_{f}}$ zeigt die restlichen Kapazitäten des Netzwerks an. Der Residualgraph ${\displaystyle G_{f}}$ hat dieselbe Knotenmenge wie ${\displaystyle G}$ und besteht aus den von ${\displaystyle f}$ nicht ausgelasteten Kanten ergänzt um Rückkanten: Für jede Kante ${\displaystyle e=(v,w)\in E}$ mit ${\displaystyle f(e)>0}$ enthält ${\displaystyle E_{f}}$ eine Rückkante ${\displaystyle {\overleftarrow {e}}=(w,v)}$. Die Residualkapazitäten ${\displaystyle u_{f}(e)}$ geben für eine Kante ${\displaystyle e\in E}$ an, um wie viel der Fluss auf ihr noch erhöht werden kann, und für eine Rückkante ${\displaystyle {\overleftarrow {e}}}$, um wie viel der Fluss auf der zugehörigen Hinkante verringert werden darf. Also:

${\displaystyle \forall e\in E:u_{f}(e)=u(e)-f(e)}$, falls ${\displaystyle f(e)<u(e)}$

${\displaystyle \forall {\overleftarrow {e}}\in E_{f}\setminus E:u_{f}({\overleftarrow {e}})=f(e)}$

Initialisiere ${\displaystyle E_{f}=\emptyset }$; ${\displaystyle u_{f}\equiv u}$;
1. Für alle Kanten ${\displaystyle e\in E}$
2.    if(${\displaystyle f(e)>0}$)
3.       Füge ${\displaystyle {\overleftarrow {e}}}$ in ${\displaystyle E_{f}}$ ein
4.       Setze ${\displaystyle u_{f}({\overleftarrow {e}}):=\!\,\!\,f(e)}$
5.    if(${\displaystyle f(e)<u(e)}$)
6.       Füge ${\displaystyle e}$ in ${\displaystyle E_{f}}$ ein
7.       Setze ${\displaystyle u_{f}(e):=\!\,\!\,u(e)-f(e)}$
8. gib aus ${\displaystyle N_{f}=(V,E_{f},u_{f},s,t)}$

Schichtnetzwerk

Der Level eines Knotens ${\displaystyle \operatorname {level} (v){\overset {\underset {\mathrm {def} }{}}{=}}\delta _{f}(s,v)}$ ist die Anzahl der Kanten eines kürzesten Weges von ${\displaystyle s}$ nach ${\displaystyle v}$ im Residualnetzwerk zum Fluss ${\displaystyle f}$. Der ${\displaystyle i}$-te Level eines Graphen ist die Menge aller Knoten mit Level ${\displaystyle i}$ also ${\displaystyle V_{i}{\overset {\underset {\mathrm {def} }{}}{=}}\{v\in V\mid \operatorname {level} (v)=i\}}$. Eine Kante ${\displaystyle e=(w,v)}$ mit Flusswert ${\displaystyle f(e)}$ heißt nützlich von ${\displaystyle w}$ nach ${\displaystyle v}$, falls ${\displaystyle f(e)<u(e)}$. Falls gilt ${\displaystyle f(e)>0}$, heißt sie nützlich von ${\displaystyle v}$ nach ${\displaystyle w}$. Eine Kante heißt nützlich aus einer Menge, falls sie nützlich von einem Element der Menge in ein Element außerhalb der Menge ist. Analog erklärt man nützlich in eine Menge. Das Schichtnetzwerk oder Levelnetzwerk ${\displaystyle {\tilde {N_{f}}}}$ zum Fluss ${\displaystyle f}$ ist ein Teilgraph von ${\displaystyle G}$ mit

1. ${\displaystyle {\tilde {V_{f}}}{\overset {\underset {\mathrm {def} }{}}{=}}V}$
2. ${\displaystyle {\tilde {E_{f}}}{\overset {\underset {\mathrm {def} }{}}{=}}\{e=(w,v)\in E_{f}\mid \operatorname {level} (w)=\operatorname {level} (v)-1\}}$

Schicht- und Residualnetzwerk können in linearer Laufzeit berechnet werden.

Besondere Wege und Flüsse

Ein x-y-Weg oder Pfad ${\displaystyle W(x,y)}$ ist eine Folge von Kanten, wobei der Ausgangsknoten jeder Kante der Endknoten ihres Vorgängers ist. Die Länge eines Weges ${\displaystyle \delta _{W}(x,y)}$, auch ${\displaystyle dist_{W}(x,y)}$ ist die Anzahl der Kanten im Weg.

Die Distanz zwischen ${\displaystyle x}$ und ${\displaystyle y}$ ist die Länge eines kürzesten Weges, falls einer existiert, und „unendlich“, falls nicht. Ein Weg im Residualnetzwerk heißt augmentierender Weg; die Bezeichnungen verbessernder Weg oder erhöhender Weg sind auch gebräuchlich. Jeder ${\displaystyle s}$-${\displaystyle t}$-Fluss lässt sich in Flüsse auf ${\displaystyle s}$-${\displaystyle t}$-Wegen und auf Kreisen zerlegen. Genau dann, wenn in einem Netzwerk zu einem ${\displaystyle s}$-${\displaystyle t}$-Fluss kein augmentierender Weg existiert, hat der Fluss maximalen Wert. Diesen Sachverhalt nutzen der Algorithmus von Ford und Fulkerson und der Algorithmus von Edmonds und Karp aus.

Ein Fluss ${\displaystyle f}$ in einem Netzwerk ${\displaystyle (G,u,s,t)}$ heißt blockierend, falls in jedem ${\displaystyle s}$-${\displaystyle t}$-Weg in ${\displaystyle G}$ eine Kante ${\displaystyle e}$ blockiert, oder auch saturiert, ist, d. h. ${\displaystyle f(e)=u(e)}$.

${\displaystyle \operatorname {PUSH} (v,w)}$
-> Voraussetzungen: ${\displaystyle v\in V}$ hat Exzess, ${\displaystyle u_{f}(v,w)>0}$ und ${\displaystyle \operatorname {h} (v)=\operatorname {h} (w)+1}$
-> Beschreibung: Schiebe ${\displaystyle d_{f}(v,w){\overset {\underset {\mathrm {def} }{}}{=}}min\{\operatorname {ex} (v),u_{f}(v,w)\}}$
              Einheiten Fluss von ${\displaystyle v}$ nach ${\displaystyle w}$
1. ${\displaystyle d_{f}(v,w)\leftarrow min\{\operatorname {ex} (v),u_{f}(v,w)\}}$
2. ${\displaystyle f(v,w)\leftarrow f(v,w)+d_{f}(v,w)}$
3. ${\displaystyle f(w,v)\leftarrow -f(v,w)}$
4. ${\displaystyle \operatorname {ex} (v)\leftarrow \operatorname {ex} (v)-d_{f}(v,w)}$
5. ${\displaystyle \operatorname {ex} (w)\leftarrow \operatorname {ex} (w)+d_{f}(v,w)}$

${\displaystyle \operatorname {LIFT} (v)}$
Voraussetzungen: ${\displaystyle v\in V}$ hat Exzess und es gilt für beliebige ${\displaystyle w\in V}$:
                  ${\displaystyle (v,w)\in E_{f}\Rightarrow \operatorname {h} (v)\leq \operatorname {h} (w)}$
Beschreibung: inkrementiere die Höhe von ${\displaystyle v}$
1. ${\displaystyle \operatorname {h} (v)\leftarrow 1+min\{\operatorname {h} (w)\mid (v,w)\in E_{f}\}}$

Präflüsse

${\displaystyle s}$-${\displaystyle t}$-Präflüsse, oder auch Vorflüsse, (engl. preflow) sind eine Verallgemeinerung von ${\displaystyle s}$-${\displaystyle t}$-Flüssen. Dieser Begriff ist nur bei komplexeren (und wesentlich effizienteren) Flussalgorithmen von Bedeutung.

Ein ${\displaystyle s}$-${\displaystyle t}$-Präfluss ist eine Funktion ${\displaystyle f\colon A\rightarrow \mathbb {R} _{+}}$ mit Kapazitätskonformität wie oben und folgender Abschwächung des Flusserhalts:

${\displaystyle \forall u\in V\setminus \{s\}:\operatorname {ex} (u)\geq 0}$

Das bedeutet, nur den Knoten ${\displaystyle s}$ darf mehr Fluss verlassen, als ihn erreicht. Ein ${\displaystyle s}$-${\displaystyle t}$-Präfluss hat Überschuss in einem Knoten, oder auch Overflow, falls sein Überschuss (wie oben) echt größer als Null ist. Das Residualnetzwerk wird analog zu oben gebildet.

Die Höhenfunktion oder Distanzmarkierung in einem Netzwerk mit ${\displaystyle s}$-${\displaystyle t}$-Präfluss ${\displaystyle f}$ ist eine Abbildung ${\displaystyle \operatorname {h} \colon V\rightarrow \mathbb {N} _{0}}$ mit ${\displaystyle \operatorname {h} (s)=|V|}$, ${\displaystyle \operatorname {h} (t)=0}$ und ${\displaystyle \operatorname {h} (v)\leq \operatorname {h} (w)+1}$ für alle Kanten ${\displaystyle e=(v,w)\in E_{f}}$.

Ferner erklärt man die Operationen Push und Lift algorithmisch, so wie rechts beschrieben. Mit diesen Mitteln kann man Preflow-Push-Algorithmen entwerfen und untersuchen, etwa den Goldberg-Tarjan-Algorithmus (nach Andrew Goldberg und Robert Tarjan). Bei diesen Algorithmen kann man die Datenstrukturen während der Algorithmus läuft nicht als ${\displaystyle s}$-${\displaystyle t}$-Fluss interpretieren. Die Methode von Goldberg und Tarjan initialisiert einen Präfluss und terminiert, falls gewisse Manipulationen der Struktur einen ${\displaystyle s}$-${\displaystyle t}$-Fluss liefern. Das ist dort stets nach endlich vielen Schritten der Fall und dieser ${\displaystyle s}$-${\displaystyle t}$-Fluss ist dann stets maximal.

Max-Flow Algorithmen nach Veröffentlichung

Jahr	Autor(en)	Name	Laufzeiten
1956	Ford, Fulkerson	Algorithmus von Ford und Fulkerson	${\displaystyle {\mathcal {O}}\left(m\cdot n\cdot u_{\max }\right)}$, falls alle Kapazitäten ganzzahlig sind
1969	Edmonds, Karp	Algorithmus von Edmonds und Karp	${\displaystyle {\mathcal {O}}\left(m^{2}\cdot n\right)}$
1970	Dinic	Algorithmus von Dinic	${\displaystyle {\mathcal {O}}\left(m\cdot n^{2}\right)}$
1973	Dinic, Gabow		${\displaystyle {\mathcal {O}}\left(m\cdot n\cdot \log \left(u_{\max }\right)\right)}$
1974	Karzanov		${\displaystyle {\mathcal {O}}\left(n^{3}\right)}$
1977	Cherkassky		${\displaystyle {\mathcal {O}}\left(n^{2}\cdot {\sqrt {m}}\right)}$
1980	Galil, Naamad		${\displaystyle {\mathcal {O}}\left(m\cdot n\cdot \log \left(n\right)^{2}\right)}$
1983	Sleator, Tarjan		${\displaystyle {\mathcal {O}}\left(m\cdot n\cdot \log \left(n\right)\right)}$
1986	Goldberg, Tarjan	Goldberg-Tarjan-Algorithmus	${\displaystyle {\mathcal {O}}\left(m\cdot n\cdot \log \left({\frac {n^{2}}{m}}\right)\right)}$
1987	Ahuja, Orlin		${\displaystyle {\mathcal {O}}\left(m\cdot n+n^{2}\cdot \log \left(u_{\max }\right)\right)}$
1987	Ahuja, Orlin, Tarjan		${\displaystyle {\mathcal {O}}\left(m\cdot n\cdot \log \left(2+{\frac {n\cdot {\sqrt {\log(u_{\max })}}}{m}}\right)\right)}$
1990	Cheriyan, Hagerup, Mehlhorn		${\displaystyle {\mathcal {O}}\left({\frac {n^{3}}{\log \left(n\right)}}\right)}$
1990	Alon		${\displaystyle {\mathcal {O}}\left(m\cdot n+{\sqrt[{3}]{n^{8}}}\cdot \log \left(n\right)\right)}$
1992	King, Rao, Tarjan		${\displaystyle {\mathcal {O}}\left(m\cdot n+n^{2+e}\right)}$
1993	Philipps, Westbrook		${\displaystyle {\mathcal {O}}\left(m\cdot n\cdot \log _{\frac {m}{n}}\left(n\right)+n^{2}\cdot \log \left(n\right)^{2+e}\right)}$
1994	King, Rao, Tarjan		${\displaystyle {\mathcal {O}}\left(m\cdot n\cdot \log _{\frac {m}{n\cdot \log(n)}}(n)\right)}$
1997	Goldberg, Rao		${\displaystyle {\mathcal {O}}\left(\min\{{\sqrt {m}},{\sqrt[{3}]{n^{2}}}\}\cdot m\cdot \log \left({\frac {n^{2}}{m}}\right)\cdot \log(u_{\max })\right)}$
2012	Orlin, King, Rao, Tarjan		${\displaystyle {\mathcal {O}}\left(n\cdot m\right)}$
2022	Chen, Kyng, Liu, Peng, Gutenberg, Sachdeva		${\displaystyle m^{1+o(1)}}$ für ganzzahlige Kapazitäten, die polynomiell beschränkt sind
Legende: ${\displaystyle n=|V|=}$ „Anzahl der Knoten“ ${\displaystyle m=|E|=}$ „Anzahl der Kanten“ ${\displaystyle u_{\max }=}$ „Maximum der Kapazitätsfunktion ${\displaystyle u}$“ ↑ Joost-Pieter Katoen: Datenstrukturen und Algorithmen. Vorlesung 18: Maximaler Fluss (K26). S. 40-41, archiviert vom Original am 1. Januar 2021; abgerufen am 1. Januar 2021.  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/moves.rwth-aachen.de  ↑ Steven J. Phillips, Jeffery Westbrook: On-Line Load Balancing and Network Flow. In Algorithmica Volume 21, Number 3, Juli 1998 245-261 ↑ V. King, S. Rao, R. Tarjan: A Faster Deterministic Maximum Flow Algorithm. In Journal of Algorithms, Volume 17, Issue 3, November 1994 447-474 ↑ Dávid Papp: The Goldberg–Rao Algorithm for the Maximum Flow Problem (PDF; 111 kB) (2006) ↑ Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva: Maximum Flow and Minimum-Cost Flow in Almost-Linear Time. arXiv 2022

Praktische Anwendungen

Diese letzte Verallgemeinerung ist motiviert durch Probleme bei der Verkabelung von VLSI-Chips, wo es aufwändig ist, in eine gewisse Nähe von gelegten Kabeln weitere zu setzen.

Die Flusstheorie hat sich historisch ausgehend von Problemen aus der Anwendung entwickelt. Allgemein ist man von der Situation ausgegangen, ein Fluid, also ein beliebig in Untergegenstände zerlegbaren Gegenstand, auf verschiedenen Wegen durch eine Welt räumlich zu verlagern – etwa elektrische Energie über ein Stromnetzwerk von einer Quelle an einen Bedarfsort, oder Daten durch ein Datennetzwerk von einem Sender zu einem Empfänger. Auch abstrakte Gegenstände wie „einander kennen“ kann man modellieren. Durch maximale Flüsse in einem sozialen Netzwerk kann man dann ein Maß dafür erhalten, wie stark zwei (Mengen von) Personen miteinander vernetzt sind.

Theoretische Anwendungen

Eine naheliegende und natürliche Anwendung hat die Flusstheorie bei der Transversalentheorie, die sich auf sehr natürliche Art und Weise in die Theorie der Flüsse einbetten lässt. Einen umfassenden Ansatz, das zu tun, hat Ford 1962 in einem Standardwerk formuliert.

Auch viele kombinatorische Probleme auf Graphen, wie bipartite Matchings, lassen sich leicht in ein geeignetes Flussproblem überführen (siehe Bild) und dort schnell lösen. Eine weitere Anwendung ist das effiziente Ermitteln der Knotenzusammenhangszahl, Kantenzusammenhangszahl oder Bogenzusammenhangszahl. Durch das Lemma von Tutte (nach William Thomas Tutte) werden zudem Anwendungen erweiterter Flusstheorie (sogenannten gruppenwertigen Flüssen) und Färbbarkeitsaussagen deutlich. Einige Vermutungen von ihm zur Existenz von k-Flüssen in planaren Graphen hätten starke theoretische Implikationen.