Sieć przepływowa
Z Wikipedii
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) > = 0. W sieci wyrózniamy dwa wierzchołki: źródło s i ujście t.
[edytuj] Pojęcia
Przepływem w sieci G nazywamy każdą funkcję spełniającą warunki:
- warunek przepustowości: dla wszystkich krawędzi zachodzi f(u,v) < = c(u,v).
- warunek skośnej symetryczności: dla wszystkich krawędzi zachodzi f(u,v) = − f(v,u).
- warunek zachowania przepływu: dla każdego zachodzi .
Przepływ netto wartość f(u,v) przepływu z wierzchołka u do v.
[edytuj] Zagadnienia związane z sieciami przepływowymi