5.3 DRILL — Håndkjøring av maks-flyt og flyt-modellering

Drill på håndkjøring av `Ford-Fulkerson`/`Edmonds-Karp` (sjanger C) OG den første halvdelen av flyt-modelleringen (sjanger H): gjenkjenn et fordelings-/barriereproblem som flyt.

85 min

10 oppgaver

DRILLHåndkjøring av maks-flytflyt-modellering

Din fremgang i kapitlet

0 / 10 oppgaver

Kapitlets plass i kurset

Bygger på

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

Brukes videre i

5.PPrøver til del 5: Maksimal flyt

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. Flyt er
verktøyet i flest av de åpne designoppgavene på slutten av settet.

Kapitlet driller to sjangre, og de skrives ut i klarspråk her:

- Sjanger C — håndkjøring, altså at du utfører algoritmen steg for steg på
papir og oppgir bare sluttilstanden. For flyt er svarformen flytverdien,
og min-snittet når begge er spurt om.
- Sjanger H — åpen algoritmedesign, altså at du skisserer en algoritme på
fem til ti linjer. Her øver vi den første halvdelen: å kjenne igjen at et
innpakket problem er et flytproblem, og å bygge nettet. Hele designsjangeren
driller vi i kap. 8.2.

Høyeste prioritet — dette må sitte.

De to mønstrene du skal kjenne igjen på tre sekunder:

Innpakningen sier	Verktøyet er
«fordel A på B, med grenser for hvor mange hver kan ta»	maks-flyt
«finn den billigste barrieren som skiller X fra Y»	min-snitt

Slik er kapitlet lagt opp (85 min):

Innhold	Tid
Løsningsoppskriften, begge halvdelene	ca. 12 min
Gjennomkjørt håndkjøringscase med margnotater	ca. 15 min
Drill på håndkjøring	ca. 22 min
Gjennomkjørt modelleringscase med margnotater	ca. 14 min
Drill på modellering	ca. 22 min

— naturlig pausepunkt — etter håndkjøringsdrillen. Modelleringen er en helt

annen type arbeid og kan tas i en egen økt.

Forkunnskaper

Dette kapitlet legger ikke til nytt stoff. De fire reglene du trenger i hånden,
står her — resten finner du i kapitlene:

1. Restnettet fra kap. 5.1:
$c_f(u,v) = c(u,v) - f(u,v)$ framover, og $c_f(v,u) = f(u,v)$ på
ryggkanten. Bare kanter med $c_f > 0$ er med. En mettet kant gir
ingen framoverkant; en tom kant gir ingen ryggkant.
2. Forøkende sti og flaskehals: en sti fra $s$ til $t$ i $G_f$ , og den
minste restkapasiteten på den.
3. Min-snittet leses av til slutt: kjør én BFS fra $s$ i restnettet når
algoritmen har stoppet. Nodene den når, utgjør $S$ . Se
kap. 5.2.
4. Heltallsteoremet: med heltallige kapasiteter finnes en maksimal flyt der
hver kant bærer et heltall. Det er dette som gjør at flyten kan leses som en
tildeling.

Øvrige forkunnskaper:

- kap. 5.2 — Ford-Fulkerson, Edmonds-Karp,
maks-flyt/min-snitt-teoremet.
- kap. 4.1 — BFS, som er stivalget i
Edmonds-Karp.

Notasjons- og pseudokodeliste

📜Løsningsoppskriften — håndkjøring (sjanger C)

Steg 1 — tegn restnettet. Ikke prøv å holde det i hodet. For hver kant
skriver du opp framoverkanten med

c - f

og ryggkanten med

f

, og stryker
dem som blir 0.

Steg 2 — finn en forøkende sti. Bruker du Edmonds-Karp, skal den være
korteste, funnet med BFS. Naboene besøkes i den rekkefølgen oppgaven
oppgir — det er en del av oppgaven.

Steg 3 — finn flaskehalsen. Den minste restkapasiteten på stien.

Steg 4 — forøk. Legg flaskehalsen til på framoverkantene og trekk den
fra på kantene der stien gikk bakover. Det siste er den feilen som gjøres
oftest.

Steg 5 — gjenta til BFS ikke finner $t$ .

Steg 6 — les av min-snittet. Nodene BFS når fra $s$ i det siste
restnettet, utgjør $S$ . Kantene fra $S$ til $T$ er alle mettet, og summen av
kapasitetene deres skal være lik flytverdien. Stemmer ikke det, har du
regnet feil.

Steg 7 — lever. Flytverdien, og min-snittet når det er spurt om. Ikke hele
tabellen med mindre oppgaven ber om den.

