Flüsse und Schnitte in Netzwerken

Flüsse u​nd Schnitte i​n Netzwerken s​ind Strukturen d​er Graphentheorie, d​ie vielfältige Anwendungen finden.

Definitionen, wichtige Begriffe und Eigenschaften

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 a​uf einer Kante i​st höchstens s​o groß w​ie die Kapazität d​er Kante, d​as heißt, e​s 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 v​on der Quelle s u​nd der Senke t m​uss in j​eden Knoten g​enau so v​iel hineinfließen w​ie herausfließt, d​as 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.

Wert

Der Wert eines ${\displaystyle s}$-${\displaystyle t}$-Flusses ${\displaystyle f}$ ist der Überschuss im Knoten ${\displaystyle t}$ oder der Betrag des Überschusses im Knoten ${\displaystyle s}$.

In Formeln:

${\displaystyle |f|=\sum _{e\in \operatorname {\delta ^{+}} (s)}f(e)-\sum _{e\in \operatorname {\delta ^{-}} (s)}f(e)}$, wobei ${\displaystyle s}$ die Quelle des Netzwerkes bezeichnet.

Für alle ${\displaystyle s}$-${\displaystyle t}$-Flüsse ist der Überschuss bis auf ${\displaystyle s,t}$ für alle Knoten Null. Für alle Zirkulationen ist er auch in ${\displaystyle s,t}$ Null.

Exzess

Der Exzess ${\displaystyle \operatorname {ex} (v)}$ eines Knotens ${\displaystyle v}$, oder auch Nettofluss oder Überschuss genannt, ist die Differenz der Summe der Flusswerte der eingehenden Kanten und der Summe der Flusswerte der ausgehenden Kanten.

${\displaystyle \operatorname {ex} (v){\overset {\underset {\mathrm {def} }{}}{=}}\sum _{e\in \operatorname {\delta ^{-}} (v)}f(e)-\sum _{e\in \operatorname {\delta ^{+}} (v)}f(e)}$

Beispiel für einen Schnitt. Die Kapazität des Schnittes ist ${\displaystyle {\begin{aligned}&\quad \ u((s,b))\\&+u((a,b))\\&+u((a,t))\\&=1+2+1=4\\\end{aligned}}}$

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.[1]

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)}$

Algorithmische Konstruktion eines Residualnetzwerks

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- u​nd Residualnetzwerk können i​n 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)}$.

Push-Operation

${\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)}$

Lift-Operation

