4.2 Minimale spenntrær — Prim og Kruskal

`MST-Prim` og `MST-Kruskal`, snittegenskapen og hvorfor en letteste kant over et snitt er **trygg**.

55 min

8 oppgaver

Minimale spenntrærPrimKruskal

Din fremgang i kapitlet

0 / 8 oppgaver

Kapitlets plass i kurset

Bygger på

4.1Grafrepresentasjon, traversering og topologisk sortering

Et fiberselskap skal knytte sammen sju grender. De har kostnadsanslag for hver
mulige trasé, og ett krav: alle grendene skal henge sammen, og totalregningen
skal bli minst mulig. Det er hele problemet dette kapitlet løser — og det løses
av to algoritmer som ser helt ulike ut, men som bygger på nøyaktig samme
prinsipp.

Hvor ofte kommer det? Minimale spenntrær er belagt i 82 % (14 av de 17
settene i grunnlaget). Grunnlaget er de 17 settene fra august 2015 til august
2023 som er gjennomgått tema for tema.

Sjangrene du møter her, med kodene skrevet ut:

- sjanger C — håndkjøring, altså at du utfører algoritmen steg for steg og
oppgir bare sluttilstanden. Her: kjør MST-Kruskal og list kantene i den
rekkefølgen de legges til.
- sjanger D — definisjon med egne ord, altså én presis setning med
hovedpoenget først. Snittegenskapen og ordet trygg er en fast
definisjonsoppgave.
- sjanger F — stemmer dette?, altså ja eller nei først og så én setning.
Den faste fella her er «det minimale spenntreet er entydig» (nei — ikke når
kantvekter er like).

Prioritet: bør sitte. Kruskal-håndkjøring er nesten gratis poeng når du har
gjort den fem ganger, og snittegenskapen er den ene setningen som forklarer
hvorfor både Prim og Kruskal virker.

Slik er kapitlet lagt opp (55 min):

#	Innhold	Tid
1	Spenntre og minimalt spenntre	ca. 10 min
2	Snittegenskapen og hva «trygg» betyr	ca. 14 min
3	`MST-Kruskal` med `Union-Find`	ca. 14 min
4	`MST-Prim` med prioritetskø	ca. 12 min
5	Entydighet, kjøretidstabell og repetisjon	ca. 5 min

Forkunnskaper

- kap. 4.1 — grafer, nabolister og traversering. Her
får kantene i tillegg en vekt, altså et tall som sier hva kanten koster.
- kap. 3.5 — disjunkte mengder, som MST-Kruskal
bruker til å svare på «henger disse to nodene allerede sammen?».

Fra kap. 3.5 trenger du disse tre operasjonene, som
til sammen kalles Union-Find. Dette sto der:

Operasjon	Hva den gjør	Kjøretid
`Make-Set(x)`	lager en ny mengde som bare inneholder `x`; `x` blir sin egen representant	$O(1)$
`Find-Set(x)`	returnerer representanten for mengden `x` ligger i. To elementer er i samme mengde nøyaktig når `Find-Set` gir samme svar	nesten konstant
`Union(x, y)`	slår sammen mengdene til `x` og `y` til én	nesten konstant

Strukturen er en skog: hver mengde er et tre der hver node peker på
forelderen sin, og roten er representanten. Find-Set går oppover til roten;
Union henger den ene rota under den andre. Med de to standardgrepene — å
henge det lave treet under det høye, og å la Find-Set peke alle nodene den

passerer rett på rota — blir en følge av $m$ operasjoner så nær $O(m)$ at vi i
kjøretidsregnskapet under behandler hver operasjon som en konstant.
Slik brukes det i MST-Kruskal: hver node får sin egen mengde med
Make-Set. En kant mellom u og v lager en sykel nøyaktig når
Find-Set(u) == Find-Set(v), altså når de allerede henger sammen. Legger vi
kanten til, kaller vi Union(u, v).

- Potenser og logaritmer — hvis $\lg$ i uttrykket $O(E\lg V)$
fortsatt kjennes uvant. $\lg n$ betyr $\log_2 n$ , altså toerlogaritmen.

Notasjons- og pseudokodeliste

Billigst mulig nett som likevel henger sammen (~10 min)

