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 to wartość   przepływu z wierzchołka   do  

Zagadnienia związane z sieciami przepływowymi

edytuj