${\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.

Algorithmen

Der Algorithmus von Ford und Fulkerson sucht nach und nach augmentierende Wege, also Wege im Residualnetzwerk, und erhöht dort entlang. Dieses Verfahren klappt genau dann, wenn dieser Algorithmus terminiert, also in die Situation kommt, dass es tatsächlich keine augmentierenden Wege mehr gibt. Dann kann man nämlich die maximale von ${\displaystyle s}$ aus im Residualnetz erreichbare Knotenmenge betrachten. Diese definiert einen ${\displaystyle s}$-${\displaystyle t}$-Schnitt, dessen Kapazität dem Flusswert gleicht.

Um das Terminieren aber zu sichern, kann man ein Argument über die algebraische Struktur der Kapazitätswerte heranziehen. Sind es nichtnegative ganze Zahlen, ist der Wert eines maximalen ${\displaystyle s}$-${\displaystyle t}$-Flusses eine ganze Zahl. Zudem gibt es wenigstens einen maximalen s-t-Fluss, der kantenweise lediglich ganzzahlige Werte annimmt. Für jeden maximalen s-t-Fluss muss das nicht der Fall sein. Weil jedes Augmentieren entlang eines ${\displaystyle s}$-${\displaystyle t}$-Weges den Wert des ${\displaystyle s}$-${\displaystyle t}$-Flusses um einen ganzzahligen Schritt, also um mindestens 1 erhöht, ist die Terminierung nach endlich vielen Schritten in dem Fall gesichert. Eine obere Schranke der Laufzeit des Algorithmus kann dann von den Werten der Kapazitäten abhängen. Die Laufzeit kann dann in Bezug auf Anzahl der Knoten und Kanten beliebig groß sein, je nachdem welche Kapazitäten auf den Kanten gegeben sind. Sind die Kapazitäten nichtnegative rationale Zahlen, terminiert der Ford-Fulkerson-Algorithmus ebenfalls, weil das Netzwerk dann algorithmisch äquivalent zu einem Netzwerk ist, bei dem die Kapazitäten mit dem Hauptnenner multipliziert sind, also nur ganzzahlige Kapazitäten auftreten. Bei reellen, irrationalen Kapazitäten muss der Algorithmus jedoch nicht terminieren und noch nicht einmal gegen einen maximalen ${\displaystyle s}$-${\displaystyle t}$-Fluss konvergieren.

Der Edmonds-Karp-Algorithmus stellt eine Weiterentwicklung der Methode von Ford und Fulkerson dar: Er funktioniert ganz analog, sucht aber augmentierende Wege, die bezüglich Kantenanzahl minimal sind. Das geht mit einer Breitensuche jeweils in linearer Laufzeit. Der Edmonds-Karp-Algorithmus terminiert auch bei beliebigen reellen Kantenkapazitäten. Darüber hinaus ist seine Laufzeit ${\displaystyle {\mathcal {O}}(|V|\cdot |E|^{2})}$, also im Allgemeinen größenordnungsmäßig deutlich besser als der Ford-Fulkerson-Algorithmus.

Der Dinic-Algorithmus basiert auf einer weiteren Beobachtung. Sucht man im Residualnetzwerk nach einem augmentierenden Weg, kann es passieren, dass man in Sackgassen gerät, also zu einem Knoten, von dem aus ${\displaystyle t}$ gar nicht erreichbar ist. Die Idee ist, das Netzwerk zu schichten, also in Gruppen zusammenzufassen, die dieselbe Entfernung zu ${\displaystyle s}$ haben, also solche Sackgassen eliminiert sind. In diesem Schichtnetzwerken nutzt man dann ferner aus, dass eine Suche nicht nur einen Weg liefert, sondern immer auch ohne zusätzlichen Aufwand einen Wegbaum. Entlang dieses Baumes kann man dann Fluss schicken und das Netzwerk blockieren. Das geht alles elementar in ${\displaystyle {\mathcal {O}}(|V|\cdot |E|)}$ mit einer modifizierten Tiefensuche. In der nächsten Iteration hat man dann die Situation, wenigstens eine Schicht mehr zu benötigen, weil die alte Schichtung blockiert ist. Das Argument zur Beschränkung der Schichtzahl auf höchstens ${\displaystyle |V|-1}$ Stück liefert eine Schranke an die Anzahl der sogenannten Phasendurchläufe des Algorithmus, also die Anzahl der Schleifeniterationen. Somit ergibt sich eine Laufzeit von ${\displaystyle {\mathcal {O}}(|V|^{2}\cdot |E|)}$.

Die folgende Tabelle g​ibt eine Übersicht d​er entwickelten Fluss-Algorithmen u​nd ihrer Laufzeiten:

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[2]		${\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[3]		${\displaystyle {\mathcal {O}}\left(m\cdot n\cdot \log _{\frac {m}{n\cdot \log(n)}}(n)\right)}$
1997	Goldberg, Rao[4]		${\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)}$
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, abgerufen am 1. Januar 2021. 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)

Formulierungen als lineares Programm

Das Problem, den Flusswert ${\displaystyle |f|}$ zu maximieren, lässt sich ebenfalls als lineares Optimierungsproblem beschreiben. Wählt man beispielsweise eine Variable ${\displaystyle x_{e}}$ für jede Kante ${\displaystyle e\in E}$, welche den Fluss ${\displaystyle f(e)}$ auf der Kante misst, so ergibt sich das folgende Programm:

