Problém toku v síti - Network flow problem

V kombinatorické optimalizace , problémy toku v síti jsou třídou výpočetních problémů, ve kterém je vstupní je síťový proud (graf s číselnými kapacit na jeho okraje), a cílem je zkonstruovat toku , číselné hodnoty na každé hraně, které respektují kapacitu omezení a která mají příchozí tok rovný odchozímu toku na všech vrcholech s výjimkou určitých určených terminálů.

Mezi konkrétní typy problémů s tokem v síti patří:

  • Problém maximálního průtoku , ve kterém je cílem maximalizovat celkové množství toku ven ze zdrojových terminálů a do terminálů jímky
  • Problém toku minimální náklady , ve kterých jsou okraje mají nákladů, jakož i kapacity a cílem je, aby se dosáhlo daného množství proudu (nebo maximální průtok), který má minimální možné náklady
  • Problém s multikomoditním tokem , ve kterém je třeba vytvořit více toků pro různé komodity, jejichž celkový objem toků respektuje kapacity
  • Tok nikde nula , typ toku studovaný v kombinatorice, ve kterém jsou množství toku omezena na konečnou množinu nenulových hodnot

Fordova-Fulkersonova věta odpovídá hodnotu maximálního průtoku na hodnoty minimálního řezu , oddíl z vrcholů sítě toku, který minimalizuje celková kapacita hran překračujících z jedné strany přepážky na druhý. Přibližné věty o maximálním průtoku a minimálním řezu poskytují rozšíření tohoto výsledku k problémům s tokem více komodit. Gömöry-Hu strom z neřízené sítě toku poskytuje stručný zastoupení všech minimálních řezů mezi různými páry koncových vrcholů.

Algoritmy pro konstrukci toků zahrnují

Jinak lze problém formulovat jako konvenčnější lineární program nebo podobný a vyřešit jej pomocí univerzálního řešení optimalizace.