4.5 DRILL — Håndkjøring av grafalgoritmer

Full drill på sjanger C for grafdelen: `Kruskal`, `DAG-Shortest-Path`, `BFS`/`DFS`-orden, `Floyd-Warshall` (`d`/`π`), `Slow-APSP`, `Transitive-Closure`.

85 min

12 oppgaver

DRILLHåndkjøring av grafalgoritmer

Din fremgang i kapitlet

0 / 12 oppgaver

Kapitlets plass i kurset

Bygger på

4.4Alle-til-alle korteste vei

Brukes videre i

4.PPrøver til del 4: Grafalgoritmer: traversering, spenntrær og korteste vei

Grafdelen er den bredeste i faget. Traversering er registrert i 14 av de 17
settene i grunnlaget (82 %), minimale spenntrær i 14 av 17 (82 %), korteste vei
fra én kilde i 13 av 17 (76 %), alle-til-alle korteste vei i 11 av 17 (65 %) og
topologisk sortering i 7 av 17 (41 %). 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.

Sjangeren er én eneste:

- Sjanger C — håndkjøring, altså at du utfører en navngitt algoritme steg
for steg på papir og oppgir bare det etterspurte. Svarformatet skifter
fra algoritme til algoritme, og halve treningen ligger i å kjenne det igjen.

Prioritet: bør sitte. Grafhåndkjøring er mekanisk arbeid som gir sikre
poeng når rutinen er der, og som koster hele oppgaven når den ikke er det.

Svarformatene, samlet:

Algoritme	Du leverer
`MST-Kruskal`	kantene i den rekkefølgen de legges til, og hvilke som forkastes
`BFS`	`v.d` for hver node, i nodenes rekkefølge
`DFS`	discover- og finish-tid per node, eventuelt kantklassifiseringen
`Topological-Sort`	nodene i synkende finish-tid
`DAG-Shortest-Path`	`v.d` for hver node
`Floyd-Warshall`	den etterspurte matrisen for den etterspurte `k`
`Slow-APSP`	den etterspurte cellen
`Transitive-Closure`	den boolske matrisen

Slik er kapitlet lagt opp (85 min):

Innhold	Tid
Løsningsoppskriften	ca. 8 min
Den gjennomarbeidede eksamenscasen (`Kruskal`)	ca. 15 min
Drill på `Kruskal` og spenntrær	ca. 14 min
Drill på `BFS`, `DFS` og topologisk sortering	ca. 22 min
Drill på `DAG-Shortest-Path`	ca. 12 min
Drill på matrisealgoritmene	ca. 14 min

— naturlig pausepunkt — etter traverseringsdrillen. Matrisealgoritmene er en
egen type arbeid og kan tas i en egen økt.

Forkunnskaper

Dette kapitlet legger ikke til nytt stoff. Det gjør fire kapitlers teori til en
ferdighet. De tre nøkkelreglene du trenger i hånden, står her — resten finner
du i kapitlene:

- Slakkeregelen fra kap. 4.3: hvis
$d[u] + w(u,v) < d[v]$ , settes $d[v] = d[u] + w(u,v)$ og $\pi[v] = u$ . Alle
korteste-vei-algoritmene er varianter av når og hvor ofte denne regelen
brukes.
- Snittegenskapen fra kap. 4.2: den letteste kanten
over et snitt som respekterer valgene så langt, er trygg — den kan legges til
spenntreet uten å ødelegge muligheten for et minimalt resultat. Det er dette
som gjør Kruskal riktig.
- Finish-tid-regelen fra kap. 4.1: en topologisk
sortering er nodene i synkende finish-tid fra DFS. Ikke stigende, og
ikke discover-tid.

Øvrige forkunnskaper:

- kap. 4.1 — nabolister og nabomatrise, BFS, DFS
med discover- og finish-tid, kantklassifisering, Topological-Sort.
- kap. 4.4 — Floyd-Warshall, min-pluss-produktet og
Transitive-Closure.
- kap. 3.5 — Union-Find, som er syklustesten i
Kruskal.