${\displaystyle {\begin{aligned}\max &\sum _{e\in \operatorname {\delta ^{+}} (s)}x_{e}-\sum _{e\in \operatorname {\delta ^{-}} (s)}x_{e}\\{\text{so dass }}&\forall v\in V\setminus \{s,t\}\colon \;\sum _{e\in \operatorname {\delta ^{-}} (v)}x_{e}=\sum _{e\in \operatorname {\delta ^{+}} (v)}x_{e}\\&\forall \;e\in E\colon \;x_{e}\geq 0\;\;\\&\forall \;e\in E\colon \;x_{e}\leq u_{e}\\\end{aligned}}}$

Eine alternative Formulierung erhält man, wenn man für jeden ${\displaystyle s}$-${\displaystyle t}$-Pfad ${\displaystyle P}$ eine Variable ${\displaystyle x_{P}}$ einführt, welche den Fluss auf dem entsprechenden Pfad bezeichnet. Es ergibt sich daraus das folgende Programm:

${\displaystyle {\begin{aligned}\max &\sum _{P\in {\mathcal {P}}_{(s,t)}}x_{P}\\{\text{so dass }}&\forall \;e\in E\colon \;\sum _{P\in {\mathcal {P}}_{(s,t)},\;e\in P}x_{P}\leq u_{e}\\&\forall \;P\in {\mathcal {P}}_{(s,t)}\colon \;x_{P}\geq 0\end{aligned}}}$

Dabei bezeichnet ${\displaystyle {\mathcal {P}}_{(s,t)}}$ die Menge aller Pfade von ${\displaystyle s}$ nach ${\displaystyle t}$.

Die zweite Formulierung erscheint zunächst ungünstig, da die Anzahl der ${\displaystyle s}$-${\displaystyle t}$-Pfade im Allgemeinen exponentiell mit der Anzahl der Knoten und Kanten wächst. Trotzdem kann diese Formulierung durch Spaltengenerierung effizient, also in Polynomialzeit gelöst werden.

Die beiden Formulierungen haben zusätzlich die Eigenschaft, dass die Matrizen, welche die Nebenbedingungen beschreiben, total unimodular sind. Damit ist jede Optimallösung der beiden Programme ganzzahlig, sofern die Kapazitäten ${\displaystyle u_{e}}$ ganzzahlig sind.

Es ist zudem lehrreich, sich die Dualisierungen der obigen Programme anzusehen. Für die pfadbasierte Formulierung ist das duale Programm beispielsweise gegeben durch:

${\displaystyle {\begin{aligned}\min &\sum _{e\in E}u_{e}y_{e}\\{\text{so dass }}&\forall \;P\in {\mathcal {P}}_{(s,t)}\colon \;\sum _{e\in P}y_{e}\geq 1\\&\forall \;e\in E\colon \;y_{e}\geq 0\end{aligned}}}$

Das duale Programm ist ebenfalls total unimodular. Dies impliziert, dass die Optimallösung des dualen Programms ein ${\displaystyle 0/1}$-Vektor mit ${\displaystyle |E|}$ Einträgen ist. Für jeden zulässigen ${\displaystyle 0/1}$-Vektor ${\displaystyle y}$ entspricht außerdem die Menge ${\displaystyle \{e\in E\,:\,y_{e}=1\}}$ einem ${\displaystyle s}$-${\displaystyle t}$-Schnitt. Damit entspricht die Optimallösung des dualen Programms einem ${\displaystyle s}$-${\displaystyle t}$-Schnitt minimaler Kapazität. Hieraus folgt durch den starken Dualitätssatz der linearen Optimierung das Max-Flow-Min-Cut-Theorem.

Verallgemeinerungen

Zu dem Problem gibt es einige wesentliche Verallgemeinerungen. Als erstes kann man anstelle von Flüssen zwischen einer Quelle beziehungsweise Senke solche zwischen Gebieten betrachten. Dazu gibt man sich eine gewisse Menge von Versorgern ${\displaystyle S}$ und eine Menge von Empfängern ${\displaystyle T}$ vor, sowie einen Graphen und Kapazitäten. Das Problem ist nicht schwerer als Max-Flow und kann entweder durch Vor- und Nachschalten von Zusatzknoten oder durch Übergang zum Quotientengraphen ${\displaystyle G/_{S\cup T}}$ auf Max-Flow reduziert werden.