📜Løsningsoppskriften — modellering (sjanger H)

Steg 1 — navngi det klassiske problemet. Les innpakningen og finn mønsteret:

Innpakningen	Problemet
noe skal fordeles på noe annet, med grenser per part	maks-flyt i et firelagsnett
«billigste barriere som skiller X fra Y»	min-snitt
«hvor mange kan tildeles samtidig»	maksimal matching, som er maks-flyt med kapasitet 1

Steg 2 — navngi paradigmet eksplisitt. Skriv «dette løses med maks-flyt» i
klartekst. Det er ett av leddene som gir uttelling.
Steg 3 — bygg konstruksjonen. Fire lag:
- kilden

s

;

- ett nodesett for det som skal tildeles;
- ett nodesett for det de tildeles til;

- sluket $t$ .

Kapasiteten fra $s$ til en venstre node er hvor mange den kan ta.
Kapasiteten fra en høyre node til $t$ er hvor mange den har plass til. En
kant i midten med kapasitet 1 betyr at nettopp den tildelingen er tillatt.
Steg 4 — kjør, og si hva flytverdien betyr. Er den lik antall enheter som

måtte plasseres, går regnestykket opp; er den lavere, finnes ingen fullstendig
tildeling.
Steg 5 — rekonstruér selve løsningen. Midtkantene som bærer flyt, er

tildelingen. Si eksplisitt at heltallsteoremet gir en heltallig flyt, slik
at hver midtkant bærer 0 eller 1 og avlesningen er entydig. Si også at
avlesningen koster $O(E)$ og ikke øker den asymptotiske kjøretiden.

Steg 6 — oppgi kjøretiden med $V$ og $E$ definert i problemets egne
størrelser.
Mangler ett av de fem leddene — problem, paradigme, konstruksjon,
rekonstruksjon, kjøretid — er svaret ufullstendig.

✏️Eksempel 1: Gjennomkjørt håndkjøring med margnotater

Et vannverk har pumpen $s$ , tre kummer $p$ , $q$ , $r$ og forbruket $t$ .
Kapasitetene, i liter per sekund, er

c(s,p) = 8    c(s,q) = 5    c(p,q) = 2    c(p,r) = 7
c(q,r) = 6    c(r,t) = 9    c(q,t) = 3

Kjør Edmonds-Karp fra nullflyten, med naboene i alfabetisk rekkefølge. Oppgi
maksimal flytverdi og et min-snitt.

Runde	Forøkende sti	Flaskehals	Flytverdi etterpå
1	$s \to q \to t$	3	3
2	$s \to p \to r \to t$	7	10
3	$s \to q \to r \to t$	2	12
4	ingen sti finnes i $G_f$	—	12

Margnotat. BFS finner korteste sti. I runde 1 er

s \to q \to t

på to
kanter, mens

s \to p \to r \to t

er på tre — derfor kommer den korte først,
selv om den bare gir 3 enheter. Å velge stien med størst flaskehals er en
annen algoritme, og den er ikke Edmonds-Karp.
Margnotat. I runde 3 er

q \to t

mettet, så BFS må gå

$s \to q \to r \to t$ . Restkapasiteten på $r \to t$ er da $9 - 7 = 2$ , og det
blir flaskehalsen.
Den endelige flyten:

f(s,p) = 7/8    f(s,q) = 5/5    f(p,q) = 0/2    f(p,r) = 7/7
f(q,r) = 2/6    f(r,t) = 9/9    f(q,t) = 3/3

Margnotat. Legg merke til at $p \to q$ ikke bærer noe. Ikke enhver kant må
brukes for at flyten skal være maksimal — flaskehalsen ligger et helt annet
sted.

Sluttilstanden — det du ville levert på eksamen:

Maks-flyt $\lvert f^*\rvert = 12$ . Min-snitt:

$S = \{p, q, r, s\}$ , $T = \{t\}$ ,
med $c(S,T) = 9 + 3 = 12$ .
Margnotat. Kontrollen tar fem sekunder: snittkapasiteten er

12, og flytverdien er

12. Like tall betyr at kjøringen er ferdig og riktig.
Ulike tall betyr at du har regnet feil et sted — og da vet du det før du
leverer.

Margnotat om delvis uttelling. En håndkjøring som stopper etter to runder,
gir uttelling for de to rundene. Skriv derfor ned sti og flaskehals for hver
runde mens du regner, ikke bare det endelige tallet.

Drill: håndkjøring (~22 min)

Fem oppgaver. Legg merke til at svarformatet skifter — noen ber om
flytverdien alene, andre om snittet i tillegg.

