5.1 Flytnett, restnett og snitt

En rettet graf der hver kant har en øvre grense for hvor mye som kan passere, og
der én node er utpekt som start og én som mål.

Formelt er et flytnett en rettet graf $G=(V,E)$ med en kilde $s$, et sluk
$t$ og en kapasitetsfunksjon $c$ som gir hver kant $(u,v) \in E$ et tall
$c(u,v) \ge 0$. Finnes det ingen kant fra $u$ til $v$, setter vi $c(u,v)=0$. Vi
antar at hver node ligger på en vei fra $s$ til $t$; noder som ikke gjør det, kan
aldri bære flyt og kan strykes.

Kilden $s$ er noden all flyt starter i, og sluket $t$ er noden all flyt ender i.
De to er de eneste nodene som får ha ubalanse mellom inn og ut.

Alle andre noder er gjennomgangsnoder. Det er nettopp derfor flytverdien kan måles
to steder med samme svar: det som netto forlater $s$, er det samme som det som
netto ankommer $t$.

En tildeling av et tall til hver kant, som sier hvor mye som faktisk sendes der, og
som oppfyller to betingelser samtidig.

En flyt er en funksjon som gir hvert nodepar en verdi $f(u,v)$ og oppfyller
kapasitetsbetingelsen $0 \le f(u,v) \le c(u,v)$ for alle kanter, og
bevaringsbetingelsen i alle noder unntatt $s$ og $t$. Flytverdien er
$\lvert f\rvert = \sum_{v \in V} f(s,v) - \sum_{v \in V} f(v,s)$, altså netto ut
av kilden. Maks-flyt-problemet er å finne en flyt med størst mulig verdi.

Ingen kant får bære mer enn kapasiteten sin, og ingen kant får bære et negativt
tall: $0 \le f(u,v) \le c(u,v)$.

Dette er den betingelsen som er lettest å sjekke, og den som faktisk blir sjekket.
En kant der $f(u,v) = c(u,v)$, kalles mettet — den er full, og kan ikke ta
imot mer uten at noe annet endres.

I alle andre noder enn kilden og sluket er summen av det som kommer inn, lik summen
av det som går ut.

Formelt: $\sum_{u \in V} f(u,v) = \sum_{w \in V} f(v,w)$ for hver
$v \in V \setminus \{s,t\}$. Dette er betingelsen som glemmes når man «tegner på»
litt ekstra flyt et sted. Kontrollen er mekanisk: gå gjennom nodene én for én og
legg sammen begge veier.

Hvor mye mer som kan sendes fra $u$ til $v$ når flyten $f$ allerede ligger der.

Det er to tilfeller, og begge er nødvendige. På en ekte kant $(u,v) \in E$ er
$c_f(u,v) = c(u,v) - f(u,v)$: kapasiteten minus det som allerede går der. Motsatt
vei er $c_f(v,u) = f(u,v)$: du kan «sende tilbake» opptil så mye som allerede går
framover. Alle andre par har $c_f = 0$. Engelsk fagterm: residual capacity.

Kanten den motsatte veien av en kant som bærer flyt. Den finnes ikke i det
opprinnelige nettet, men i restnettet, og den representerer retten til å angre.

Går det $f(u,v) = 8$ fra $u$ til $v$, har restnettet en kant fra $v$ til $u$ med
kapasitet 8. Å sende 3 langs ryggkanten betyr ikke at vann renner baklengs; det
betyr at du reduserer $f(u,v)$ fra 8 til 5 og bruker de tre enhetene et bedre sted.
Uten ryggkantene kan en algoritme male seg inn i et hjørne — å glemme dem er den
vanligste feilen i hele Del 5.

Grafen som viser alt som fortsatt er mulig: samme noder som det opprinnelige
nettet, men med de kantene som har positiv restkapasitet.

Restnettet $G_f$ har kantmengden $\{(u,v) : c_f(u,v) > 0\}$. Det inneholder inntil
to kanter per opprinnelig kant — framoverkanten og ryggkanten — så antallet kanter
er høyst $2E$, altså $O(E)$. Å bygge det tar $\Theta(V+E)$. Merk at $G_f$
ikke er et delnett av $G$: ryggkantene finnes ikke i $G$.

En vei fra kilden til sluket i restnettet, altså en rekke kanter som alle har
restkapasitet igjen.

