Flüsse und Schnitte in Netzwerken

Flüsse und Schnitte in Netzwerken

Bei der Betrachtung von Flüssen in der Graphentheorie ist ein Netzwerk N=(V, E, s, t, c) ein gerichteter Graph (V,E) (ohne Mehrfachkanten) mit zwei ausgezeichneten Knoten s (Quelle) und t (Senke) aus V und einer Kapazitätsfunktion 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 Belegung f der einzelnen Kanten (x,y) im Netzwerk mit nicht negativen reellen Zahlen. Dabei müssen folgende Bedingungen erfüllt sein:

Keine Kante darf mit einem höheren Wert belegt sein, als ihre Kapazität (Zulässigkeit des Flusses)
Abgesehen von Quelle und Senke muss in jeden Knoten genau so viel hineinfließen wie herausfließen, d.h. die Summe der Belegungen der eingehenden Kanten entspricht der Summe der Belegungen der ausgehenden Kanten (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).

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. | |} {| | valign="top" | 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.

Das Restnetzwerk bezüglich eines zulässigen Flusses ist das Netzwerk, das alle Kanten des ursprünglichen Netzwerkes enthält, mit um den jeweiligen Flusswert verminderten Kantenkapazitäten (die dicken grauen Pfeile im Bild). Zusätzlich hat das Restnetzwerk noch genau dem Fluss entgegenlaufende Kanten (mit der entsprechenden Kantenkapazität, die dünnen grauen Pfeile). | |}

Algorithmen

Der Algorithmus von Ford und Fulkerson findet in einem Netzwerk einen maximalen Fluss, indem sukzessiv augmentierende Pfade gesucht und hinzugefügt werden. Der Algorithmus hat jedoch eine sehr schlechte Laufzeit (abhängig von den Kapazitäten) und terminiert für irrationale Kapazitäten mitunter nicht sowie konvergiert dabei nicht unbedingt gegen den richtigen Wert.

Wenn in jedem Augmentierungsschritt der jeweils kürzeste s-t-Pfad gewählt wird, verkürzt sich die Laufzeit auf O(|V||E|²).

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

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