Sieć przepływowa

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

Pojęcia

Przepływem w sieci G {\displaystyle G} nazywamy każdą funkcję f : V × V → R {\displaystyle f\colon V\times V\to R} spełniającą warunki:

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

Przepływ netto to wartość f ( u , v ) {\displaystyle f(u,v)} przepływu z wierzchołka u {\displaystyle u} do v . {\displaystyle v.}

Zagadnienia związane z sieciami przepływowymi