Maksimal flyt

Mest mulig gjennom rørene

Se for deg et nettverk av vannrør fra en pumpestasjon til en tank. Hvert rør har en grovhet som setter en øvre grense for hvor mange liter i sekundet det tåler. Spørsmålet er enkelt å stille og overraskende rikt å svare på: hvor mye vann kan vi sende fra pumpa til tanken samtidig? Dette er maksimal flyt, og samme modell beskriver datapakker gjennom et nett, varer gjennom en forsyningskjede, og — som vi skal se — parring av folk og oppgaver.

Vi formaliserer det som et flytnett: en rettet graf med en utpekt kilde $s$ og et sluk $t$, der hver kant $(u,v)$ har en kapasitet $c(u,v)\ge 0$. En flyt er en tilordning av et tall $f(u,v)$ til hver kant som oppfyller to krav. For det første kan ingen kant føre mer enn den tåler, og flyten er aldri negativ — ƒkapasitetsbegrensning. For det andre må alt som renner inn i en node, bortsett fra kilden og sluket, renne ut igjen; ingenting hopes opp eller forsvinner underveis. Det er flytbevaring: ƒflytbevaring.

Verdien av en flyt, skrevet $|f|$, er nettomengden som forlater kilden — som på grunn av bevaring er nøyaktig like mye som ankommer sluket. Målet vårt er å gjøre $|f|$ så stor som mulig.

I nettet over står «flyt/kapasitet» på hver kant. Kanten $s\to a$ fører for eksempel 2 av sine 3 mulige enheter. Sjekk gjerne bevaringen i en node: inn til $c$ kommer $2+1=3$ enheter, og ut går $3$. Den samlede flytverdien her er 4, summen som forlater $s$.

Den grådige fellen, og veien rundt

En naturlig idé er å være grådig: finn en vei fra $s$ til $t$ der alle kantene har ledig kapasitet, dytt så mye flyt du kan langs den, gjenta. Det virker rett, men kan kjøre seg fast. Tar du en tidlig vei som «sperrer» en kant en bedre løsning trengte, finnes det ingen ren forover-vei igjen — selv om den maksimale flyten ikke er nådd. Vi trenger en måte å angre et tidligere valg på.

Løsningen er restnettet. For hver kant regner vi ut hvor mye mer den tåler — restkapasiteten ƒrestkapasitet. Men her ligger det geniale grepet: for hver kant $(u,v)$ som allerede fører flyt, legger vi inn en bakoverkant $(v,u)$ i restnettet, med restkapasitet lik den nåværende flyten. Å sende flyt langs en bakoverkant betyr i praksis å trekke tilbake flyt på den ekte kanten. Slik kan algoritmen ombestemme seg uten å starte på nytt.

En forøkende sti er en hvilken som helst sti fra $s$ til $t$ i restnettet der hver kant har positiv restkapasitet. Den minste restkapasiteten langs stien er flaskehalsen — så mye ekstra flyt kan vi presse gjennom. På forover-kanter øker vi flyten, på bakover-kanter senker vi den. I figuren over har stien $s\to b\to c\to t$ ledig kapasitet hele veien, med flaskehals 1, så vi kan øke den totale flyten med 1.

Ford-Fulkerson: finn en sti, øk flyten, gjenta

ford-fulkerson er hele metoden i én setning: start med null flyt overalt, finn en forøkende sti i restnettet, øk flyten langs den med flaskehalsverdien, og gjenta helt til ingen forøkende sti finnes igjen.

for hver kant (u, v):
    f[u][v] = 0
mens det finnes en forøkende sti P fra s til t i restnettet:
    Δ = minste restkapasitet langs P
    for hver kant (u, v) på P:
        if (u, v) er en forover-kant:
            f[u][v] = f[u][v] + Δ
        else:                       # bakover-kant: angre flyt
            f[v][u] = f[v][u] - Δ
returner f

Når løkka stopper, er det fordi sluket ikke lenger er nåbart fra kilden i restnettet. Det er ikke tilfeldig at flyten da er maksimal — det er kjernen i hele teorien, og vi forklarer hvorfor i neste avsnitt.

Et ord om kjøretid. Hvis vi velger forøkende sti uforsiktig, kan Ford-Fulkerson i verste fall øke flyten med bare én enhet per runde, og antallet runder avhenger da av selve kapasitetstallene. Med to kanter av kapasitet en million og en uheldig stivalg-rekkefølge kan det ta en million runder. Det er en svakhet vi snart fjerner.