Notasjons- og pseudokodeliste

📜Løsningsoppskriften for en grafhåndkjøring

Steg 1 — les grafen først, og skriv den om til den representasjonen
algoritmen bruker. Kruskal trenger en liste over kantene med vekter. BFS
og DFS trenger nabolistene, og rekkefølgen innenfor hver naboliste er en
del av oppgaven — den avgjør hvilket svar som er riktig. Matrisealgoritmene
trenger vektmatrisen.

Steg 2 — skriv ned hvilken rekkefølge algoritmen dikterer, før du begynner
å regne:

- Kruskal: kantene sortert stigende etter vekt. Ved lik vekt, bruk den
rekkefølgen oppgaven oppgir — eller alfabetisk, og si at du gjør det.
- BFS: FIFO-køen. Nodene forlates i den rekkefølgen de ble oppdaget.
- DFS: nabolistene, i den rekkefølgen de står. Klokka går fra 1 og telles opp
både ved oppdagelse og ved ferdigstilling.
- DAG-Shortest-Path: den topologiske rekkefølgen, som du må finne først.
- Floyd-Warshall: k fra 1 og oppover, med hele matrisen ferdig per k.

Steg 3 — utfør mekanisk. Skriv ned tilstanden etter hvert steg mens du
regner. Det er der delpoengene ligger hvis du bommer til slutt.

Steg 4 — oppgi kun det etterspurte, i formatet fra tabellen i
Eksamensvinkel-boksen over.

Steg 5 — kontroller. Hver algoritme har en gratis kontroll:

Algoritme	Kontroll
`Kruskal`	spenntreet skal ha nøyaktig $V-1$ kanter
`BFS`	ingen `v.d` kan avvike med mer enn 1 mellom to naboer
`DFS`	siste finish-tid skal være $2V$ ; hver node har ett par tider
topologisk sortering	hver kant skal peke framover i lista
`DAG-Shortest-Path`	ingen `d`-verdi kan bli lavere etter at noden er passert
`Floyd-Warshall`	diagonalen skal være 0 hele veien

Steg 6 — lever kort. Én linje per delspørsmål. Lange svar teller ikke
positivt, og de nitten andre oppgavene venter.

✏️Eksempel 1: Gjennomarbeidet eksamenscase med margnotater

Et fiberselskap skal knytte sammen sju knutepunkter A til G. Mulige
strekninger med kostnad:

A–B 4, A–C 3, B–C 2, B–D 6, C–D 3, C–E 7, D–E 5, D–F 9,
E–F 1, E–G 10, F–G 4.

Kjør MST-Kruskal og list kantene i den rekkefølgen de legges til. Ved lik
vekt behandles kantene alfabetisk. Oppgi også samlet vekt.

Steg 1 — sorter kantene stigende, med alfabetisk likhetsbryting:

E–F 1, B–C 2, A–C 3, C–D 3, A–B 4, F–G 4, D–E 5, B–D 6,
C–E 7, D–F 9, E–G 10.

Margnotat. Sorteringen er halve arbeidet, og den er verdt å skrive ned
ordentlig. To kanter med vekt 3 og to med vekt 4 — her må likhetsbrytingen
oppgis, ellers er svaret flertydig.

Steg 2 — gå gjennom listen og bruk syklustesten:

Kant	Vekt	Handling	Samlet vekt
E–F	1	legges til	1
B–C	2	legges til	3
A–C	3	legges til	6
C–D	3	legges til	9
A–B	4	forkastes (ville lagd en syklus)	9
F–G	4	legges til	13
D–E	5	legges til	18
B–D	6	forkastes (ville lagd en syklus)	18
C–E	7	forkastes (ville lagd en syklus)	18
D–F	9	forkastes (ville lagd en syklus)	18
E–G	10	forkastes (ville lagd en syklus)	18

