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 kantens kapasitet. For hver node unntatt kilde og sluk må sum av innflyt være lik sum av utflyt. Verdien til en flyt er den totale utstrømningen fra kilden, ofte skrevet som |f| = sum over utgående kanter fra s av f(e) minus sum over innkommende kanter til s av f(e).

Maksimal flyt-problemet består i å finne en flyt med maksimal verdi under kapasitet- og balansebetingelsene. Ifølge max-flow min-cut-teoremet er den maksimale flyten lik kapasiteten til den minste s-t-kuttet i grafen.

Algoritmer som ofte brukes er Ford-Fulkerson-metoden, Edmonds-Karp-varianten (BFS-basert augmenting paths) og moderne tilnærminger som Dinics algoritme og Push-relabel-algoritmer. Begge disse typene bruker residualgrafen for å finne augmenterende stier og oppdatere flyten.

Residualgrafen viser gjenstående kapasitet på hver kant og hjelper til med å identifisere nye augmenterende stier. Viktige egenskaper inkluderer at flyter kan være integrale når kapasitetene er heltallige, og max-flow min-cut-teoremet gir en dyp sammenheng mellom flyt og kutt.

Anvendelser inkluderer nettverksruting, logistikk og transportplanlegging, telekommunikasjon, vann- og strømforsyning, bildebehandling (for eksempel segmentering) og bipartitt matching i operasjonsanalyse.

Historisk ble konseptet utviklet av L. L. Ford og D. R. Fulkerson i 1956. Siden har flytnettverk vært sentralt i grafteori og anvendt optimering.