5.2 Ford-Fulkerson, Edmonds-Karp og maks-flyt/min-snitt

`Ford-Fulkerson`-metoden, `Edmonds-Karp` (BFS-forøkende stier), maks-flyt/min-snitt-teoremet, og hvorfor FF er pseudopolynomisk mens EK er polynomisk.

55 min

6 oppgaver

Ford-FulkersonEdmonds-Karpmaks-flyt/min-snitt

Din fremgang i kapitlet

0 / 6 oppgaver

Kapitlets plass i kurset

Bygger på

5.1Flytnett, restnett og snitt

Brukes videre i

5.3DRILL — Håndkjøring av maks-flyt og flyt-modellering 7.1P, NP og co-NP — sertifikat og verifikasjon

Maksimal flyt er registrert i 16 av de 17 settene i grunnlaget (94 %).
Grunnlaget er de 17 settene fra august 2015 til august 2023 som er gjennomgått
tema for tema — det er nevneren hver gang boka oppgir en prosent.

Maks-flyt er den ene av fagets to designryggrader: de åpne designoppgavene på
slutten av settet handler oftere om flyt enn om noe annet. Prioritet:
høyeste prioritet — dette må sitte.

Tre sjangre henter fra dette kapitlet, og de skrives ut i klarspråk her:

- Sjanger E — kjøretidskunnskap, altså at du oppgir kjøretiden i det
strammeste uttrykket som er riktig. $O(VE^2)$ for Edmonds-Karp er et av
tallene som skal sitte kaldt.
- Sjanger F — «stemmer dette?», altså at du svarer ja eller nei først og
deretter gir én presis setning. Den klassiske her: «Er Ford-Fulkerson
polynomisk?»
- Sjanger G — argument om vanskelighet, altså at du sier hva et argument
faktisk viser. Her møter du skillet mellom pseudopolynomisk og
NP-hardt, som er et av fagets faste innsiktsspørsmål.

Det ene skillet du må ha klart: at Ford-Fulkerson ikke er polynomisk,
betyr ikke at maks-flyt er et vanskelig problem. Maks-flyt løses i
polynomisk tid av Edmonds-Karp. Det er algoritmen som er treg, ikke problemet
som er hardt. Dette er felle #7.

Slik er kapitlet lagt opp (55 min):

Innhold	Tid
Ford-Fulkerson-metoden	ca. 15 min
`Edmonds-Karp` og hvorfor den er polynomisk	ca. 12 min
Maks-flyt/min-snitt-teoremet	ca. 14 min
Pseudopolynomisk mot polynomisk	ca. 14 min

Forkunnskaper

- kap. 5.1 — flytnett, restnett og snitt. Dette er
hele grunnlaget, og de fire resultatene du trenger i hånden, står her:

1. Restkapasiteten er $c_f(u,v) = c(u,v) - f(u,v)$ for en framoverkant,
og $c_f(v,u) = f(u,v)$ for ryggkanten. Restnettet $G_f$ inneholder
alle kanter med $c_f > 0$ .
2. En forøkende sti er en sti fra $s$ til $t$ i restnettet.
Flaskehalsen er den minste restkapasiteten på stien.
3. Et snitt $(S,T)$ deler nodene med $s \in S$ og $t \in T$ .
Snittkapasiteten $c(S,T)$ teller bare kantene som går fra $S$ til $T$ .
4. Snittlemmaet: for enhver lovlig flyt og ethvert snitt er
$\lvert f\rvert = f(S,T) \le c(S,T)$ . All flyt må krysse ethvert snitt.

Det siste er den ene ulikheten hele dette kapitlet hviler på.
- kap. 4.1 — BFS. Edmonds-Karp er Ford-Fulkerson
med BFS til å finne stien, og det er den eneste forskjellen.
- kap. 1.1 — de asymptotiske symbolene.

Notasjons- og pseudokodeliste

Ford-Fulkerson-metoden (~15 min)

