Otwórz menu główne

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ęciaEdytuj

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ływowymiEdytuj