Fiberselskapet har målt opp elleve mulige traseer mellom de sju grendene, med
hver sin gravekostnad. De trenger ikke alle. De trenger akkurat så mange at
signalet kommer fram overalt — og ikke én meter mer enn nødvendig.

Legg merke til at problemet har to krav som trekker mot hverandre. Alt skal
henge sammen, som presser antall traseer opp. Regningen skal være lav, som
presser den ned. Det viser seg at det finnes et eksakt svar på hvor de to
møtes: nettet skal være et tre, og det skal være det letteste treet som
finnes.

Ordet «tre» er ikke tilfeldig. Har du sju grender og bygger åtte traseer, har du
minst én rundtur — og en rundtur betyr at minst én trasé kan fjernes uten at noe
mister forbindelsen. Har du bare fem, faller nettet i to biter. Seks, altså
$V - 1$ , er svaret.

Spenntre

V

Minimalt spenntre (MST)

w(T) = \sum_{(u,v) \in T} w(u,v)

✏️Eksempel 1: Er dette et spenntre?

Fiberselskapets sju grender heter A til G, og de elleve mulige traseene med
kostnad i hundre tusen kroner er:

A-B 4    A-C 2    B-C 5    B-D 10
C-D 3    C-E 8    D-E 6    D-F 11
E-F 7    E-G 9    F-G 1

En saksbehandler foreslår disse fem traseene: A–C, C–D, A–B, D–E og E–F.

a) Er forslaget et spenntre?
b) Hva om han i tillegg tar med B–C?

a) Nei. Forslaget har fem kanter, og et spenntre over sju noder må ha

V - 1 = 6

. Følger du kantene, får du A, B, C, D, E og F knyttet sammen, men
G henger utenfor — ingen av de fem kantene rører G. Grenda ville stått uten
fiber.

b) Nei, og nå av motsatt grunn. Med B–C har forslaget seks kanter, altså
riktig antall, men de gale kantene: A–C, C–D, A–B og B–C danner rundturen
A, B, C, A. Da er det ikke et tre, og G er fortsatt ikke med.

Den korte kontrollen du kan gjøre på papiret: tell kantene, og sjekk at
tallet er $V - 1$ . Stemmer det ikke, er svaret nei uten mer arbeid. Stemmer det,
må du i tillegg sjekke at alt henger sammen — for $V - 1$ kanter er
nødvendig, men ikke tilstrekkelig.

📝Oppgave 1

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

a) Hva er et spenntre?
b) Hvor mange kanter har et spenntre i en graf med 12 noder?
c) En graf har 12 noder og 11 kanter, og henger sammen. Hva vet du da om
den?

Snittegenskapen: når er en kant trygg? (~14 min)

Begge MST-algoritmene bygger opp svaret én kant om gangen. Da trenger de en
regel som sier: denne kanten kan du legge til nå, uten fare for at du senere
angrer. Den regelen heter snittegenskapen, og den er kapitlets viktigste
setning.

Tenk deg at du deler grendene i to grupper — hvilke som helst to grupper, så
lenge begge er ikke-tomme og ingen grend er i begge. Den delingen kalles et
snitt. Noen traseer går innad i en gruppe; de bryr vi oss ikke om. Andre går
over delingen, fra den ene gruppen til den andre. Nettet må ha minst én slik
trasé, ellers henger ikke gruppene sammen.

Snittegenskapen sier: den letteste av traseene som krysser, kan du trygt
bygge. Men det gjelder bare hvis snittet er valgt slik at ingen av traseene du
allerede har bestemt deg for, krysser det. Den betingelsen er ikke pynt — uten
den er påstanden gal, og vi viser et konkret moteksempel om litt.

Snitt og kryssende kant

(S, T)

Snitt som respekterer en kantmengde

(S, T)

Trygg kant

A

📜Snittegenskapen

G = (V, E)

være en sammenhengende, urettet og vektet graf, og la

A

være en kantmengde som er del av et minimalt spenntre for

G

La $(S, T)$ være et snitt som respekterer $A$ — altså der ingen kant i
$A$ krysser snittet.

La $(u,v)$ være en letteste kant som krysser snittet, altså en kant med
minst mulig vekt blant alle som går mellom $S$ og $T$ .