Ideen er så enkel at det er lett å undervurdere den: så lenge det finnes en
vei å presse mer vann gjennom, gjør det.

«En vei» betyr en sti fra $s$ til $t$ i restnettet, og restnettet er nettopp
konstruert slik at en sti der alltid er lovlig å bruke. Ryggkantene gjør at
metoden kan angre tidligere valg: å sende flyt bakover langs en ryggkant
betyr i praksis å trekke tilbake litt av det som ble sendt framover før.

Legg merke til ordet metode, ikke algoritme. Ford-Fulkerson sier ikke
hvordan stien skal finnes — bare at den skal finnes. Det valget er det som
avgjør kjøretiden, og det er derfor Edmonds-Karp finnes.

📜Pseudokode-kontrakt: `Ford-Fulkerson`

Antagelser om representasjon. Flytnettet er

G=(V,E)

med kilde s, sluk
t og kapasiteter c(u,v) >= 0. Restnettet G_f bygges av c og f etter
regelen fra kap. 5.1. Kapasitetene antas heltallige
— ellers er ikke terminering garantert.

Prebetingelse: c(u,v) >= 0 for alle kanter.
Postbetingelse: f er en maksimal flyt, og nodene som kan nås fra s i
restnettet, utgjør venstresiden i et min-snitt.

Ford-Fulkerson(G, s, t)
  Input:  flytnettet G med kapasiteter c, kilde s, sluk t
  Output: en maksimal flyt f
  for hver kant (u,v) i E
      f(u,v) = 0
  while det finnes en sti p fra s til t i restnettet G_f
      flaskehals = min over kantene (u,v) paa p av c_f(u,v)
      for hver kant (u,v) paa p
          if (u,v) er en framoverkant
              f(u,v) = f(u,v) + flaskehals
          else
              f(v,u) = f(v,u) - flaskehals
  return f
  Kjoeretid: O(E * |f*|) med heltallige kapasiteter

Invarianten i én setning: f er hele veien en lovlig flyt — den bryter
verken kapasitets- eller bevaringsbetingelsen — og flytverdien øker med minst 1
i hver runde.

Hvorfor den terminerer. Med heltallige kapasiteter er flaskehalsen alltid
et positivt heltall, så $\lvert f\rvert$ øker med minst 1 per runde. Den kan
ikke overstige maksimal flytverdi $\lvert f^*\rvert$ , så antall runder er høyst
$\lvert f^*\rvert$ . Hver runde koster $O(E)$ til å finne stien og forøke.

Kjøretid: $O(E\cdot\lvert f^*\rvert)$ . Legg merke til hva som står der:
kjøretiden avhenger av tallverdien til svaret, ikke bare av hvor stor
grafen er. Det er nettopp definisjonen på pseudopolynomisk, og vi kommer
tilbake til det.

✏️Eksempel 1: `Ford-Fulkerson` fra tom flyt til maksimal

Vanningsanlegget fra kap. 5.1 har pumpehuset $s$ ,
kummene $a$ , $b$ , $c$ , $d$ og jordet $t$ , med kapasitetene

c(s,a) = 12    c(s,b) = 9     c(a,b) = 4    c(a,c) = 8
c(b,d) = 10    c(c,t) = 14    c(d,c) = 5    c(d,t) = 9

Kjør Ford-Fulkerson fra nullflyten, og finn stiene med BFS (altså
Edmonds-Karp). Naboene besøkes i alfabetisk rekkefølge.

Oppgi maksimal flytverdi og et min-snitt.

Runde	Forøkende sti	Flaskehals	$\lvert f\rvert$ etterpå
1	$s \to a \to c \to t$	8	8
2	$s \to b \to d \to t$	9	17
3	$s \to a \to b \to d \to c \to t$	1	18
4	ingen sti finnes i $G_f$	—	18

Runde 1: stien

s \to a \to c \to t

har restkapasiteter

12

8

14

— flaskehalsen er 8, satt av den mettede kanten

a \to c

.
Runde 2: stien