Margnotat. Legg merke til A–B med vekt 4. På det tidspunktet ligger A,
B, C og D allerede i samme komponent, så kanten forkastes — selv om den
er billigere enn D–E, som legges til senere. Det er hele poenget med
Kruskal: prisen alene bestemmer ikke, det gjør prisen kombinert med
syklustesten.
Margnotat. Fra og med B–D er treet ferdig, og resten forkastes. En
gjennomkjøring kan stoppe når

V-1 = 6

kanter er lagt til — men på eksamen
lønner det seg å ta med de forkastede kantene med merking, siden oppgaven ofte
spør om nettopp dem.
Sluttilstanden — det du ville levert på eksamen:
Kantene i rekkefølge: E–F, B–C, A–C, C–D, F–G, D–E. Samlet vekt
18.

Margnotat. Kontrollen: 6 kanter for 7 noder, altså $V-1$ . Stemmer ikke det,
har du enten lagt til en kant for mye eller hoppet over en.
Margnotat om delvis uttelling. En håndkjøring som stopper halvveis, gir
uttelling for det som er riktig så langt. Skriv derfor ned kantene etter hvert
som de legges til — ikke bare det ferdige treet.

Drill: `Kruskal` og spenntrær (~14 min)

Tre oppgaver. Legg merke til at svarformatet skifter mellom dem.

📝Oppgave 1

Eksamensnivå, sjanger C

En urettet, vektet graf har nodene P, Q, R, S, T, U og kantene:

P–Q 5, P–R 8, Q–R 3, Q–S 6, R–T 2, S–T 4, S–U 9, T–U 7.

Kjør MST-Kruskal. List kantene i den rekkefølgen de legges til, og oppgi
samlet vekt.

📝Oppgave 2

Eksamensnivå, sjanger C…

Bruk grafen fra Eksempel 1 (A til G).

a) Hvilke kanter forkastes, og hvorfor?
b) En kandidat påstår at kanten A–B med vekt 4 må være med i ethvert
minimalt spenntre, siden det finnes dyrere kanter i treet. Stemmer det?

📝Oppgave 3

Eksamensnivå, sjanger E

a) Hva er kjøretiden til MST-Kruskal, og hvilket steg dominerer?
b) Hva er kjøretiden til MST-Prim med binærhaug?
c) Hvor mange kanter har et minimalt spenntre i en sammenhengende graf med

V

noder?

Drill: `BFS`, `DFS` og topologisk sortering (~22 min)

Fire oppgaver på den samme grafen. Nabolistene er oppgitt i den rekkefølgen
algoritmene skal følge — det er en del av oppgaven, og ulik rekkefølge gir ulikt
svar.

📝Oppgave 4

Eksamensnivå, sjanger C

En rettet graf har disse nabolistene, i den rekkefølgen de skal behandles:

- a: b, d
- b: c
- c: f
- d: b, e
- e: c, f
- f: ingen

Kjør BFS fra node a. Oppgi v.d for hver node.

📝Oppgave 5

Eksamensnivå, sjanger C

Bruk den samme grafen og de samme nabolistene.

Kjør DFS med ytterløkka i alfabetisk rekkefølge a, b, c, d, e, f. Klokka
starter på 0 og telles opp ved både oppdagelse og ferdigstilling.

Oppgi discover- og finish-tid for hver node.

📝Oppgave 6

Eksamensnivå, sjanger C

Bruk DFS-kjøringen fra forrige oppgave.

a) Klassifiser hver av de åtte kantene som trekant, forlengs kant,
krysskant eller tilbakekant.
b) Har grafen en sykel? Begrunn med ett ord fra svaret i a).

📝Oppgave 7

Eksamensnivå, sjanger C

Bruk DFS-kjøringen fra oppgave 5.

Oppgi en topologisk sortering av grafen, og forklar med én setning hvilken
regel du brukte.

Drill: `DAG-Shortest-Path` (~12 min)