Da er $(u,v)$ trygg for $A$ : mengden $A \cup \{(u,v)\}$ er fortsatt del
av et minimalt spenntre.

Ideen bak, i tre setninger. Anta at $A$ ligger i et MST $T^{*}$ som ikke
inneholder $(u,v)$ . Legger du $(u,v)$ til $T^{*}$ , får du en sykel, og den
sykelen må krysse snittet minst én gang til — la den andre kryssende kanten
hete $(x,y)$ . Bytt $(x,y)$ ut med $(u,v)$ : det er fortsatt et spenntre, det
inneholder fortsatt hele $A$ siden $(x,y)$ ikke lå i $A$ (snittet respekterer
$A$ ), og vekten er ikke større fordi $(u,v)$ var en letteste kryssende kant.

Betingelsen er ufravikelig. Sløyfer du «som respekterer $A$ », er setningen
rett og slett usann — se moteksempelet i Eksempel 2. Det er også det
løsningsforslagene ser etter i en definisjonsoppgave om trygge kanter: nevner du
ikke betingelsen, mangler hovedpoenget.

Både Prim og Kruskal er denne setningen i praksis. De velger bare snittet
sitt på hver sin måte: Prim lar $S$ være nodene i treet som vokser, Kruskal lar
$S$ være komponenten til den ene enden av kanten den vurderer.

✏️Eksempel 2: Snittegenskapen — og hva som skjer uten betingelsen

a) I fibergrafen fra Eksempel 1 har du så langt valgt traseene A–C (2) og
C–D (3). Sett

S = \{A, C, D\}

T = \{B, E, F, G\}

. Respekterer snittet
valgene dine? Hvilken kant er trygg?

b) Vis med et konkret eksempel at påstanden «den letteste kanten som krysser
et snitt er trygg» blir gal hvis vi dropper kravet om at snittet må
respektere valgene så langt.

a) Ja, snittet respekterer valgene. Både A–C og C–D har begge endene inne i

S

, så ingen valgt kant krysser.

De kryssende kantene er A–B (4), B–C (5), D–E (6), C–E (8), B–D (10) og
D–F (11). Den letteste er A–B med vekt 4, og den er derfor trygg: du kan
legge den til uten å ødelegge muligheten for å ende på et minimalt spenntre.
Grafen har nøyaktig ett minimalt spenntre — A–C (2), C–D (3), A–B (4), D–E (6),
E–F (7), F–G (1), med total vekt 23 — og A–B ligger i det.

b) Moteksempelet. Fire målestasjoner K, L, M og N med disse fem strekningene:

K-L 5    K-M 5    K-N 7    L-M 10    M-N 7

Grafen har to minimale spenntrær, begge med vekt 17: $\{K–L, K–M, M–N\}$ og
$\{K–L, K–M, K–N\}$ .

Anta at du har valgt $A = \{K–M\ (5),\ K–N\ (7)\}$ — en lovlig start, siden den
er del av det siste av de to trærne. Velg nå snittet $S = \{K, L, M\}$ ,
$T = \{N\}$ . Dette snittet respekterer ikke $A$ : kanten K–N krysser det.

De kryssende kantene er K–N (7) og M–N (7). Begge er letteste kryssende kant.
Velger du M–N, får du $A \cup \{M–N\} = \{K–M, K–N, M–N\}$ — og det er ingen
delmengde av noe spenntre i det hele tatt, for de tre kantene danner rundturen
K, M, N, K.

Poenget i én linje: uten betingelsen kan «letteste kryssende kant» være
nettopp den kanten som lukker en sykel med noe du allerede har valgt. Det er
derfor både Prim og Kruskal er nøye med hvilket snitt de bruker.

📝Oppgave 2

Sjanger D

Forklar MST-snittstrategien med egne ord.

a) Hva vil det si at en kant er trygg?
b) Formulér snittegenskapen presist, med alle betingelsene.
c) Hvorfor kan ikke betingelsen om at snittet respekterer valgene, sløyfes?

📜Når er det minimale spenntreet entydig?

Er alle kantvektene i grafen forskjellige, har grafen nøyaktig ett minimalt
spenntre. Er to eller flere kantvekter like, kan den ha flere — alle med samme
totale vekt.

