Flüsse und Schnitte in Netzwerken

Inhaltsverzeichnis

1 Definitionen 2 Beispiel 3 Algorithmen 4 Literatur

Definitionen

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 Dabei müssen folgende Bedingungen erfüllt sein:

1. Keine Kante darf mit einem höheren Wert sein als ihre Kapazität ( Zulässigkeit des Flusses )
2. Abgesehen von Quelle und Senke muss in Knoten genau so viel hineinfließen wie herausfließen die Summe der Belegungen der eingehenden Kanten der Summe der Belegungen der ausgehenden Kanten Flusserhaltung )

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

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

Es fehlt an dieser Stelle eine Erklärung augmentierender Pfad

Beispiel

Nebenstehendes Beispiel zeigt ein einfaches Netzwerk einen möglichen Schnitt darin. Die Kapazität des ist c(s b) + c(a b) + c(a = 1 + 2 + 1 = . Im zweiten Bild ist ein möglicher angegeben. Die Belegung steht zusammen mit der an den einzelnen Kanten. Der Wert des ist 2.

Aus dem gegebenen Fluss ergibt sich in Grau dargestellte Restnetzwerk . Auf dem Pfad s a b t lässt sich der Fluss um den 2 erhöhen. Das Restnetzwerk bezüglich eines zulässigen Flusses das Netzwerk das alle Kanten des ursprünglichen enthält mit um den jeweiligen Flusswert verminderten (die dicken grauen Pfeile im Bild). Zusätzlich das Restnetzwerk noch genau dem Fluss entgegenlaufende (mit der entsprechenden Kantenkapazität die dünnen grauen

Algorithmen

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

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

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

Flussalgorithmen lassen sich beispielsweise zur Berechnung Knotenzusammenhangszahl und Kantenzusammenhangszahl verwenden.

Literatur

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

Bücher zum Thema Flüsse und Schnitte in Netzwerken

Dieser Artikel von Wikipedia unterliegt der GNU FDL.