flytnettverk
Flytnettverk er et rettet graf som brukes til å modellere flyt av en ressurs gjennom et system. Noder representerer punkter eller steder, og kanter (arcs) har kapasitet som angir maksimal flyt gjennom kanten i en gitt retning. Et startpunkt kalles kilde (s) og et sluttpunkt kalles sluk (t).
En flyt f tilordner hver kant e en verdi f(e) mellom 0 og c(e), der c(e) er
Maksimal flyt-problemet består i å finne en flyt med maksimal verdi under kapasitet- og balansebetingelsene. Ifølge
Algoritmer som ofte brukes er Ford-Fulkerson-metoden, Edmonds-Karp-varianten (BFS-basert augmenting paths) og moderne tilnærminger som Dinics algoritme
Residualgrafen viser gjenstående kapasitet på hver kant og hjelper til med å identifisere nye augmenterende stier.
Anvendelser inkluderer nettverksruting, logistikk og transportplanlegging, telekommunikasjon, vann- og strømforsyning, bildebehandling (for eksempel segmentering) og bipartitt
Historisk ble konseptet utviklet av L. L. Ford og D. R. Fulkerson i 1956. Siden har flytnettverk