Formelt er det en enkel sti fra $s$ til $t$ i $G_f$. En slik sti kan bestå av både
framoverkanter og ryggkanter, og det er helt i orden — en ryggkant på stien betyr
bare at en tidligere beslutning delvis reverseres. Engelsk fagterm:
augmenting path. Å lete etter en tar $\Theta(V+E)$ med BFS.

Den minste restkapasiteten langs stien — altså akkurat så mye du kan sende før det
første leddet går tomt.

For en sti $p$ er flaskehalsen minimum av $c_f(u,v)$ over kantene på $p$. Forøker
du med dette tallet, blir minst én kant på stien mettet (eller minst én ryggkant
tømt), og stien forsvinner fra restnettet. Flaskehalsen er alltid et positivt tall,
siden alle kanter i $G_f$ har $c_f > 0$.

En oppdeling av alle nodene i to deler, der kilden ligger i den ene og sluket i den
andre.

Et snitt $(S,T)$ er en partisjon av $V$ med $s \in S$ og $t \in T$, der $S$ og $T$
til sammen utgjør $V$ og ikke har noen node felles. Hver node er i nøyaktig én av
delene. Det er ingen krav om at delene skal være like store eller henge sammen:
$S = \{s\}$ er et fullgodt snitt. Et nett med $n$ noder har $2^{n-2}$ ulike snitt.

Summen av kapasitetene på kantene som går fra $S$-siden til $T$-siden — og bare de.

$c(S,T) = \sum_{u \in S} \sum_{v \in T} c(u,v)$. Kanter som går den andre veien,
fra $T$ til $S$, teller ikke med, og kanter som går internt i $S$ eller internt
i $T$, teller heller ikke. Dette er den enkeltdetaljen som oftest gir feil svar på
en snittoppgave.

Netto hvor mye som faktisk krysser snittet: flyten fra $S$ til $T$ minus flyten fra
$T$ til $S$.

I motsetning til kapasiteten teller snittflyten begge retninger, men med
motsatt fortegn: du summerer $f(u,v)$ for $u \in S$, $v \in T$, og trekker fra
$f(v,u)$ for de samme parene. Blander du de to reglene, får du feil på begge
regnestykkene.

Netto hvor mye som forlater kilden — og dermed også netto hvor mye som ankommer
sluket.

Regnestykket er summen av $f(s,v)$ over alle noder, minus summen av $f(v,s)$.
Trekket for flyt inn i $s$ er sjelden aktuelt, men det hører med i definisjonen. Å
lese av flytverdien tar $\Theta(V)$ når du har nabolista til $s$. Kontroller alltid
mot sluket: får du et annet tall der, har du brutt bevaringsbetingelsen et sted.

En kant der flyten er lik kapasiteten, altså $f(u,v) = c(u,v)$.

En mettet kant har ingen framoverkant i restnettet, bare ryggkant. I et min-snitt er
alle kantene fra $S$ til $T$ mettet — det er selve kjennetegnet på at snittet er
stramt.

Flyten der $f(u,v) = 0$ for hver kant. Den er alltid lovlig, og den har verdi 0.

Nullflyten er startpunktet for alle flytalgoritmer. Restnettet til nullflyten er det
opprinnelige nettet uten ryggkanter, siden ingen kant bærer noe å angre på.

Å finne en lovlig flyt med størst mulig verdi i et gitt flytnett.

Problemet er løsbart i polynomisk tid — Edmonds-Karp klarer det i $O(VE^2)$, se
kap. 5.2. Det finnes alltid en optimal løsning, og med
heltallige kapasiteter finnes det alltid en heltallig optimal løsning. Bruk
maks-flyt når oppgaven handler om å presse mest mulig gjennom et nett med
kapasiteter, eller om å tilordne én mengde til en annen.

Et snitt med minst mulig snittkapasitet blant alle snitt i nettet.

Snittlemmaet gir at $\lvert f\rvert \le c(S,T)$ for alle par av flyt og snitt, så
maks-flyten er høyst så stor som det minste snittet. At de to faktisk er like —
maks-flyt/min-snitt-teoremet — vises i kap. 5.2. Et nett kan
ha flere min-snitt med samme kapasitet, og derfor ber oppgaver om «et
min-snitt», ikke «det».