s \to b \to d \to t

har restkapasiteter

9

10

9

—
flaskehalsen er 9.
Runde 3: nå er de to åpenbare veiene brukt opp, og BFS finner

$s \to a \to b \to d \to c \to t$ med restkapasiteter $4$ , $4$ , $1$ , $5$ og
$6$ . Flaskehalsen er 1, satt av $b \to d$ , som allerede bærer 9 av 10.

Runde 4: BFS fra $s$ i restnettet når bare $a$ og $b$ . Ingen sti til $t$
finnes, og algoritmen stopper.

Den endelige flyten:

f(s,a) = 9/12    f(s,b) = 9/9     f(a,b) = 1/4     f(a,c) = 8/8
f(b,d) = 10/10   f(c,t) = 9/14    f(d,c) = 1/5     f(d,t) = 9/9

Sluttilstanden — det du ville levert på eksamen:

Maks-flyt $\lvert f^*\rvert = 18$ . Et min-snitt er
$S = \{a, b, s\}$ , $T = \{c, d, t\}$ ,

med snittkapasitet $8 + 10 = 18$ .

Slik leser du av min-snittet. Når algoritmen stopper, kjører du én siste

BFS fra $s$ i restnettet. Nodene den når, utgjør $S$ ; resten utgjør $T$ . Her

nås $a$ og $b$ , men ikke $c$ , $d$ eller $t$ .
Legg merke til at runde 3 var den vanskelige. Uten ryggkantene i restnettet
ville den stien ikke eksistert — kanten $d \to c$ er en vanlig framoverkant her,

men det er sidesprangene gjennom $a \to b$ som gjør at den siste enheten finner
veien. En sti som denne er nettopp det håndkjøringsoppgaver tester.
Merk at oppgaven ba om både flytverdien og et min-snitt. Er begge spurt om,

er begge en del av svaret.

📝Oppgave 1

(Innstegsoppgave, sjanger D — definisjon med egne ord, altså én presis setning
med hovedpoenget først.)

Forklar hva Ford-Fulkerson-metoden gjør, og hvorfor den kalles en metode
og ikke en algoritme.

📝Oppgave 2

Eksamensnivå, sjanger C

Et flytnett har nodene $s$ , $u$ , $v$ , $x$ , $y$ , $t$ og kapasitetene

c(s,u) = 10    c(s,v) = 8     c(u,v) = 3    c(u,x) = 6
c(v,y) = 9     c(x,t) = 7     c(y,x) = 4    c(y,t) = 5

Kjør Edmonds-Karp fra nullflyten, med naboene i alfabetisk rekkefølge.

a) Oppgi de forøkende stiene og flaskehalsene.
b) Oppgi maksimal flytverdi og et min-snitt.

`Edmonds-Karp` og hvorfor den er polynomisk (~12 min)

Forskjellen mellom Ford-Fulkerson og Edmonds-Karp er én linje: hvordan
stien velges. Edmonds-Karp bruker korteste forøkende sti, målt i antall
kanter, og finner den med BFS.

Det høres ut som en detalj. Det er det ikke.

📜Pseudokode-kontrakt: `Edmonds-Karp`

Antagelser om representasjon. Som Ford-Fulkerson. Restnettet

G_f

bygges på nytt (eller oppdateres) etter hver forøkning, og BFS kjøres på det.

Prebetingelse: c(u,v) >= 0. Merk at heltallighet ikke er nødvendig
her — kjøretidsgrensen holder også for reelle kapasiteter.
Postbetingelse: f er en maksimal flyt.

Edmonds-Karp(G, s, t)
  Input:  flytnettet G med kapasiteter c, kilde s, sluk t
  Output: en maksimal flyt f
  for hver kant (u,v) i E
      f(u,v) = 0
  while BFS finner en sti p fra s til t i G_f
      flaskehals = min over kantene (u,v) paa p av c_f(u,v)
      forok flyten langs p med flaskehals
  return f
  Kjoeretid: O(V * E^2)