To oppgaver. Algoritmen er den raskeste korteste-vei-algoritmen som finnes —
$\Theta(V+E)$ — men den virker bare på syklusfrie grafer.

📝Oppgave 8

Eksamensnivå, sjanger C

Den samme rettede grafen som over, nå med kantvekter:

$a \to b$ 4, $a \to d$ 2, $b \to c$ 5, $c \to f$ 3, $d \to b$ 1, $d \to e$ 7,
$e \to c$ 2, $e \to f$ 6.

Kjør DAG-Shortest-Path fra a, med den topologiske rekkefølgen du fant i
oppgave 7. Oppgi v.d for hver node.

📝Oppgave 9

Eksamensnivå, sjanger F…

Bruk resultatet fra forrige oppgave.

a) Hvilken sti gir $d[f]$ , og hvordan leser du den av?
b) Hvorfor er DAG-Shortest-Path $\Theta(V+E)$ mens Dijkstra er
$O(E\lg V)$ ?
c) Kunne du brukt DAG-Shortest-Path hvis en av kantvektene var negativ?

Drill: matrisealgoritmene (~14 min)

Tre oppgaver på en ny graf. Her er svarformatet en matrise eller én celle —
les nøye hvilket.

📝Oppgave 10

Eksamensnivå, sjanger C

En rettet, vektet graf har fire noder og kantene:

$1 \to 2$ (4), $1 \to 3$ (11), $2 \to 3$ (2), $2 \to 4$ (6), $3 \to 1$ (3),
$4 \to 3$ (1).

a) Skriv opp vektmatrisen $W = d^{(0)}$ .
b) Utfør runden med $k = 1$ i Floyd-Warshall, og oppgi $d^{(1)}$ .

📝Oppgave 11

Eksamensnivå, sjanger C

Fortsett fra $d^{(1)}$ i forrige oppgave, med den samme grafen.

Utfør runden med $k = 2$ , og oppgi både $d^{(2)}$ og $\pi^{(2)}$ .

📝Oppgave 12

Eksamensnivå, sjanger C

Bruk den samme grafen med fire noder.

a) Regn ut $l^{(2)}_{14}$ med min-pluss-produktet, og vis alle leddene.
b) Hva ville vanlig matriseprodukt gitt for den samme cellen, og hvorfor er
det galt her?

Typiske feil

De tre første koster hele oppgaven.

- Å bruke starttid i stedet for finish-tid i topologisk sortering. Dette er
felle #11. Regelen er synkende finish-tid. Kontrollen er at hver kant
skal peke framover i den ferdige listen.
- Å legge til en syklusskapende kant i Kruskal. Syklustesten er
Find-Set(u) != Find-Set(v), og den skal gjøres før kanten legges til.
Kontrollen er at treet skal ha nøyaktig $V-1$ kanter.
- Å bruke vanlig matriseprodukt i Slow-APSP. Produktet er min-pluss:
minimum av summer.
- Å ignorere rekkefølgen i nabolistene. For DFS og BFS er
naboliste-rekkefølgen en del av oppgaven, og et annet valg gir et annet
gyldig svar på et annet spørsmål.
- Å bruke Dijkstra på negative kantvekter. Dette er felle #8. På en
DAG med negative vekter er DAG-Shortest-Path det riktige valget, og den
bryr seg ikke om fortegnet.
- Å behandle nodene i feil rekkefølge i DAG-Shortest-Path. Uten topologisk
rekkefølge kan en node bli behandlet før den har fått sin endelige
d-verdi, og da er svaret galt.
- Å blande d-regelen og π-regelen i Floyd-Warshall, eller å arve
forgjengeren fra rad $i$ i stedet for rad $k$ .
- Å oppgi mer enn det som er spurt om. Ber oppgaven om v.d, er det én rad
med tall. Ber den om kantrekkefølgen i Kruskal, er det seks kantnavn.

Og den gjennomgående: å ikke skrive ned tilstanden underveis. Delvis riktig
håndkjøring gir delvis uttelling, men bare hvis mellomregningen finnes på
arket.

