Sieć przepływowa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]