Grunnideen i én setning: når stien alltid er den korteste, kan avstanden
fra $s$ til hver node i restnettet aldri synke underveis — og det gir en
grense på hvor mange forøkninger som kan gjøres.

Utledningen, i tre ledd.

Ledd 1. Avstanden $\delta_f(s,v)$ fra $s$ til $v$ i restnettet er
ikke-synkende gjennom hele kjøringen. Hver forøkning fjerner minst én kant fra
restnettet (den som var flaskehals) og kan legge til ryggkanter, men aldri på
en måte som forkorter avstanden.

Intuisjon: BFS tar alltid den korteste veien, så en ny snarvei måtte ha
eksistert allerede.

Ledd 2. En kant $(u,v)$ som er flaskehals i én runde, kan ikke bli flaskehals
igjen før avstanden $\delta_f(s,u)$ har økt med minst 2.

Intuisjon: kanten forsvinner fra restnettet når den mettes, og den kommer
bare tilbake hvis flyt sendes bakover gjennom den — og det skjer bare når
$u$ ligger lenger unna $s$ enn før.

Ledd 3. Avstanden er høyst $V-1$ , så hver av de $E$ kantene kan være
flaskehals høyst $O(V)$ ganger. Det gir $O(VE)$ forøkninger totalt, og hver
koster $O(E)$ til BFS.

Kjøretid: $O(VE^2)$ . Uttrykket inneholder bare $V$ og $E$ — ingen
kapasiteter. Det er nettopp det som gjør algoritmen polynomisk.

📝Oppgave 3

Eksamensnivå, sjanger E

a) Hva er kjøretiden til Edmonds-Karp, og hva avhenger den av?
b) Hva er kjøretiden til Ford-Fulkerson med vilkårlig valg av sti, og hva
avhenger den av?
c) Hvilken av de to ville du valgt hvis kapasitetene kunne være opptil en
milliard?

Maks-flyt/min-snitt-teoremet (~14 min)

Nå kommer resultatet hele delen bygger mot, og det er et av de vakreste i
faget: det største du kan presse gjennom, er nøyaktig like mye som den
billigste flaskehalsen.

📜Maks-flyt/min-snitt-teoremet

Påstanden. For enhver lovlig flyt

f

i et flytnett er disse tre utsagnene
ekvivalente:

1. $f$ er en maksimal flyt.
2. Restnettet $G_f$ inneholder ingen forøkende sti.
3. Det finnes et snitt $(S,T)$ med $\lvert f\rvert = c(S,T)$ .

Følgen er navnet på teoremet: den maksimale flytverdien er lik den minimale
snittkapasiteten,

$\max_f \lvert f\rvert = \min_{(S,T)} c(S,T)$

Argumentet, kort. At 1 gir 2 er lett: fantes det en forøkende sti, kunne
flyten økes, og da var den ikke maksimal. At 3 gir 1 følger av snittlemmaet fra
kap. 5.1: enhver flyt er $\le c(S,T)$ , så en flyt som
når $c(S,T)$ , kan ikke slås.

Den interessante retningen er at 2 gir 3, og den er konstruktiv: la $S$ være
nodene som kan nås fra $s$ i restnettet. Siden ingen forøkende sti finnes, er
$t \notin S$ , så $(S,T)$ er et snitt. Hver kant fra $S$ til $T$ må være
mettet — ellers ville den gitt en restkant, og naboen ville ligget i $S$ .
Hver kant fra $T$ til $S$ må ha null flyt, av samme grunn. Da er
$\lvert f\rvert = f(S,T) = c(S,T)$ .

Konsekvensen du bruker på eksamen: når Ford-Fulkerson stopper, kjør én
BFS fra $s$ i restnettet. Nodene den når, er venstresiden i et min-snitt.
Du får snittet gratis, og du får samtidig beviset på at flyten er maksimal.

✏️Eksempel 2: Bevis at en flyt er maksimal

