In diesem Kapitel werden wir Begriffe formal definieren und erste Erkenntnisse über Flussnetzwerke sammeln.
Flussnetzwerke
Hier ist nochmals ein (etwas kleineres) Flussnetzwerk:
Es stellt sich heraus, dass es oft bequemer ist, mit einer leicht veränderten Definition zu arbeiten: die Kapazitätsfunktion \(c\) ist einfach eine Funktion \(V \times V \rightarrow \R^+_0\), und die (gerichteten) Kanten des Netzwerkes sind einfach die Paare \((u,v)\), für die \(c(u,v) > 0\) gilt. Die Kapazitätsfunktion \(c\) kodiert also bereits den zugrundeliegenden Graphen. Hier ist also unsere alternative Definition:
Die Funktion $c$ kann man als Matrix in $\mathbb{R}^{n \times n}$ darstellen. Das obige Netzwerk ergäbe zum beispielsweise
wobei die leeren Matrixeinträge 0 darstellen. Wenn wir mathematisch-formal über Flussnetzwerke räsonnieren, dann ist vorzuziehen. Wenn wir aber Beispiele zeichnen oder einen Algorithmus implementieren wollen, dann ist sie womöglich ineffizient: da \(c : V \times V \rightarrow \R^+_0\) ist, müssen wir \(\Theta(n^2)\) Zahlen speichern; eventuell hat unser Netzwerk aber weitaus weniger Kanten; daher ist für Implementierungszwecke vorzuziehen, da wir hier mit einem Speicherplatz von \(\Theta(m)\) auskommen.
Flüsse in Flussnetzwerken
Hier zeigen wir noch einmal das obige Flussnetzwerk, nun aber mit violetten Zahlen, die einen Fluss beschreiben.
Wir sprechen auch manchmal von einem $s$-$t$-Fluss, um hervorzuheben, von wo nach wo es denn fließen soll. Dies ist ein Fluss, weil (1) an keiner Kante die Kapazität überschritten wird und (2) an keiner Kante Fluss verloren geht oder entsteht (außer an $s$ und $t$). Definieren wir nun Netzwerkflüsse formal. Ein Fluss \(f\) ist erst einmal eine Funktion \(f: V \times V \rightarrow \R\). Die Idee ist, dass \(f(u,v)\) angibt, wieviele Einheiten wir entlang der Kante \( (u,v) \) leiten. Dieser Betrag darf natürlich nicht die Kapazität überschreiten. Dies führt uns zu der ersten Bedingung: \(f(u,v) \leq c(u,v)\). Zweitens sollte \(f(u,v) \geq 0\) gelten, da negative Werte ja keinen Sinn machen. Diese zwei Bedingungen zusammen heißen nun auch, dass Fluss nur entlang einer Kante fließen darf: wenn es von \(u\) nach \(v\) keine Kante gibt, also \( (u,v) \not \in E\), dann ist ja \(c(u,v) = 0\) nach der zweiten Definition von Flussnetzwerken, und somit ist \(f(u,v) = 0\) der einzig mögliche Wert. Als dritte Bedingung kommt noch Flusserhalt hinzu: was in \(u\) hineinfließt, muss auch wieder herausfließen, also \( \sum_{v: (v,u) \in E} f(v,u) = \sum_{w: (u,w) \in E} f(u,w)\). Diese Bedingung gilt an allen Knoten außer \(s\) und \(t\); wir wollen ja, dass im Netto Resourcen nach \(t\) hineinfließen. Der Wert des Flusses ist dann die Gesamtmenge, die wir an $s$ nach draußen schicken: $\sum_{v \in V} f(s,v)$.
Schiefsymmetrie-Konvention. Wir können unser Leben mit einem kleinen Trick weitaus einfacher machen. Wir "verlangen" einfach, dass \(f (u,v) = -f(v,u)\) gilt, die Funktion \(f\) also schiefsymmetrisch (auf Englisch skew-symmetric) ist. Die Aussage wir leiten -2 Einheiten Erdgas von \(A\) nach \(B\) hieße also, dass wir 2 Einheiten von \(B\) nach \(A\) leiten. Diese Konvention ist zum Beispiel auch in elektrischen Netzwerken üblich (Kirchhoffsche Regeln). Mit dieser Konvention können wir Flusserhalt ganz kompakt schreiben: \(\sum_{v \in V} f(u,v) = 0\). Hier ist nun unsere vollständige Definition von Netzwerkflüssen:
- Kapazitätskonformität: \(f(u,v) \leq c(u,v)\) für alle \(u,v \in V\).
- Schiefsymmetrie: \(f(u,v) = -f(v,u)\) für alle \(u,v \in V\).
- Flusserhalt: \(\sum_{v \in V} f(u,v) = 0\) für alle \(u \in V \setminus \{s,t\}\).
Auch $f$ können wir als Matrix darstellen. Obiger Fluss wäre dann
Wenn wir die Matrixsichtweise wörtlich nehmen, dann können wir Schiefsymmetrie schreiben als $f^T = -f$, Kapazitätskonformität als $f \leq c$ (wobei wir $\leq$ bei Matrizen komponentenweise verstehen), und Flusserhalt so, dass sich in jeder Zeile die Einträge auf $0$ summieren (bis in der von $s$ und $t$). Aus der Schiefsymmetrie folgt auch sofort, dass \(f(u,u) = 0\) gilt, dass es also keinen Fluss von \(u\) zu sich selbst geben kann. Wenn Sie über Flüsse räsonnieren und sich über etwas nicht im Klaren sind, halten Sie sich an die axiomatische Definition von Flüssen. Dann wird schnell klar werden, ob etwas erlaubt ist oder nicht. Betrachten wir beispielsweise folgendes Netzwerk mit Fluss:
Dies ist definitiv ein "seltsamer" Fluss; es fließen drei Einheiten aus \(s\) über eine Kante heraus, eine Einheit über eine andere aber wieder hinein. Ähnliches spielt sich bei \(t\) ab; schließlich haben wir auch noch einen "Kreisverkehr" in der Mitte des Netzwerkes. Sie mögen dies als unrealistisch, verschwenderisch oder redundant tadeln. Es ist aber alles konform mit den Flussaxiomen, die wir oben ausgearbeitet haben, und daher sehen Sie hier in der Tat einen legalen Fluss. Der Wert dieses Flusses? Der ist 2. In der Summe \(\sum_{v} f(s,v)\) haben Sie eine 3, eine -1 und ganz viele Nullen.
Die zentrale algorithmische Fragestellung dieses Kapitels ist, wie man effizient einen Fluss von größtmöglichem Wert findet.
Zeigen Sie, dass wir solche "Knotenkapazitäten" mit unserer Definition von Flussnetzwerken und Netzwerkflüssen simulieren können, also keine modifizierten / verallgemeinerten Definitionen brauchen.
Wie würden Sie die Definition von Flussnetzwerken und Netzwerkflüssen anpassen, um diesen Fall behandeln zu können?
Zeigen Sie, dass unser Formalismus das "simulieren" kann; wir also nicht extra neue Definitionen von Netzwerken mit mehreren Terminals einführen müssen.
$s$-$t$-Schnitte
Hier ist obiges Netzwerk, aber so in zwei Teile geschnitten, dass $s$ und $t$ in getrennt werden:
Es gibt vier Kanten von $S$ nach $V \setminus S$, nämlich $(u,x)$, $(u,v)$, $(w,v)$ und $(w,z)$ (beachten Sie, dass $(v,s)$ nicht dazuzählt). Diese vier Kanten haben insgesamt eine Kapazität von $4+2+3+3 = 12$. Wenn wir sie entfernen, dann zerstören wir alle Pfade von $s$ nach $t$.
Definition Sei $(V,s,t,c)$ ein Flussnetzwerk. Ein $s$-$t$-Cut ist eine Menge $S \subseteq V$ mit $s \in S$ und $t \not \in V$. Die Kapazität von $S$ ist
\begin{align*} \capacity(S) := \sum_{u \in S} \sum_{v \in V \setminus S} c(u,v) \ . \end{align*}Schauen wir uns Fluss und Schnitt gemeinsam an:
Wenn wir die Kanten betrachten, die von $S$ nach $V \setminus S$ gehen, dann summieren sich die schwarzen Zahlen die $12 = \capacity(S)$ auf. Die violetten Zahlen sind höchstens die Zahlen, und somit summieren sie sich auf $3 + 0 + 3 + 2 = 8$ auf. Dies ist genau der Wert des Flusses. Jeder Schnitt gibt uns also eine obere Schranke dafür, wie groß den der Wert eines Flusses werden kann.
Theorem (Max-Flow-Min-Cut-Theorem, einfache Richtung). Sei $(V,s,t,c)$ ein Flussnetzwerk, $f$ ein $s$-$t$-Fluss und $S$ ein $s$-$t$-Cut. Dann gilt $\val(f) \leq \capacity(S)$.
Beweis. Wir beginnen mit einer Behauptung. Der Nettowert der Flusses, der von $S$ nach $V \setminus S$ fließt, ist gleich dem Wert des Flusses. Formal:
Behauptung. Es gilt
\begin{align} \val(f) = \sum_{u \in S} \sum_{v \in V \setminus S} f(u,v) \ . \label{value-and-sum-across-S} \end{align}Das Theorem folgt direkt aus der Behauptung. Nämlich:
\begin{align*} \val(f) & = \sum_{u \in S} \sum_{v \in V \setminus S} f(u,v) \tag{Behauptung} \\ & = \sum_{u \in S} \sum_{v \in V \setminus S} c(u,v) \tag{Kapazitätskonformität} \\ & = \capacity(S) \ . \end{align*}Beweis der Behauptung. Als erstes betrachten wir die Gesamtmenge, die "von $S$ nach $S$ fließt":
\begin{align} X := \sum_{u \in S} \sum_{v \in S} f(u,v) \ . \label{sum-inside-S} \end{align}Intuitiv sollte das $0$ sein: all das, was in (\ref{sum-inside-S}) gegeben wird, wird in (\ref{sum-inside-S}) genommen, also sollte $S$ danach weder "reicher" noch "ärmer" sein. Zeigen wir es formal, mithilfe der Schiefsymmetrie:
\begin{align*} X & = \sum_{u \in S} \sum_{v \in S} f(u,v) \\ & = \sum_{u \in S} \sum_{v \in S} -f(v,u) \tag{Schiefsymmetrie} \\ & = \sum_{x \in S} \sum_{y \in S} -f(y,x) \tag{umbenennen: $u \mapsto x, v \mapsto y$} \\ & = \sum_{v \in S} \sum_{u \in S} -f(u,v) \tag{umbenennen: $ y \mapsto u, x \mapsto v$} \\ & = \sum_{u \in S} \sum_{v \in S} -f(u,v) \tag{Summierung umordnen} \\ & = -X \ . \end{align*}Somit haben wir $X = -X$ gezeigt, also $X = 0$. Nun betrachten wir eine weitere Doppelsumme:
\begin{align*} Y := \sum_{u \in S} \sum_{v \in V} f(u,v) & = \sum_{u \in S} \left( \sum_{v \in S} f(u,v) + \sum_{v \in V \setminus S} f(u,v)\right) \tag{aufteilen}\\ & = \sum_{u \in S} \sum_{v \in S} f(u,v) + \sum_{u\in S} \sum_{v \in V \setminus S} f(u,v) \tag{umstellen} \\ & = 0 + \sum_{u\in S} \sum_{v \in V \setminus S} \ . \end{align*}$Y$ ist also gleich der rechten Seite in unserer Behauptung (\ref{value-and-sum-across-S}). Nun werten wir $Y$ nochmals aus, auf andere Weise:
\begin{align*} Y = \sum_{u \in S} \sum_{v \in V} f(u,v) & = \underbrace{\sum_{v \in V} f(s,v)}_{\textnormal{gleich } \val(f)} + \sum_{u \in S \setminus \{s\}} \underbrace{\left( \sum_{v \in V} f(u,v)\right)}_{\textnormal{gleich $0$}} \\ & = \val(f) \ . \end{align*}Wir haben also gezeigt, dass $Y$ gleich der linken Seite und gleich der rechten Seite von (\ref{value-and-sum-across-S}) ist. Somit gilt die Behauptung. \(\square\)
Wie oben gezeigt, folgt das Theorem aus der Behauptung.\(\square\)
$s$-$t$-Schnitte sind also eine Methode, um obere Schranken für den Wert von Flüssen zu zeigen. Ist diese Methode vollständig? Wenn also z.B. keinen Fluss von Wert größer als $\alpha$ gibt, können wir das dann immer mit einem Schnitt von Kapazität $\alpha$ zeigen? Wie sähe das im obigen Beispiel aus?
Hier sehen wir das gleiche Flussnetzwerk wie oben, allerdings mit einem anderen Fluss und einem anderen Schnitt. Alle Kanten von $S$ nach $V \setminus S$ sind "ausgelastet", und somit addieren sich über den Schnitt die schwarzen Zahlen zu $2 + 1 + 3 + 3 = 9 = \capacity(S)$ und die violetten Zahlen zu $2 + 1 + 3 + 3 = 9 = \val(f)$. Für dieses Netzwerk sind wir also überzeugt: der Maxfluss hat einen Wert von $9$. Besser kann es nicht gehen. Im nächsten Kapitel zeigen wir, dass das immer so ist.