Det motsatte gjelder ikke: like kantvekter kan gi flere minimale
spenntrær, men trenger ikke. En graf med to like vekter som ikke ligger på noen
felles sykel, har fortsatt ett eneste MST.

Et eksempel med to svar. Fire pumpestasjoner i en firkant, med
strekningene K–L (1), L–M (2), M–N (1) og K–N (2). Et spenntre må droppe
nøyaktig én av de fire kantene, og for å få minst mulig vekt må den som droppes
ha vekt 2. Det gir to forskjellige minimale spenntrær:

- K–L (1), L–M (2), M–N (1) — vekt 4
- K–L (1), K–N (2), M–N (1) — vekt 4

Begge er riktige svar. Blir du bedt om «et minimalt spenntre», leverer du ett av
dem; blir du bedt om «det minimale spenntreet» i en graf med like vekter, er
selve spørsmålet upresist, og du bør skrive at treet ikke er entydig.

På eksamen: påstanden «MST-et er entydig» er en klassisk sjanger F-oppgave.
Riktig svar er nei, med betingelsen: entydige kantvekter gir entydig
minimalt spenntre.

📝Oppgave 3

Sjanger F

En kandidat skriver: «En sammenhengende graf har alltid nøyaktig ett
minimalt spenntre.»

a) Stemmer dette? Svar ja eller nei først.
b) Gi et moteksempel med tall.
c) Under hvilken betingelse er påstanden riktig?

Kruskal: billigste kant først, hopp over dem som lukker en ring (~14 min)

— naturlig pausepunkt —

Den første av de to algoritmene tenker som en innkjøper: sorter alle traseene
etter pris, og gå gjennom lista fra billigst til dyrest. For hver trasé stiller
du ett spørsmål — henger disse to grendene allerede sammen? Gjør de det, er
traseen unødvendig, og du hopper over den. Gjør de det ikke, bygger du den.

Underveis har du altså ikke ett tre, men en samling atskilte biter som gradvis
smelter sammen. Det er nøyaktig det Union-Find fra
kap. 3.5 er laget for: Find-Set svarer på om to noder
er i samme bit, Union slår to biter sammen.

Snittegenskapen forklarer hvorfor det er riktig. Når MST-Kruskal vurderer den
letteste gjenværende kanten mellom to biter, kan du sette $S$ til den ene biten
og $T$ til resten. Alle kanter valgt så langt ligger inne i biter, så snittet
respekterer dem — og kanten er den letteste som krysser, siden alle lettere
kanter allerede er behandlet.

📜Pseudokode-kontrakt: `MST-Kruskal`

Antagelser om representasjon.

G = (V, E)

er urettet, sammenhengende og
vektet med

w(u,v)

. Kantene ligger i en liste som kan sorteres. Union-Find
er en skog av disjunkte mengder, én mengde per node i starten. Kanter med lik
vekt sorteres i en fast, oppgitt rekkefølge, slik at håndkjøringen blir
entydig — i denne boka alfabetisk på nodenavn.

Prebetingelse: grafen er sammenhengende. Postbetingelse: A er et
minimalt spenntre med nøyaktig $V - 1$ kanter.

MST-Kruskal(G, w)
  Input:  urettet sammenhengende vektet graf G = (V, E)
  Output: A, et minimalt spenntre
  A = tom mengde
  for hver node v i V
      Make-Set(v)
  sorter kantene i E stigende etter vekt w(u,v)
  for hver kant (u,v) i E, i sortert rekkefolge
      if Find-Set(u) != Find-Set(v)
          A = A forent med {(u,v)}
          Union(u, v)
  return A
  Kjoretid: O(E lg V)

Invarianten i én setning: før hver runde er A en delmengde av et minimalt
spenntre, og Union-Find-mengdene er nøyaktig komponentene A deler grafen i.

Kjøretid $O(E\lg V)$ : sorteringen av $E$ kanter koster $O(E\lg E)$ , og siden
$E \le V^2$ er $\lg E \le 2\lg V$ , så $O(E\lg E) = O(E\lg V)$ . De $V$ kallene til
Make-Set og de $O(E)$ kallene til Find-Set og Union koster til sammen
mindre enn dette. Sorteringen dominerer — det er det svaret en
kjøretidsoppgave er ute etter.

✏️Eksempel 3: Kruskal på fibernettet

