Sieć przepływowa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Sieć przepływowa graf skierowany, w którym każda krawędź należąca do zbioru krawędzi ma nieujemną przepustowość . W sieci wyróżniamy dwa wierzchołki: źródło i ujście .

Pojęcia[edytuj]

Przepływem w sieci nazywamy każdą funkcję spełniającą warunki:

  • warunek przepustowości: dla wszystkich krawędzi zachodzi .
  • warunek skośnej symetryczności: dla wszystkich krawędzi zachodzi .
  • warunek zachowania przepływu: dla każdego zachodzi .

Przepływ netto wartość przepływu z wierzchołka u do v.

Zagadnienia związane z sieciami przepływowymi[edytuj]