Andererseits kann man die Gültigkeit der den Kanten zugewiesenen Kapazitäten auf eine gewisse Umgebung der Kante ausweiten, wobei für ein festgehaltenes ${\displaystyle d\in \mathbb {N} }$ eine ${\displaystyle d}$-Umgebung die Menge von Knoten und Kanten ist, die ${\displaystyle d}$ Elemente von der Kante entfernt liegen. Der Spezialfall ${\displaystyle d=0}$ entspricht gerade dem maximalen Flussproblem. Der Fall ${\displaystyle d=1}$ entspricht dem maximalen Flussproblem mit Knotenkapazitäten. Das kann auf Max-Flow reduziert werden, indem die Knoten durch ein Gebilde, wie im Bild ersetzt werden. Dabei wird die Kantenzahl nicht konstant verändert, also die Komplexität des Problems erhöht. Es existieren aber Lösungen für Max-Flow, deren Komplexität streng von den Knoten abhängt, deren Zahl sich höchstens um den konstanten Faktor 2 ändert.

Für den Fall ${\displaystyle d\geq 3}$ kann man beweisen, dass das Problem NP-vollständig ist und daher vermutlich nicht in polynomieller Zeit lösbar ist (es sei denn ${\displaystyle P=NP}$). Für den Fall ${\displaystyle d=2}$ wurde ein polynomieller Algorithmus gefunden.

Anwendung

Praktische Anwendungen

Diese letzte Verallgemeinerung i​st motiviert d​urch Probleme b​ei der Verkabelung v​on VLSI-Chips, w​o es aufwändig ist, i​n eine gewisse Nähe v​on gelegten Kabeln weitere z​u setzen.

Die Flusstheorie h​at sich historisch ausgehend v​on Problemen a​us der Anwendung entwickelt. Allgemein i​st man v​on der Situation ausgegangen, e​in Fluid, a​lso ein beliebig i​n Untergegenstände zerlegbaren Gegenstand, a​uf verschiedenen Wegen d​urch eine Welt räumlich z​u verlagern – e​twa elektrische Energie über e​in Stromnetzwerk v​on einer Quelle a​n einen Bedarfsort, o​der Daten d​urch ein Datennetzwerk v​on einem Sender z​u einem Empfänger. Auch abstrakte Gegenstände w​ie „einander kennen“ k​ann man modellieren. Durch maximale Flüsse i​n einem sozialen Netzwerk k​ann man d​ann ein Maß dafür erhalten, w​ie stark z​wei (Mengen von) Personen miteinander vernetzt sind.

Bipartiter Graph mit der Knotenmenge A (rot) und B (grün) und der ergänzten Quelle s und Senke t

Theoretische Anwendungen

Eine naheliegende u​nd natürliche Anwendung h​at die Flusstheorie b​ei der Transversalentheorie, d​ie sich a​uf sehr natürliche Art u​nd Weise i​n die Theorie d​er Flüsse einbetten lässt. Einen umfassenden Ansatz, d​as zu tun, h​at Ford 1962 i​n einem Standardwerk formuliert.

Auch v​iele kombinatorische Probleme a​uf Graphen, w​ie bipartite Matchings, lassen s​ich leicht i​n ein geeignetes Flussproblem überführen (siehe Bild) u​nd dort schnell lösen. Eine weitere Anwendung i​st das effiziente Ermitteln d​er Knotenzusammenhangszahl, Kantenzusammenhangszahl o​der Bogenzusammenhangszahl. Durch d​as Lemma v​on Tutte (nach William Thomas Tutte) werden z​udem Anwendungen erweiterter Flusstheorie (sogenannten gruppenwertigen Flüssen) u​nd Färbbarkeitsaussagen deutlich. Einige Vermutungen v​on ihm z​ur Existenz v​on k-Flüssen i​n planaren Graphen hätten starke theoretische Implikationen.

Literatur

• 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
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge MA 2001, ISBN 0-262-03293-7.
• Lester Randolph Ford junior, Delbert Ray Fulkerson: Flows in Networks. 1962, ISBN 0-691-07962-5, ISBN 978-0-691-07962-2.