Kjør MST-Kruskal på fibergrafen med de elleve traseene:

A-B 4    A-C 2    B-C 5    B-D 10
C-D 3    C-E 8    D-E 6    D-F 11
E-F 7    E-G 9    F-G 1

Kanter med lik vekt behandles alfabetisk. Oppgaven ber om kantene i den
rekkefølgen de legges til, ikke om en forklaring av algoritmen.

Kantene sortert stigende:

F–G (1), A–C (2), C–D (3), A–B (4), B–C (5), D–E (6), E–F (7), C–E (8),
E–G (9), B–D (10), D–F (11)

Sporingstavlen. Én rad per kant i sortert rekkefølge, uten unntak — også de
som forkastes.

Steg	Kant	Vekt	Avgjørelse	Komponentene etter steget
1	F–G	1	legges til	{A} {B} {C} {D} {E} {F,G}
2	A–C	2	legges til	{A,C} {B} {D} {E} {F,G}
3	C–D	3	legges til	{A,C,D} {B} {E} {F,G}
4	A–B	4	legges til	{A,B,C,D} {E} {F,G}
5	B–C	5	forkastes — lager sykel	{A,B,C,D} {E} {F,G}
6	D–E	6	legges til	{A,B,C,D,E} {F,G}
7	E–F	7	legges til	{A,B,C,D,E,F,G}
8	C–E	8	forkastes — lager sykel	{A,B,C,D,E,F,G}
9	E–G	9	forkastes — lager sykel	{A,B,C,D,E,F,G}
10	B–D	10	forkastes — lager sykel	{A,B,C,D,E,F,G}
11	D–F	11	forkastes — lager sykel	{A,B,C,D,E,F,G}

På eksamen leverer du bare linjene under — tavlen er her for å vise hvordan du
kommer dit.
Kantene i den rekkefølgen de legges til: F–G (1), A–C (2), C–D (3), A–B (4),
D–E (6), E–F (7)
Forkastet, i den rekkefølgen de vurderes: B–C (5), C–E (8), E–G (9), B–D (10),
D–F (11)
Total vekt:

1 + 2 + 3 + 4 + 6 + 7 = 23

Legg merke til to ting. For det første at treet er ferdig etter steg 7 — da
har det

V - 1 = 6

kanter — men algoritmen går videre gjennom lista og forkaster
resten. En implementasjon kan gjerne stoppe der; håndkjøringen din bør likevel
vise hvorfor de gjenværende kantene ikke kan brukes. For det andre at B–C (5)
forkastes selv om den er lettere enn både D–E (6) og E–F (7): rekkefølgen i

lista avgjør ikke alene, sykeltesten gjør.
Fellenote. Fellen er å oppgi alle kantene, også de forkastede, uten å merke

dem — eller å legge til en kant som lager en sykel. Sjekk til slutt at du har
nøyaktig $V - 1$ kanter.

📝Oppgave 4

Eksamensnivå, sjanger C

Et strømnett har seks
transformatorpunkter og disse ni mulige linjene, med kostnad i millioner:

A-B 7    A-C 3    B-C 5    B-D 2
C-D 8    C-E 6    D-E 9    D-F 4
E-F 1

Kjør MST-Kruskal. Oppgaven ber om kantene i den rekkefølgen de legges til,
samt hvilke som forkastes.

Prim: ett tre som vokser utover (~12 min)

Den andre algoritmen tenker som en entreprenør med én gravemaskin. Han starter i
én grend og bygger seg utover: i hver runde velger han den billigste traseen som
går fra det ferdige nettet til en grend som ennå ikke har fiber.

Forskjellen fra Kruskal er at Prim aldri har flere biter samtidig. Det er alltid
ett sammenhengende tre som vokser. Til gjengjeld må han hele tiden vite hvilken
node utenfor treet som er billigst å hente inn, og det er en jobb for en
prioritetskø: hver node utenfor treet har et felt key med vekten på den
letteste kjente kanten inn til treet, og Extract-Min gir noden med lavest
key.

Snittegenskapen igjen: la $S$ være nodene i treet og $T$ resten. Ingen valgt
kant krysser, siden alle valgte kanter ligger inne i treet — så snittet
respekterer valgene, og den letteste kryssende kanten er trygg. Det er nøyaktig
den kanten Extract-Min peker ut.

