Flüsse und Schnitte in Netzwerken

Ein Netzwerk N=(V, E, s, t, c) ist in der Graphentheorie ein gerichteter Graph ohne Mehrfachkanten mit zwei ausgezeichneten Knoten s (Quelle) und t (Senke) aus V und einer Kapazitätsfunktion c, die jeder Kante (x,y) aus E eine Kapazität c(x,y) aus dem Bereich der nicht negativen reellen Zahlen zuweist.

Ein s-t-Fluss ist eine Funktion f, die von den Kanten im Netzwerk in die Menge der nicht negativen reellen Zahlen abbildet. Dabei müssen folgende Bedingungen erfüllt sein:

Der Fluss einer Kante ist maximal so groß wie die Kapazität auf der Kante erlaubt, d.h. es gilt $\forall (x,y)\in E:f((x,y))\leq c((x,y))$ .
Abgesehen von der Quelle s und der Senke t muss in jeden Knoten genau so viel hineinfließen, wie herausfließen, d.h. $\forall x\in V \setminus \{ s,t \} :\sum_{y\in N^+}f((x,y))=\sum_{y\in N^-}f((x,y))$ (Flusserhaltung)

Der Wert eines s-t-Flusses ist die Summe der eingehenden abzüglich der ausgehenden Belegungen der Senke s bzw. die ausgehenden Belegungen abzüglich der eingehenden Belegungen der Quelle t.

Eine Teilmenge der Knoten in einem Netzwerk, die s aber nicht t enthält, nennt man einen Schnitt. Die Kapazität eines Schnittes ist die Summe der Kapazitäten der aus dem Schnitt herausführenden Kanten. Der Wert eines maximalen Flusses im Netzwerk kann nicht größer als die Kapazität eines beliebigen und somit auch eines minimalen Schnittes sein (Max-Flow-Min-Cut Theorem).

Das Restnetzwerk (auch: Residualgraph) bezüglich eines zulässigen Flusses ist ein Graph, der alle Kanten des ursprünglichen Netzwerkes enthält, mit um den jeweiligen Flusswert verminderten Kantenkapazitäten.

Beispiel

Fluss-in-Graph-1.png Nebenstehendes Beispiel zeigt ein einfaches Netzwerk und einen möglichen Schnitt darin. Die Kapazität des Schnittes ist c(s,b) + c(a,b) + c(a,t) = 1 + 2 + 1 = 4.

Fluss-in-Graph-2.png Im zweiten Bild ist ein möglicher Fluss angegeben. Die Belegung steht zusammen mit der Kapazität an den einzelnen Kanten. Der Wert des Flusses ist 2.

Fluss-in-Graph-3.png Aus dem gegebenen Fluss ergibt sich das in Grau dargestellte Restnetzwerk. Auf dem Pfad s, a, b, t lässt sich der Fluss um den Wert 2 erhöhen.

Algorithmen

Der Algorithmus von Ford und Fulkerson findet in einem Netzwerk einen maximalen Fluss.

Mit dem Algorithmus von Dinic, der alle kürzesten s-t-Pfade in einem Schritt findet, ist eine Laufzeit von O(|V|³) möglich; wenn alle Kanten nur 0 oder 1 als Kapazitäten haben dürfen, verbessert sich die Laufzeit auf O(|V|^2/3|E|).

Anwendung

Flussalgorithmen lassen sich beispielsweise zur Berechnung der Knotenzusammenhangszahl und Kantenzusammenhangszahl verwenden.

Matching flow.png Ferner kann durch Flussalgorithmen eine maximale Paarung in einem bipartiten Graphen gefunden werden. In einem solchen Graph kann die Menge der Knoten $V$ in die disjunkten Teilmengen $A$ und $B$ eingeteilt werden. Erzeugt man nun ein Netzwerk $N$ , indem man eine Quelle $s$ hinzufügt und diese mit jedem Knoten aus $A$ verbindet und entsprechend alle Knoten aus $B$ mit einer Senke $t$ und ordnet man all diesen Kanten die Kapazität 1 sowie allen anderen Kanten aus dem originalen Graphen $G$ eine beliebige Kapazität $\geq1$ zu, dann entspricht ein maximaler Fluss in $N$ einer maximalen Paarung in $G$ und umgekehrt.

Siehe auch

Schnitt (Graphentheorie)

Literatur

L. R. Ford, D. R. Fulkerson: Flows in Networks, 1962

Weblinks

http://dsor.upb.de/phpvorms/index.php?subpage=content&unit=OR_21_FFvsDinic&style=vormsPlus&chapter=0