📝Oppgave 1

Eksamensnivå, sjanger C

Et flytnett har nodene $s$ , $p$ , $q$ , $r$ , $w$ , $t$ og kapasitetene

Kant	Kapasitet	Kant	Kapasitet
$s \to p$	7	$s \to q$	6
$p \to r$	5	$p \to w$	4
$q \to r$	3	$q \to w$	8
$r \to t$	6	$w \to t$	9

Kjør Edmonds-Karp med naboene i alfabetisk rekkefølge, og oppgi maksimal
flytverdi.

📝Oppgave 2

Eksamensnivå, sjanger C

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

c(s,u) = 4    c(s,v) = 9    c(u,w) = 6    c(v,u) = 3
c(v,w) = 2    c(w,t) = 5    c(v,t) = 7

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

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

📝Oppgave 3

Eksamensnivå, sjanger…

Bruk vanningsanlegget fra kap. 5.2, der maksimal flyt
er 18 og den siste forøkende stien var $s \to a \to b \to d \to c \to t$ med
flaskehals 1.

Anta i stedet at kanten $b \to d$ har kapasitet 9 i stedet for 10, mens alt
annet er uendret.

a) Hva blir maksimal flytverdi?
b) Hva blir min-snittet?

📝Oppgave 4

Eksamensnivå, sjanger F

En kandidat har kjørt Edmonds-Karp på et nett og fått flytverdi 15. Hun
finner et snitt med kapasitet 19 og konkluderer: «Flyten er maksimal, siden
$15 \le 19$ .»

Er konklusjonen riktig? Svar ja eller nei, og forklar hva som mangler.

📝Oppgave 5

Eksamensnivå, sjanger C…

Et flytnett har nodene $s$ , $x$ , $y$ , $t$ med kapasitetene

c(s,x) = 20    c(s,y) = 20    c(x,y) = 1
c(x,t) = 20    c(y,t) = 20

a) Hvor mange runder bruker Edmonds-Karp, og hva blir maksimal flyt?
b) Hvor mange runder kan Ford-Fulkerson med uheldig valg av sti bruke?
c) Hva illustrerer forskjellen?

Modellering: fra innpakning til flytnett (~14 min)

Den andre halvdelen av kapitlet handler om det som skjer før algoritmen: å
se at et problem i det hele tatt er et flytproblem.

Kjennetegnet er nesten alltid det samme. Noe skal fordeles på noe annet, hver
part har en øvre grense, og bare visse kombinasjoner er tillatt. Da bygger du
et nett i fire lag.

✏️Eksempel 2: Gjennomkjørt modelleringscase med margnotater

Et laboratorium har fem analyseinstrumenter og sju prøver som skal kjøres i
løpet av natten. Hver prøve kan kjøres på visse av instrumentene, ikke alle.
Hvert instrument rekker to prøver i løpet av natten.

Beskriv hvordan du avgjør om alle sju prøvene rekkes, og hvordan du finner en
konkret kjøreplan.

Steg 1 — det klassiske problemet. Prøver skal fordeles på instrumenter, hver
part har en grense, og bare visse par er tillatt. Dette er et
tilordningsproblem med kapasiteter, altså maks-flyt.

Margnotat. Å navngi problemet er ett av de fem leddene som gir uttelling.
«Dette er et flytproblem» er en halv linje, og den halve linja teller.

Steg 2 — paradigmet. Maksimal flyt i et firelagsnett. Skriv det eksplisitt.

Steg 3 — konstruksjonen.

- Kilde $s$ og sluk $t$ .
- Én node per prøve, med kant $s \to \text{prøve}$ og kapasitet 1 —
hver prøve skal kjøres nøyaktig én gang.
- Én node per instrument, med kant $\text{instrument} \to t$ og kapasitet
2 — hvert instrument rekker to prøver.
- En kant $\text{prøve} \to \text{instrument}$ med kapasitet 1 for hvert par
der prøven kan kjøres på instrumentet.

Margnotat. Legg merke til hvor grensene sitter. «Én gang per prøve» er
kapasiteten på kildekanten; «to per instrument» er kapasiteten på
slukkanten. Å bytte om de to er den vanligste modelleringsfeilen.

Margnotat. Midtkantene trenger bare kapasitet 1. Kapasiteten der koder ikke
en grense — den koder at dette paret er tillatt.

Steg 4 — kjør og tolk. Kjør Edmonds-Karp. Alle sju prøvene rekkes hvis og
bare hvis maksimal flyt er 7, altså at hver kildekant er mettet.