Snitt: en mur mellom kilde og sluk

For å forstå hvorfor Ford-Fulkerson gir maksimal flyt, trenger vi begrepet snitt (i flytnett). Et snitt deler nodene i to grupper: en kilde-side $S$ som inneholder $s$, og en sluk-side $T$ som inneholder $t$. Kapasiteten til snittet er summen av kapasitetene på alle kantene som krysser fra $S$ til $T$ — bakoverkantene teller ikke.

Tenk på snittet som en mur tvers gjennom rørnettet. Alt vann som skal fra pumpe til tank må krysse muren et sted. Derfor kan ingen flyt noensinne overstige kapasiteten til noe snitt: hver eneste flyt er begrenset ovenfra av hvert eneste snitt. Spesielt er den maksimale flyten begrenset av det minste snittet.

Det forbløffende er at denne grensa alltid nås nøyaktig. maks-flyt/min-snitt-teoremet sier: ƒmaks-flyt/min-snitt — den maksimale flyten er lik kapasiteten til det minste snittet. Argumentet henger sammen med Ford-Fulkerson: når algoritmen stopper, er det ingen forøkende sti, altså er $t$ utilgjengelig fra $s$ i restnettet. La $S$ være alle nodene som er nåbare fra $s$ i restnettet. Da må hver kant fra $S$ til $T$ være helt full (ellers ga den restkapasitet, og naboen var nåbar), og hver kant fra $T$ til $S$ være helt tom. Flyten over snittet er da nøyaktig snittkapasiteten — og siden ingen flyt kan overstige noe snitt, må denne flyten være maksimal og dette snittet minimalt. De tre tingene — ingen forøkende sti, maksimal flyt, og et mettet minste snitt — er én og samme situasjon.

Edmonds-Karp: velg stien klokt

Svakheten i Ford-Fulkerson var det udisiplinerte stivalget. edmonds-karp fjerner den med ett lite grep: velg alltid den forøkende stien med færrest kanter, altså korteste sti i restnettet målt i antall hopp. Det finner vi enkelt med et bredde-først-søk fra $s$.

mens BFS fra s i restnettet når t:
    P = korteste sti (i antall kanter) fra s til t
    øk flyten langs P med flaskehalsverdien

Med dette valget kan man vise at avstanden fra $s$ til hver node i restnettet aldri minker mens algoritmen går, og at hver kant blir flaskehals høyst $O(V)$ ganger. Det gir totalt $O(V\cdot E)$ forøkende stier, og siden hvert BFS koster $O(E)$, lander vi på ƒedmonds-karp, $O(V\cdot E^2)$. Avgjørende er at denne grensa ikke nevner kapasitetene med ett ord: Edmonds-Karp er polynomiell uansett hvor store tallene er. Den million-runders-fellen er borte.

Samme rammeverk, nytt problem: matching

Det vakreste med maks-flyt er hvor mange tilsynelatende urelaterte problemer den løser når du klarer å modellere dem som et flytnett. Det klassiske eksempelet er bipartitt matching: du har en gruppe søkere og en gruppe jobber, og en kant mellom en søker og en jobb betyr at søkeren er kvalifisert. Hvor mange kan vi ansette samtidig, når hver søker kan ta én jobb og hver jobb fylles av én person?

Trikset er å bygge et flytnett rundt grafen. Legg til en kilde $s$ med en kant av kapasitet 1 til hver søker, og et sluk $t$ med en kant av kapasitet 1 fra hver jobb. La hver kvalifikasjonskant gå fra venstre til høyre med kapasitet 1. Kjør så maks-flyt. Kapasitet 1 inn til hver søker tvinger søkeren til å bli brukt høyst én gang, og kapasitet 1 ut av hver jobb tvinger det samme der. En heltallig flyt av verdi $k$ svarer da nøyaktig til en matching med $k$ par — og Ford-Fulkerson gir alltid heltallige flytverdier når kapasitetene er heltall. I figuren over er $x_1$–$y_1$, $x_2$–$y_3$ og $x_3$–$y_2$ en matching som parrer alle tre.

Det er denne oversettbarheten som gjør maks-flyt til et av de mest anvendelige verktøyene i hele algoritmefaget: lær deg å gjenkjenne et flytnett i forkledning, så får du en effektiv løsning nesten gratis.