Kjøretidene du kan bli spurt om i en deloppgave

Algoritme	Kjøretid	Krav / egenskap
`BFS`	$\Theta(V+E)$	gir færrest kanter, ikke minst vekt; bruker FIFO-kø
`DFS`	$\Theta(V+E)$	gir discover- og finish-tid; tilbakekant betyr sykel
`Topological-Sort`	$\Theta(V+E)$	synkende finish-tid; krever DAG
`DAG-Shortest-Path`	$\Theta(V+E)$	krever DAG; tåler negative vekter
`Dijkstra` (binærhaug)	$O(E\lg V)$	krever ikke-negative vekter
`Bellman-Ford`	$\Theta(VE)$	tåler negative kanter; oppdager negative sykler
`MST-Kruskal`	$O(E\lg V)$	sortering + `Union-Find`; gir $V-1$ kanter
`MST-Prim` (binærhaug)	$O(E\lg V)$	ett tre som vokser fra rota
`Floyd-Warshall`	$\Theta(V^3)$	uavhengig av antall kanter; tåler negative kanter
`Slow-APSP`, ett produkt	$\Theta(V^3)$	min-pluss
`Transitive-Closure`	$\Theta(V^3)$	boolsk variant

Én presisering som er verdt å ta med seg. Fire av algoritmene er

\Theta(V+E)

, og det er ingen tilfeldighet: de besøker hver node og hver kant
nøyaktig én gang, uten prioritetskø. Logaritmefaktoren i Dijkstra, Kruskal
og Prim kommer fra sortering eller fra en prioritetskø — ikke fra selve
grafgjennomgangen.

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 `MST-Kruskal`

V-1

Svarformat for `BFS` og `DFS`

2V

Svarformat for en topologisk sortering

oppgi nodene i synkende finish-tid fra DFS . Kontrollen: hver kant skal peke framover i listen. Felle #11 bor her: stigende discover-tid gir et annet, og galt, svar.

Svarformat for `Floyd-Warshall`

oppgi den etterspurte matrisen for den etterspurte runden k . Bare celler der veien om k er kortere, endrer seg. Resten står uendret, i begge matrisene. Diagonalen skal være 0 hele veien — det er kontrollen.

Syklustesten i `Kruskal`

Find-Set(u) != Find-Set(v) — ligger endepunktene i ulike komponenter, kan kanten legges til. Testen gjøres før kanten legges til, og Union kalles etterpå. Uten testen ville algoritmen lagd sykler, og resultatet ville ikke vært et tre.

Slakking

d[u] + w(u,v) < d[v]

`DAG-Shortest-Path`

\Theta(V+E)

Kantklassifisering i `DFS`

d[u] < d[v]

Felle #11 — starttid mot finish-tid

topologisk sortering bruker synkende finish-tid, ikke stigende discover-tid. De to gir ulike svar på de fleste grafer, og bare det første er riktig. Kontrollen er å sjekke at hver kant peker framover i den ferdige listen.

Sjanger C — håndkjøring

oppgavetypen der du utfører en navngitt algoritme steg for steg og oppgir sluttilstanden. Svarformen skifter fra algoritme til algoritme, og halve treningen ligger i å kjenne den igjen. Delvis riktig gir delvis uttelling — skriv ned tilstanden underveis.

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.

4.5 DRILL — Håndkjøring av grafalgoritmer

Forkunnskaper

Drill: Kruskal og spenntrær (~14 min)

Drill: BFS, DFS og topologisk sortering (~22 min)

Drill: DAG-Shortest-Path (~12 min)

Drill: matrisealgoritmene (~14 min)

Kjøretidene du kan bli spurt om i en deloppgave

Begrepsbank

Drill: `Kruskal` og spenntrær (~14 min)

Drill: `BFS`, `DFS` og topologisk sortering (~22 min)

Drill: `DAG-Shortest-Path` (~12 min)