Er maksimal flyt 6, er svaret nei — og min-snittet forteller deg til og med
hvorfor: det peker ut den flaskehalsen som gjør det umulig.

Steg 5 — rekonstruér kjøreplanen. Midtkantene som bærer flyt 1, er
planen: prøve $i$ kjøres på instrument $j$ . Heltallsteoremet garanterer at
en maksimal flyt kan velges heltallig når alle kapasitetene er heltall, så hver
midtkant bærer enten 0 eller 1, og avlesningen er entydig. Den koster $O(E)$ og
øker ikke den asymptotiske kjøretiden.

Margnotat. Dette leddet er det som skiller et fullt svar fra et halvt.
Oppgaven ba om en kjøreplan, ikke om et ja eller nei — og da må du si
hvordan planen leses ut.

Steg 6 — kjøretiden. Nettet har $V = 7 + 5 + 2 = 14$ noder og $E = O(7 + 5 + k)$ kanter, der $k$ er antall tillatte prøve–instrument-par. Edmonds-Karp
gir $O(VE^2)$ .

Hele svaret, i eksamensform:

Dette er et tilordningsproblem med kapasiteter, og løses med maks-flyt. Bygg
et nett med kilde $s$ , én node per prøve (kant fra $s$ med kapasitet 1), én
node per instrument (kant til $t$ med kapasitet 2), og en kant med kapasitet
1 fra hver prøve til hvert instrument den kan kjøres på. Kjør Edmonds-Karp.
Alle prøvene rekkes hvis og bare hvis maksimal flyt er 7. Kjøreplanen leses
av som de midtkantene som bærer flyt; heltallsteoremet gir en heltallig flyt,
og avlesningen koster $O(E)$ . Kjøretid $O(VE^2)$ med $V = 14$ og
$E = O(12 + k)$ .

Åtte linjer. Det er lengden en sjanger H-oppgave skal ha.

Drill: modellering (~22 min)

Fem oppgaver. Alle er nyskrevne innpakninger av de samme to mønstrene.

📝Oppgave 6

Eksamensnivå, sjanger H

En idrettshall har $m$ treningstider ledig i uka. $n$ lag har hver oppgitt
hvilke tider de kan bruke, og hvert lag skal ha nøyaktig én tid. Hver tid kan
brukes av bare ett lag.

Beskriv hvordan du avgjør om alle lagene får en tid, og hvordan du finner
fordelingen.

📝Oppgave 7

Eksamensnivå, sjanger H

En kommune skal sette opp midlertidige flomsperrer. Kartet er et rutenett der
noen ruter er elvebredd og noen er sentrum. Å sette opp en sperre i en rute
koster et oppgitt beløp. Kommunen vil finne den billigste samlingen ruter
som gjør det umulig å komme fra elvebredden til sentrum.

Beskriv hvordan problemet løses.

📝Oppgave 8

Eksamensnivå, sjanger…

Et transportfirma har $n$ sjåfører og $m$ oppdrag. Hver sjåfør kan ta høyst to
oppdrag, og hvert oppdrag trenger nøyaktig én sjåfør. I tillegg gjelder: sjåfør
og oppdrag må høre til samme distrikt.

a) Bygg flytnettet.
b) En kollega foreslår å modellere distriktskravet som en kapasitet på
kildekanten. Er det riktig?

📝Oppgave 9

Eksamensnivå, sjanger…

Et datasenter har $n$ servere og $m$ jobber. Jobb $j$ krever $r_j$ kjerner, og
server $i$ har $k_i$ ledige kjerner. En jobb kan splittes på flere servere.
Alle jobber skal kjøres.

a) Bygg flytnettet.
b) Hva er forskjellen fra en vanlig matching, og hva betyr det for
avlesningen?

📝Oppgave 10

Eksamensnivå, sjanger F…

En kandidat modellerer et fordelingsproblem som maks-flyt, kjører
Edmonds-Karp, og skriver som hele svaret: «Maksimal flyt er 14, så svaret er
ja.»

a) Hva mangler i svaret?
b) Skriv om svaret slik at det er fullstendig, for oppgaven «tildel 14
vakter til 6 vikarer som hver kan ta høyst 3 vakter».

Typiske feil

De to første koster hele oppgaven.