📜Pseudokode-kontrakt: `MST-Prim`

Antagelser om representasjon.

G = (V, E)

er urettet, sammenhengende og
vektet, gitt som nabolister. Hver node v har feltene v.key og v.pi. Q er
en prioritetskø over nodene, ordnet etter key, med Extract-Min og
Decrease-Key i

O(\lg V)

hver med binærhaug. Ved lik key bryter vi likhet
alfabetisk på nodenavn, slik at håndkjøringen blir entydig.

Prebetingelse: grafen er sammenhengende, og r er en node i den.
Postbetingelse: pi-feltene beskriver et minimalt spenntre: kantene
$(v, v.\pi)$ for alle $v$ unntatt rota r.

MST-Prim(G, w, r)
  Input:  urettet sammenhengende vektet graf G, rotnode r
  Output: v.pi for hver node, som til sammen gir et minimalt spenntre
  for hver node u i V
      u.key = uendelig
      u.pi  = NIL
  r.key = 0
  Q = alle noder i V
  while Q ikke er tom
      u = Extract-Min(Q)
      for hver v i Adj[u]
          if v er i Q og w(u,v) < v.key
              v.pi  = u
              Decrease-Key(Q, v, w(u,v))
  Kjoretid: O(E lg V)

Invarianten i én setning: før hver runde er kantene $(v, v.\pi)$ for nodene
som ikke står i Q, del av et minimalt spenntre, og v.key er vekten på den
letteste kanten fra treet til v for alle v som fortsatt står i Q.

Kjøretid $O(E\lg V)$ : Extract-Min kalles $V$ ganger à $O(\lg V)$ , altså
$O(V\lg V)$ , og Decrease-Key kalles høyst én gang per kantpost, altså
$O(E)$ ganger à $O(\lg V)$ . Summen er $O(V\lg V + E\lg V) = O(E\lg V)$ for en
sammenhengende graf, der $E \ge V - 1$ .

Rota spiller ingen rolle for svaret. Starter du et annet sted, får du
kantene i en annen rekkefølge, men — når kantvektene er entydige — det samme
treet.

✏️Eksempel 4: Prim på fibernettet, med rot A

Kjør MST-Prim på fibergrafen fra Eksempel 1 med rota A. Oppgi hvilken node
Extract-Min gir i hver runde, hvilken kant som blir med i treet, og
key-verdiene underveis.

A-B 4    A-C 2    B-C 5    B-D 10
C-D 3    C-E 8    D-E 6    D-F 11
E-F 7    E-G 9    F-G 1

Sporingstavlen. key-kolonnen viser verdiene rett etter runden; en strek
betyr at noden er tatt ut av køen.

Runde	`Extract-Min` gir	Kant som blir med i treet	Oppdateringer	`key` for nodene som fortsatt står i køen
1	`A`	-	`B.key`: uendelig til 4, `B.pi` = A; `C.key`: uendelig til 2, `C.pi` = A	A=-, B=4, C=2, D=uendelig, E=uendelig, F=uendelig, G=uendelig
2	`C`	A–C (2)	`D.key`: uendelig til 3, `D.pi` = C; `E.key`: uendelig til 8, `E.pi` = C	A=-, B=4, C=-, D=3, E=8, F=uendelig, G=uendelig
3	`D`	C–D (3)	`E.key`: 8 til 6, `E.pi` = D; `F.key`: uendelig til 11, `F.pi` = D	A=-, B=4, C=-, D=-, E=6, F=11, G=uendelig
4	`B`	A–B (4)	ingen	A=-, B=-, C=-, D=-, E=6, F=11, G=uendelig
5	`E`	D–E (6)	`F.key`: 11 til 7, `F.pi` = E; `G.key`: uendelig til 9, `G.pi` = E	A=-, B=-, C=-, D=-, E=-, F=7, G=9
6	`F`	E–F (7)	`G.key`: 9 til 1, `G.pi` = F	A=-, B=-, C=-, D=-, E=-, F=-, G=1
7	`G`	F–G (1)	ingen	A=-, B=-, C=-, D=-, E=-, F=-, G=-