En kandidat leverer en flyt med verdi 18 i vanningsanlegget og påstår at den er
maksimal.

a) Hvordan kan påstanden bevises uten å kjøre algoritmen på nytt?
b) Gjennomfør beviset.
c) Hva ville et snitt med kapasitet 22 fortalt deg?

a) Finn et snitt med kapasitet 18. Snittlemmaet sier at enhver flyt er

\le c(S,T)

for ethvert snitt, så en flyt som når kapasiteten til et snitt,
kan ikke slås — og snittet kan ikke være dyrere enn noe annet.

Det er den ene retningen av maks-flyt/min-snitt, og den er kort nok til å
skrives på to linjer.

b) Velg $S = \{s, a, b\}$ og $T = \{c, d, t\}$ . Kantene fra $S$ til $T$ er
$a \to c$ med kapasitet 8 og $b \to d$ med kapasitet 10. Ingen andre kanter går
den veien.

$c(S,T) = 8 + 10 = 18 = \lvert f\rvert$

Altså er flyten maksimal, og snittet er minimalt. Ferdig.

c) Ingenting avgjørende. Et snitt med kapasitet 22 gir bare den øvre
grensen $\lvert f\rvert \le 22$ , og den er allerede oppfylt av en flyt på 18.
Beviset krever et snitt som treffer flytverdien.

Snittet $S = \{s\}$ har for eksempel kapasitet $12 + 9 = 21$ — sant, men
ubrukelig som bevis.

Svarformen på eksamen: oppgi snittet, list kantene som krysser, summer, og
konstater likheten. Fire linjer.

📝Oppgave 4

Eksamensnivå, sjanger F

Ta stilling til hver av påstandene:

a) Et flytnett har alltid nøyaktig ett min-snitt.
b) Hvis en kant krysser et min-snitt fra $S$ til $T$ , må den være mettet.
c) Maks-flyt/min-snitt-teoremet gjelder bare når kapasitetene er heltall.

Pseudopolynomisk mot polynomisk (~14 min)

Her ligger et av fagets faste innsiktsskiller, og det er verdt å bruke tid på —
fordi det blir hentet fram igjen i kap. 7.2 og fordi
det er lett å trekke feil konklusjon av det.

Pseudopolynomisk

O(E\cdot\lvert f^*\rvert)

Felle #7 — pseudopolynomisk er ikke det samme som NP-hardt

Dette er felle #7, og den er blant fagets mest fremhevede.

At Ford-Fulkerson ikke er polynomisk, sier ingenting om hvor vanskelig
maks-flyt-problemet er. Det sier bare noe om den ene algoritmen.

Maks-flyt er et lett problem: Edmonds-Karp løser det i $O(VE^2)$ , altså i
polynomisk tid. Problemet ligger i klassen P.

Kontrollen når du skal formulere svaret:

- «Ford-Fulkerson er pseudopolynomisk» — riktig.
- «Maks-flyt er derfor et vanskelig problem» — galt.
- «Maks-flyt kan løses i polynomisk tid av Edmonds-Karp» — riktig.

Det samme skillet dukker opp igjen i kap. 6.2 med
0-1-ryggsekk, som har en $\Theta(nm)$ -algoritme der $m$ er en tallverdi.
Der er problemet faktisk NP-hardt — men det følger ikke av at algoritmen er
pseudopolynomisk, det følger av et helt annet argument.

✏️Eksempel 3: Et nett der `Ford-Fulkerson` kan gå galt

Konstruér et flytnett med fire noder der Ford-Fulkerson med uheldig valg
av forøkende sti bruker mange flere runder enn nødvendig, og forklar hvorfor
Edmonds-Karp slipper unna.

Konstruksjonen. La nodene være

s

u

v

t

med kapasitetene

c(s,u) = 1000000    c(s,v) = 1000000
c(u,t) = 1000000    c(v,t) = 1000000
c(u,v) = 1

