Maksimal flyt

Flyt er det mest allsidige grafproblemet i pensum: det kobler optimering, dualitet og reduksjoner i ett rammeverk. Mange tilsynelatende urelaterte problemer — maksimal paring, kantdisjunkte stier, prosjektutvelgelse — løses ved å oversette dem til et flytnett og kjøre én algoritme.

Flytnett, flyt og maks-flyt

Et flytnett er en rettet graf $G = (V, E)$ med en ikke-negativ kapasitet $c(u,v) \ge 0$ på hver kant, en kilde $s$ og en sluk $t$. En flyt er en funksjon $f(u,v)$ som oppfyller to krav:

Maks-flyt-problemet er å finne en lovlig flyt med størst mulig verdi $|f|$. Verdien er begrenset oppad av enhver «flaskehals» i nettet — det er nettopp denne dualiteten min-snitt-teoremet gjør presis.

Restnett og forøkende stier

Gitt en flyt $f$ er ikke det interessante hvor mye som er sendt, men hvor mye mer som kan sendes. Det fanger restnettet $G_f$.

Bakoverkantene er nøkkelen: de lar algoritmen ombestemme seg og dirigere flyt en bedre vei senere. En forøkende sti er en hvilken som helst sti fra $s$ til $t$ i $G_f$. Langs den kan vi øke flytverdien med stiens flaskehals — den minste restkapasiteten på stien — uten å bryte verken kapasitet eller bevaring.

Maks-flyt/min-snitt-teoremet

Et snitt $(S, T)$ deler nodene slik at $s \in S$ og $t \in T$. Snittets kapasitet er summen av kapasiteten på alle kanter som krysser fra $S$ til $T$. Enhver flyt må passere et hvilket som helst snitt, så $|f|$ er aldri større enn kapasiteten til noe snitt. Det stramme tilfellet er hovedresultatet:

Ekvivalensen $(1)\!\Leftrightarrow\!(2)$ gir terminerings­garantien for algoritmene under; $(2)\!\Leftrightarrow\!(3)$ gir et sertifikat: når søket ikke finner flere stier, danner nodene som fortsatt er nåbare fra $s$ i $G_f$ den ene siden $S$ av et minimalt snitt.

Ford-Fulkerson-metoden

Ford-Fulkerson er en metode, ikke én bestemt algoritme: så lenge restnettet har en forøkende sti, finn en og forøk flyten langs den.

def ford_fulkerson(G, s, t):
  for (u, v) in G.E:
      f[u][v] = 0
  while finnes_forøkende_sti(G_f, s, t):
      p = bfs_sti(G_f, s, t)
      c_f = min(restkapasitet(u, v) for (u, v) in p)
      for (u, v) in p:
          f[u][v] += c_f          # eller opphev motgående flyt
  return sum(f[s][v] for v in G.adj[s])

Hvis vi alltid velger den korteste forøkende stien (færrest kanter), målt med et BFS i restnettet, får vi Edmonds-Karp. Det er nettopp denne varianten stepperen viser. Edmonds-Karp kjører i $O(VE^2)$ uavhengig av kapasitetene, mens en uheldig stivalg-strategi i den rene metoden kan bruke flere forøkninger jo større tallene er.

Heltallsteoremet

Når algoritmen følger en sti og legger til flaskehalsen, holder den seg innenfor heltallene så lenge kapasitetene er heltall:

Dette er grunnen til at flyt kan modellere kombinatoriske «alt-eller-ingenting»-valg: en heltallsflyt med kapasiteter $0/1$ velger faktisk hele kanter eller paringer.

Reduksjoner til maks-flyt

Styrken ligger i at andre problemer kan reduseres til maks-flyt. Mønsteret er alltid det samme: bygg et flytnett der en heltalls maks-flyt koder en optimal løsning på det opprinnelige problemet.

Sjekk deg selv