Flüsse und Schnitte in Netzwerken

Inhaltsverzeichnis
1 Definitionen
2 Beispiel
3 Algorithmen
4 Literatur

Definitionen

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:

  1. 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)).
  2. 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 Netzwerk, das alle Kanten des ursprünglichen Netzwerkes enthält, mit um den jeweiligen Flusswert verminderten Kantenkapazitäten. Zusätzlich hat das Restnetzwerk noch genau dem Fluss entgegenlaufende Kanten.

Es fehlt an dieser Stelle eine Erklärung zu augmentierender Pfad

Beispiel

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.

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.

Bild:Fluss-in-Graph-1.pngBild:Fluss-in-Graph-2.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. Bild:Fluss-in-Graph-3.png

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|3) 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|).

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

Literatur

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

See also: Flüsse und Schnitte in Netzwerken, 1962, Algorithmus von Ford und Fulkerson, Gerichteter Graph, Graph ohne Mehrfachkanten, Graphentheorie, Kantenzusammenhangszahl, Knotenzusammenhangszahl, Reelle Zahlen