Problém toku sítě - Network flow problem

v kombinatorická optimalizace, problémy s tokem v síti jsou třídou výpočetních problémů, ve kterých je vstup a toková síť (graf s numerickými kapacitami na okrajích) a cílem je sestrojit a tok, číselné hodnoty na každé hraně, které respektují kapacitní omezení a které mají příchozí tok stejný jako odchozí tok na všech vrcholech s výjimkou určitých určených terminálů.

Mezi konkrétní typy problémů se síťovým tokem patří:

  • The problém s maximálním průtokem, ve kterém je cílem maximalizovat celkové množství toku ven ze zdrojových terminálů a do terminálů jímky
  • The problém toku minimálních nákladů, ve kterém mají hrany náklady i kapacity a cílem je dosáhnout daného množství toku (nebo maximálního toku), které má minimální možné náklady
  • The problém multikomoditního toku, ve kterém je třeba zkonstruovat více toků pro různé komodity, jejichž celkový objem toků respektuje kapacity
  • Nikde nulový tok, typ toku studovaného v kombinatorice, ve kterém jsou množství toku omezena na konečnou množinu nenulových hodnot

The věta o maximálním toku o minimálním řezu odpovídá hodnotě maximálního průtoku hodnotě a minimální řez, oddíl vrcholů tokové sítě, který minimalizuje celkovou kapacitu hran přecházejících z jedné strany oddílu na druhou. Přibližné věty o maximálním průtoku min poskytnout rozšíření tohoto výsledku k problémům s multikomoditním tokem. The Gomory – Hu strom sítě s nepřímým tokem poskytuje stručné znázornění všech minimálních řezů mezi různými páry vrcholů terminálů.

Algoritmy pro konstrukci toků patří