På eksamen leverer du bare linjene under — tavlen er her for å vise hvordan du
kommer dit.
Kantene i den rekkefølgen Prim legger dem til: A–C (2), C–D (3), A–B (4),
D–E (6), E–F (7), F–G (1)
Forgjengerne: A.pi = NIL, B.pi = A, C.pi = A, D.pi = C, E.pi = D,
F.pi = E, G.pi = F
Total vekt:

2 + 3 + 4 + 6 + 7 + 1 = 23

Samme tre, annen rekkefølge. Kruskal i Eksempel 3 fant nøyaktig de samme

seks kantene, men i rekkefølgen F–G, A–C, C–D, A–B, D–E, E–F. Det er ventet:
grafen har entydige kantvekter, og da er det minimale spenntreet entydig.

Rekkefølgen kantene velges i, er derimot algoritmens egen.
Legg merke til runde 6. Da F ble hentet inn, falt G.key fra 9 til 1,

fordi F–G koster 1. Prim ser ikke framover — den oppdaget den billigste kanten i
hele grafen først i nest siste runde. Kruskal tok den først. Begge lander likevel

på 23, og det er snittegenskapen som garanterer det.

Fellenote. Fellen er å oppdatere key for en node som allerede er tatt ut av
køen. Testen i pseudokoden er if v er i Q, ikke bare «hvis vekten er lavere» —
en node som er hentet inn i treet, er ferdig.

📝Oppgave 5

Eksamensnivå, sjanger C

Bruk strømnettet fra oppgave 4:

A-B 7    A-C 3    B-C 5    B-D 2
C-D 8    C-E 6    D-E 9    D-F 4
E-F 1

Kjør MST-Prim med rota A. Oppgaven ber om rekkefølgen Extract-Min
henter nodene i, og kantene som velges — ikke om en forklaring av algoritmen.

📝Oppgave 6

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, og hvilke to
operasjonene utgjør den?
c) Hvorfor holder det ikke å bruke en vanlig usortert liste i stedet for
Union-Find i Kruskal?

Typiske feil

- Å tro at det minimale spenntreet er entydig. Det er det bare når alle
kantvektene er forskjellige. Skriv betingelsen — det er nettopp den som
skiller et fullt svar fra et halvt.
- Å legge til en kant som lager sykel i Kruskal. Kontrollen er Find-Set(u)
mot Find-Set(v), ikke øyemål på tegningen. Tell til slutt: har du flere enn
$V - 1$ kanter, har du lagt til minst én for mye.
- Å liste alle kantene uten å merke de forkastede. Håndkjøringsoppgaven ber
om kantene i den rekkefølgen de legges til. Tar du med de forkastede uten
å merke dem, er svaret galt.
- Å hevde snittegenskapen uten betingelsen. «Den letteste kanten over et
snitt er trygg» er en ufullstendig — og som Eksempel 2 viser, gal — påstand.
Snittet må respektere kantene du har valgt.
- Å blande spenntre med et vilkårlig tre. Kantene må være grafens egne, og
alle noder må være med. En «snarvei» mellom to noder som ikke har en kant
mellom seg, finnes ikke.
- Å oppdatere key i Prim for en node som er tatt ut av køen. Testen er
if v er i Q. En node som er hentet inn i treet, har fått sin endelige kant.

📝Oppgave 7

Eksamensnivå, sjanger C

Fire pumpestasjoner er knyttet sammen slik:

K-L 1    L-M 2    M-N 1    K-N 2

a) Kjør MST-Kruskal med alfabetisk likhetsbryting, og oppgi kantene i den
rekkefølgen de legges til.
b) Hvor mange minimale spenntrær har grafen, og hva er vekten til hvert av
dem?
c) Hva ville skjedd med svaret ditt i a) hvis likhetsbrytingen hadde vært
motsatt alfabetisk?

📝Oppgave 8

Eksamensnivå, sjanger C

Fem grender skal knyttes sammen med fiber. Traseene
og kostnadene er:

A-B 2    A-C 6    B-C 3    B-D 8
C-D 5    C-E 9    D-E 7

Kommunen har allerede gravd grøfta mellom C og E, så den traseen må være med
i nettet uansett hva den koster.

a) Hva er det billigste nettet uten den bindingen?
b) Hvordan kan du bruke MST-Kruskal til å finne det billigste nettet som
inneholder C–E, uten å endre algoritmen? Kjør det.
c) Hva koster bindingen?