- Å glemme ryggkantene under forøkning. Går den forøkende stien bakover
langs en kant, skal flyten der senkes med flaskehalsen. Uten det finner
ikke håndkjøringen den maksimale flyten.
- Å 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 det siste
restnettet.
- Å bruke stien med størst flaskehals i stedet for korteste sti.
Edmonds-Karp krever korteste sti, funnet med BFS. Andre valg gir
gyldige flyter, men det er en annen algoritme og et annet svar på
håndkjøringen.
- Å sette kapasitetene feil sted i en modellering. «Hvor mange hver kan
ta» hører på kildekanten; «hvor mange hver har plass til» hører på
slukkanten. Hvilke par som er tillatt, kodes ved at midtkanten finnes
eller ikke — ikke ved en kapasitet.
- Å glemme heltallsteoremet i modelleringssvaret. Det er det som gjør at
flyten kan leses som en tildeling, og det er ett av leddene som gir
uttelling.
- Å stoppe ved flytverdien i en designoppgave. Oppgaven ber om en
tildeling eller en plan, og da må du si hvordan den leses ut av
flyten. Å oppgi bare optimalverdien er felle #6.
- Å bruke et for dyrt snitt som bevis. Beviset krever et snitt som treffer
flytverdien.
- Å tro at en treg algoritme betyr et hardt problem. Felle #7 — se
kap. 5.2.

Og den gjennomgående: å skrive mer enn de fem leddene. Et designsvar er
fem til ti linjer. Lengre svar gir ingen ekstra uttelling.

Kjøretidene du kan bli spurt om i en deloppgave

Operasjon	Kjøretid	Krav / egenskap
`Edmonds-Karp`	$O(VE^2)$	korteste forøkende sti; polynomisk
`Ford-Fulkerson` (vilkårlig sti)	$O(E\cdot\lvert f^*\rvert)$	pseudopolynomisk; krever heltall for terminering
Én `BFS` i restnettet	$O(V+E)$	både stivalget og avlesningen av snittet
Å lese av tildelingen fra flyten	$O(E)$	øker ikke den asymptotiske kjøretiden
Todelt matching via flyt	$O(VE^2)$	alle kapasiteter 1
Min-snitt med nodekostnader	$O(VE^2)$	krever nodesplitting først

Én presisering som er verdt å ta med seg. Kjøretiden i et designsvar skal
oppgis i problemets egne størrelser: hvor mange noder og kanter nettet får
når det bygges av oppgavens

n

m

k

. Å skrive «

O(VE^2)

» uten å si hva

V

E

er i denne konstruksjonen, er et halvt svar.

Begrepsbank

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

Svarformat for en flyt-håndkjøring

oppgi flytverdien, og min-snittet når begge er spurt om. Kontrollen: snittkapasiteten skal være lik flytverdien. Skriv ned sti og flaskehals for hver runde underveis — delvis riktig håndkjøring gir delvis uttelling.

Å føre restnettet

c - f

Å forøke langs en sti

legg flaskehalsen til på framoverkantene, og trekk den fra på kantene der stien gikk bakover. Minst én kant blir mettet i hver forøkning. Fratrekket på ryggkantene er den vanligste feilen i denne håndkjøringen.

Modelleringsmalen

fire lag: kilde, ett nodesett for det som skal tildeles, ett for det de tildeles til, og sluk. Kapasiteten fra kilden koder hvor mange hver kan ta; kapasiteten til sluket koder hvor mange hver har plass til. Kantenes eksistens i midten koder hva som er tillatt — ikke en kapasitet.

Fordelingsmønsteret

«fordel A på B, med grenser for hvor mange hver kan ta» — kjennetegnet på et maks-flyt-problem. Alle tildelingene kan gjøres hvis og bare hvis maksimal flyt er lik antall enheter som måtte plasseres. Er alle kapasitetene 1, er problemet en ren maksimal matching.

Barrieremønsteret

«finn den billigste samlingen som gjør det umulig å komme fra X til Y» — kjennetegnet på et min-snitt -problem. Løses ved å kjøre maks-flyt og lese av snittet fra det siste restnettet. Ligger kostnaden på noder, splitt hver node i to med en indre kant som bærer kostnaden.

Nodesplitting

v

Rekonstruksjon fra en flyt

O(E)

Sjanger C — håndkjøring

oppgavetypen der du utfører algoritmen steg for steg og oppgir sluttilstanden. For flyt: flytverdien, og min-snittet når det er spurt om. Naboenes rekkefølge er en del av oppgaven når BFS brukes.

Sjanger H — åpen algoritmedesign

oppgavetypen der du skisserer en algoritme på fem til ti linjer. Fem obligatoriske ledd: navngi problemet, navngi paradigmet, konstruksjonen, rekonstruksjonen av selve løsningen, og kjøretiden. Mangler ett ledd, er svaret ufullstendig — og det er oftest rekonstruksjonen som glipper.

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.