Sieć przepływowa

Sieć przepływowa $G(V,E)$ – graf skierowany, w którym każda krawędź $(u,v)$ należąca do zbioru krawędzi $E$ ma nieujemną przepustowość $c(u,v)⩾0.$ W sieci wyróżniamy 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)⩽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 to wartość $f(u,v)$ przepływu z wierzchołka $u$ do $v.$

Zagadnienia związane z sieciami przepływowymi

• problem maksymalnego przepływu