Maximale Flüsse

Als Maximaler Fluss wird ein Fluss in einem Netzwerk bezeichent, mit dem die größe Menge an Einheiten von der Quelle zur Senke fließen. Die Suche nach einem maximalen Fluss ist ein weit verbreitetes Problem, dass z.b. bei der Bestimmung von Lieferkapazitäten, Produktionskapazitäten oder Netzkapazitäten.

Optimalitätskriterium

Das Optimalitätskriterium gibt uns eine Eigenschaft mit der wir feststellen können, ob der gegebene Fluss zu einem Netzwerk maximal ist.

Satz

Sei G=(V,E,c)G = (V,E,c) ein Netzwerk und ff ein zulässiger Fluss. Dann gilt:
ff ist maximal gdw. kein ff-augmentierender Weg im Residualgraphen GfG_f existiert.

Ford-Fulkerson Methode

Die Ford-Fulkerson Methode findet einen maximalen Fluss zu einem gegebenen Netzwerk. Dabei ist die Grundidee solange ff-augmentierende Wege zu suchen, und den Fluss an diesen entsprechend zu augmentieren, bis keine ff-augmentierenden Wege mehr im zugehörigen Residualgraphen existieren. Dabei speziefiziert Ford-Fulkerson nicht, nach welchem Prinzip ff-augmentierenden Wege gesucht werden, weswegen es verschiedene implementierungen der Methode gibt. Eine Implementierung ist z.b. der Edmonds-Karp-Algorithmus, in dem die suche nach ff-augmentierenden Wegen als Breitensuche implementiert ist.

Im folgenden wird die Ford-Fulkerson Methode vorgestellt.

Eingabe:

  • Netzwerk G=(V,E,c)G=(V,E,c) mit Quelle ss und Senke tt

Ausgabe:

  • Maximaler Fluss ff in GG
$G \leftarrow (V,E,c)$
$\mathbf{for} \text{ jede Kante } (a,b) \in E~\mathbf{do}$
    
$f((a,b)) = 0$
$\mathbf{while}~ \text{es existiert ein $f$-augmentierender Weg $p$ in } G_f ~\mathbf{do}$
    
$c_f(p) = \min\{c_f(a,b) : (a,b) \in p\}$
    
$\mathbf{for}~ \text{jede Kante } (a,b) \in p~ \mathbf{do}$
        
$\text{augmentiere $f$ entlang $(a,b)$ um $c_f(p)$}$
    
$\text{aktualisiere } G_f$
$\mathbf{return}~f$

In Worten geht die Methode folgendermaßen vor: Zuerst wird für jede Kante im Netzwerk GG der Fluss mit 00 initialisiert (2,3). Anschleißend wird, solange im zu GG gehörenden Residualgraphen ein ff-augmentierender Weg existiert (4), die Bottleneck-Kapazität des Wegs bestimmt (5) und der Fuss im Netzwerk endlang des Weges um die Bottleneck-Kapazität augmentiert (6,7). Nachdem der Fluss augmentiert wurde, wird der Residualgraph an den neuen Fluss angepasst (8). Die Methode enden, wenn im Residualgraphen kein ff-augmentierender Weg mehr existiert.cor2013

Beispiel

Zum besseren Verständnis wenden wir die Ford-Fulkerson Methode jetzt einmal auf ein Beispiel an. Dabei wird im Pseudocode immer die Zeile hervorgehoben, die aktuel ausgeführt wird. Direkt unter dem Pseudocode ist das Netzwerk GG, für dass der maximale Fluss bestimmt werden soll und da drunter wird der zu GG gehörende Residualgraph GfG_f gezeigt. Der ff-augmentierende Weg wird in lachs in den Graphen hervorgehoben und die augmentierten Kanten in grün.

  • $G \leftarrow (V,E,c)$
    $\mathbf{for} \text{ jede Kante } (a,b) \in E~\mathbf{do}$
        
    $f((a,b)) = 0$
    $\mathbf{while}~ \text{es existiert ein $f$-augmentierender Weg $p$ in } G_f ~\mathbf{do}$
        
    $c_f(p) = \min\{c_f(a,b) : (a,b) \in p\}$
        
    $\mathbf{for}~ \text{jede Kante } (a,b) \in p~ \mathbf{do}$
            
    $\text{augmentiere $f$ entlang $(a,b)$ um $c_f(p)$}$
        
    $\text{aktualisiere } G_f$
    $\mathbf{return}~f$
    Netzwerk GG:
    Residualgraph GfG_f:
  • $G \leftarrow (V,E,c)$
    $\mathbf{for} \text{ jede Kante } (a,b) \in E~\mathbf{do}$
        $f((a,b)) = 0$
    $\mathbf{while}~ \text{es existiert ein $f$-augmentierender Weg $p$ in } G_f ~\mathbf{do}$
        
    $c_f(p) = \min\{c_f(a,b) : (a,b) \in p\}$
        
    $\mathbf{for}~ \text{jede Kante } (a,b) \in p~ \mathbf{do}$
            
    $\text{augmentiere $f$ entlang $(a,b)$ um $c_f(p)$}$
        
    $\text{aktualisiere } G_f$
    $\mathbf{return}~f$
    Netzwerk GG:
    Residualgraph GfG_f:

Verbindung zu Matchings

In diesem Abschnitt wollen wir auf die Verbindung zwischen Matchings und Netzwerken eingehen. Genauer werden wir Zeigen, dass wir ein maximales Matching auf einem Graphen GG finden können, in dem wir einen Maximalen Fluss in einem aus GG konstruierten Netzwerk GNG_N finden.

Konstruktion des Netzwerks

Ein Netzwerk GNG_N kann in drei Schritten aus einem bipartiten Graphen G=(L∪R,E)G=(L \cup R, E) konstruiert werden:

  1. Alle Kanten aus GG werden zu gerichteten Kanten von LL nach RR im Netzwerk.
  2. Füge GG eine Quelle ss und eine Senke tt hinzu. Dazu füge Kanten von ss zu allen Knoten in LL und Kanten von allen Knoten in RR zu tt hinzu.
  3. Gib allen Kanten im Netzwerk eine Kapazität von ein.

Mit diesen Schritten erhalten wir für einen bipartiten Graphen G=(L∪R,E)G=(L \cup R, E) das Netzwerk:

GN=(L∪R∪{s,t},{(a,b)∣{a,b}∈E}∪{(s,b)∣b∈L}∪{(a,t)∣a∈R}=EN,c)mit c:=EN→{1},c(e)=1G_N = (L \cup R \cup \{s,t\}, \{(a,b) | \{a,b\} \in E\} \cup \{(s,b) | b \in L\} \cup \{(a,t) | a \in R \} = E_N, c) \\ \text{mit } c := E_N \rightarrow \{1\}, c(e) = 1

Da wir jetzt wissen, wie wir aus einem bipartiten Graphen ein Netzwerk konstruieren, müssen wir jetzt noch folgendens Zeigen:

Satz

Ein Graph GG hat ein maximales Matching der Grüße kk gdw. Das Netzwerk GNG_N hat einen maximalen Fluss mit Flusswert kk.

  1. [COR2013]: Corman, T. H., Leiserson, C. E., Rivest, R., Algorithmen - Eine Einführung, De Gruyter Oldenbourg, 2013.↩