Sieć przepływowa

Siecią przepływową $G(V,E)$ nazywamy graf skierowany, w którym każda krawędź $(u,v)$ należąca do zbioru krawędzi $E$ ma nieujemną przepustowość $c(u,v)\geqslant 0$. W sieci wyrózniamy dwa wierzchołki: źródło $s$ i ujście $t$.

Pojęcia

Przepływem w sieci $G$ nazywamy każdą funkcję $f: V \times V \to R$ spełniającą warunki:

• warunek przepustowości: dla wszystkich krawędzi $(u,v) \in E$ zachodzi $f(u,v)\leqslant c(u,v)$.
• warunek skośnej symetryczności: dla wszystkich krawędzi $(u,v)\in E$ zachodzi $f(u,v)= -f(v,u)$.
• warunek zachowania przepływu: dla każdego $u \in V \setminus \{ s,t \}$ zachodzi $\sum_{v\in V} f(v,u) = \sum_{v\in V} f(u,v)$.

Przepływ netto wartość $f(u,v)$ przepływu z wierzchołka u do v.

Zagadnienia związane z sieciami przepływowymi

• Problem maksymalnego przepływu