Det uheldige valget. Velger metoden stien $s \to u \to v \to t$ , er
flaskehalsen 1 — kanten $u \to v$ slipper bare én enhet gjennom. Etter
forøkningen finnes ryggkanten $v \to u$ med restkapasitet 1, og metoden kan
velge $s \to v \to u \to t$ , som også har flaskehals 1.

Fortsetter den å veksle mellom disse to stiene, øker flyten med 1 per
runde, og det trengs 2 000 000 runder for å nå maksimal flyt.

Hvorfor Edmonds-Karp slipper unna. BFS finner alltid den korteste
stien. Stiene $s \to u \to t$ og $s \to v \to t$ har to kanter; de uheldige
stiene har tre. Edmonds-Karp tar derfor de to korte først, mestrer hele
flyten på to runder, og rører aldri kanten $u \to v$ .

Poenget med eksemplet. Antall runder i Ford-Fulkerson avhenger av
kapasitetenes størrelse; i Edmonds-Karp avhenger det bare av grafens
form. Fordoble kapasitetene i eksemplet, og den første kjøringen tar dobbelt så
lang tid mens den andre er uendret.

Og merk hva eksemplet ikke viser: at maks-flyt er vanskelig. Det samme
nettet løses på to runder av Edmonds-Karp.

📝Oppgave 5

Eksamensnivå, sjanger F…

En kandidat skriver: «Ford-Fulkerson er pseudopolynomisk. Maks-flyt er derfor
et vanskelig problem, sannsynligvis NP-hardt.»

Er konklusjonen riktig? Svar ja eller nei, og forklar hva argumentet viser og
hva det ikke viser.

📝Oppgave 6

Eksamensnivå, sjanger H

Et sykehus har $n$ sykepleiere og $m$ vakter. Hver sykepleier har oppgitt
hvilke vakter hun kan ta, og kan ta høyst tre vakter. Hver vakt trenger
nøyaktig én sykepleier.

Beskriv hvordan du avgjør om alle vaktene kan dekkes, og hvordan du finner en
konkret vaktliste.

Typiske feil

De to første koster hele oppgaven.

- Å blande pseudopolynomisk og NP-hardt. Dette er felle #7. At
Ford-Fulkerson er pseudopolynomisk, sier noe om algoritmen, ikke om
problemet. Maks-flyt ligger i P.
- Å glemme ryggkantene under forøkning. En forøkende sti kan gå bakover
langs en kant som bærer flyt, og da skal flyten på den kanten senkes.
Uten ryggkantene finner metoden ikke den maksimale flyten.
- Å tro at Edmonds-Karp bare er «Ford-Fulkerson med BFS for
bekvemmelighets skyld». Kravet er at stien er den korteste; det er
nettopp det som gir $O(VE^2)$ .
- Å oppgi bare flytverdien når min-snittet også er spurt om. Er begge
etterspurt, er begge en del av svaret — og snittet leses gratis av
restnettet til slutt.
- Å telle kanter fra $T$ til $S$ i snittkapasiteten. Bare kantene fra $S$
til $T$ teller. Kantene den andre veien påvirker $f(S,T)$ , men ikke
$c(S,T)$ .
- Å bruke et snitt med for høy kapasitet som «bevis». Beviset krever et
snitt som treffer flytverdien. Et dyrere snitt gir bare en øvre grense.
- Å tro at min-snittet er entydig. Det kan finnes flere snitt med samme
minimale kapasitet.

Og den gjennomgående: å skrive $\Theta$ der bare $O$ er vist. Begge
kjøretidene i dette kapitlet er $O$ -grenser, ikke tette.

Kjøretidene samlet

Dette er kapitlets puggeflate. Eksamen er hjelpemiddelfri, så tabellen må ligge
i hodet.

