prev up inhalt next


8.1 Fluß

Ein Fluß ist dann eine Funktion f : E$\to$$
\mathbb {R}
$ mit:
1.
0$\le$f ((i,j))$\le$c(i,j)
2.
für alle i $\in$ V$\backslash${s,t} gilt: $\sum\limits_{a\in V(i)}^{}$f (a,i) = $\sum\limits_{b\in N(i)}^{}$f (i,b) , wobei V(i)[N(i)] alle Vorgänger [Nachfolger] von i im Graphen G sind.
Gesucht ist nun der maximale Gesamtfluß F = $\sum\limits_{b\in N(s)}^{}$f (s,b) = $\sum\limits_{a\in V(t)}^{}$f (a,t) .


prev up inhalt next