Kjøretidene samlet (~5 min)

Algoritme/operasjon	Kjøretid	Hva som dominerer	Krav og egenskap
`MST-Kruskal`	$O(E\lg V)$	sorteringen av kantene	trenger `Union-Find`; bygger flere biter som smelter sammen
`MST-Prim` med binærhaug	$O(E\lg V)$	$E$ kall til `Decrease-Key`	trenger prioritetskø; bygger ett sammenhengende tre
`Make-Set`, `Find-Set`, `Union`	nesten konstant hver	—	fra kap. 3.5; svarer på «henger disse sammen?»
`Extract-Min`, `Decrease-Key`	$O(\lg V)$ hver	—	binærhaug fra kap. 3.1
Sjekk om en kantmengde er et spenntre	$\Theta(V + E)$	én traversering	tell kantene ( $V-1$ ) og sjekk at alt henger sammen

Begge algoritmene er $O(E\lg V)$ , så kjøretiden alene skiller dem ikke.
Forskjellen er praktisk: Kruskal vil ha kantene i en liste som kan sorteres,
Prim vil ha nabolister og en prioritetskø. Er kantene allerede sortert, er
Kruskal raskere; er grafen tett, gjør Prim færre operasjoner på hver node.
Merk O framfor \Theta. Vi skriver

O(E\lg V)

fordi begge algoritmene
kan stoppe tidlig i heldige tilfeller — Kruskal når treet har

V - 1

kanter,

lenge før lista er gjennomgått. Uttrykket er en øvre grense som alltid holder,
og det er det svaret en kjøretidsoppgave er ute etter.

Begrepsbank

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

`MST-Kruskal`

O(E\lg V)

`MST-Prim`

O(E\lg V)

`Union-Find` (disjunkte mengder)

Datastrukturen som holder styr på hvilke elementer som ligger i samme mengde, uten at mengdene overlapper. Fra kap. 3.5 . Representeres som en skog : ett tre per mengde, hver node peker på forelderen, roten er representanten. Med de to standardgrepene — å henge det lave treet under det høye, og å la Find-Set peke nodene rett på rota — er en følge av operasjoner så nær lineær at hver operasjon regnes som nesten konstant. I MST-Kruskal er den sykeltesten.

`Make-Set`, `Find-Set` og `Union`

De tre operasjonene på disjunkte mengder. Make-Set(x) lager en ny mengde med bare x . Find-Set(x) gir representanten for mengden x ligger i — to elementer er i samme mengde nøyaktig når svarene er like. Union(x, y) slår de to mengdene sammen. I MST-Kruskal kalles Make-Set én gang per node, Find-Set to ganger per kant og Union én gang per valgt kant.

Prioritetskø

O(\lg V)

`key`- og `pi`-feltene i Prim

\infty

Skog

V

Sammenhengende graf

\Theta(V + E)

Vektfunksjonen

w(u,v)

u

Antall kanter i et tre

V

Grådig algoritme

En algoritme som tar det beste valget her og nå, uten å gå tilbake på det senere. Både MST-Prim og MST-Kruskal er grådige: de tar alltid den letteste tilgjengelige kanten. Grådighet gir ikke alltid riktig svar — for de fleste problemer gjør den ikke det — men her gjør den det, og snittegenskapen er beviset . Den sier nøyaktig at det grådige valget er trygt.

Entydighet av minimalt spenntre

Et minimalt spenntre er entydig når alle kantvektene i grafen er forskjellige. Er to kantvekter like, kan grafen ha flere minimale spenntrær — alle med samme totale vekt. Den totale vekten er alltid entydig; det er utvalget av kanter som kan variere. Derfor sier oppgavetekster «finn et minimalt spenntre», og derfor oppgir håndkjøringsoppgaver en likhetsbryting.

Letteste kryssende kant

Blant alle kantene som krysser et snitt, en av dem med minst vekt. Ordet «en av dem» er med vilje: er det uavgjort mellom to kanter, er begge en letteste kryssende kant, og begge er trygge. Det er dette som gjør at en graf med like kantvekter kan ha flere minimale spenntrær. MST-Prim finner den med Extract-Min; MST-Kruskal finner den ved at kantene behandles i sortert rekkefølge.

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.