Algoritme	Kjøretid	Krav / egenskap
`Ford-Fulkerson` (vilkårlig sti)	$O(E\cdot\lvert f^*\rvert)$	pseudopolynomisk; krever heltallige kapasiteter for terminering
`Edmonds-Karp`	$O(VE^2)$	polynomisk; krever korteste forøkende sti, funnet med `BFS`
Én `BFS` i restnettet	$O(V+E)$	brukes både til å finne stien og til å lese av min-snittet
Én forøkning langs en sti	$O(V)$	stien har høyst $V-1$ kanter
Å lese av min-snittet	$O(V+E)$	én `BFS` fra $s$ etter at algoritmen har stoppet
Antall forøkninger i `Edmonds-Karp`	$O(VE)$	hver kant kan være flaskehals $O(V)$ ganger

Én presisering som er verdt å ta med seg. Det finnes raskere maks-flyt-
algoritmer enn Edmonds-Karp, men de er ikke pensum her. Det du skal kunne, er
at maks-flyt kan løses i polynomisk tid, og at

O(VE^2)

er tallet for
Edmonds-Karp.

Begrepsbank

Begrepsbanken er flashcard- og repetisjonsstoff — den gjentar det du nettopp
har lest. Hopp trygt over ved førstegangslesing; tidsanslaget for kapitlet
gjelder kjernestoffet.

`Ford-Fulkerson`-metoden

O(E\cdot\lvert f^*\rvert)

`Edmonds-Karp`

O(VE^2)

Forøkende sti

s

Flaskehals

den minste restkapasiteten blant kantene på en forøkende sti. Flyten økes med nøyaktig dette tallet, og minst én kant blir mettet. Med heltallige kapasiteter er flaskehalsen minst 1, og det er grunnen til at metoden terminerer.

Maks-flyt/min-snitt-teoremet

\max_f \lvert f\rvert = \min_{(S,T)} c(S,T)

Å lese av min-snittet

s

Pseudopolynomisk

O(E\cdot\lvert f^*\rvert)

Polynomisk algoritme

O(VE^2)

Felle #7 — pseudopolynomisk mot NP-hardt

å slutte fra «denne algoritmen er pseudopolynomisk» til «problemet er vanskelig». Ford-Fulkerson er pseudopolynomisk, men maks-flyt ligger i P fordi Edmonds-Karp er polynomisk. Skill mellom en egenskap ved algoritmen og en egenskap ved problemet.

Mettet kant

f(u,v) = c(u,v)

Ryggkant

(v,u)

Restnettet

G_f

c_f > 0

Snittkapasitet

S

Heltallsteoremet

er alle kapasitetene heltall, finnes en maksimal flyt der hver kant bærer et heltall. Det følger av at Ford-Fulkerson bare legger til heltallige flaskehalser. Dette er grunnen til at flyt er et tilordningsverktøy: en kant som bærer 1, betyr «denne tildelingen skjer».

Flytmodellering

å oversette et fordelingsproblem til et flytnett: kilde, ett nodesett for det som skal tildeles, ett for det de tildeles til, og sluk. Kapasiteten på kilde- og slukkantene koder øvre grenser; kantene i midten koder hvilke tildelinger som er tillatte. Rekonstruksjonen er å lese av hvilke midtkanter som bærer flyt.

Sjanger E — kjøretidskunnskap

O(VE^2)

Sjanger F — «stemmer dette?»

oppgavetypen der du får en påstand og skal ta stilling til den. Svarformen er ja eller nei først, deretter én presis setning. «Er Ford-Fulkerson polynomisk?» er den klassiske i denne delen — og svaret er nei, med ordet pseudopolynomisk i begrunnelsen.

Sjanger G — argument om vanskelighet

oppgavetypen der du skal si hva et argument faktisk viser, og hva det ikke viser. Svarformen er retningen, konsekvensen og det eksplisitte forbeholdet. Her er standardfeilen å slutte fra en treg algoritme til et hardt problem.

Repetisjonsoppgaver

Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.

Skolesaga er en uavhengig læringsressurs og er ikke tilknyttet eller godkjent av Norges teknisk-naturvitenskapelige universitet. Dette er ikke offisielt studiemateriell. Les mer.