4.1 Grafrepresentasjon, traversering og topologisk sortering

Nabomatrise vs. naboliste, `BFS`, `DFS` med kantklassifisering, og topologisk sortering via **synkende finish-tid**.

60 min

9 oppgaver

Grafrepresentasjontraverseringtopologisk sortering

Din fremgang i kapitlet

0 / 9 oppgaver

Kapitlets plass i kurset

Bygger på

3.5Køer, stakker, amortisert analyse og disjunkte mengder

Brukes videre i

4.2Minimale spenntrær — Prim og Kruskal 4.3Korteste vei fra én kilde — Dijkstra, Bellman-Ford, DAG 5.1Flytnett, restnett og snitt

En rutebilsjåfør, en montasjeleder og en driftsvakt stiller det samme spørsmålet
i tre forkledninger: hva henger sammen med hva, og i hvilken rekkefølge må jeg
ta det? Svaret er en graf og en traversering. Dette kapitlet gir deg de to
traverseringene hele resten av grafdelen hviler på, og den ene ordningen de
brukes til å lage.

Hvor ofte kommer det? Grafrepresentasjon og traversering er belagt i
82 % (14 av de 17 settene i grunnlaget), og topologisk sortering i
41 % (7 av de 17 settene). Grunnlaget er de 17 settene fra august 2015 til
august 2023 som er gjennomgått tema for tema — det er nevneren hver gang et
prosenttall dukker opp i denne boka.

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: BFS- eller DFS-rekkefølgen, d-verdiene eller
finish-tidene.
- sjanger D — definisjon med egne ord, altså én presis setning med
hovedpoenget først: «definér topologisk sortering».
- sjanger F — stemmer dette?, altså et påstandsspørsmål der du svarer
ja eller nei først og deretter én setning. Den faste fella er
«topologisk sortering ordner nodene etter starttid» (nei — synkende
finish-tid).

Prioritet: bør sitte. Traversering er ikke det aller første du pugger, men
det er fundamentet under korteste vei, spenntrær og flytnett. Sitter BFS og
DFS, får du billige poeng i fire senere kapitler.

Slik er kapitlet lagt opp (60 min):

#	Innhold	Tid
1	Nabomatrise mot naboliste — og når du velger hva	ca. 12 min
2	`BFS`: færrest kanter, lag for lag	ca. 14 min
3	`DFS`: klokka, finish-tidene og de fire kanttypene	ca. 16 min
4	Topologisk sortering via synkende finish-tid	ca. 14 min
5	Kjøretidstabell, begrepsbank og repetisjon	ca. 4 min

Forkunnskaper

- kap. 3.5 — køer og stakker. De to traverseringene
i dette kapitlet skiller seg fra hverandre på nøyaktig ett punkt: hvilken
beholder de tar den neste noden fra. BFS bruker en kø (først inn, først
ut), DFS bruker en stakk (sist inn, først ut) — og i praksis er stakken
rekursjonsstakken, altså at prosedyren kaller seg selv.
- Mengdelære — grafen skrives $G = (V, E)$ , altså et par av to
mengder: nodene $V$ og kantene $E$ . Trenger du en oppfriskning av
mengdenotasjonen bak den skrivemåten, ligger den der.
- Algoritmedefinisjon, pseudokode og kompleksitet (Big-O)
— et mykere første møte med $O$ -notasjon og med å lese pseudokode, hvis
kjøretidsuttrykkene under fortsatt kjennes uvante.

Du trenger ingen kjennskap til vektede grafer her. Kantene i dette kapitlet
har ingen tall på seg; vekter kommer i kap. 4.2 og
kap. 4.3.

Notasjons- og pseudokodeliste

Grafen på papiret: to måter å lagre den på (~12 min)

Et bysykkelselskap har 640 stativer og litt over 1 700 sykkelveistrekninger
mellom dem. Systemet skal svare på to slags spørsmål hele dagen: «går det en
strekning direkte fra stativ 88 til stativ 402?» og «hvilke stativer kan jeg
sykle til fra stativ 88?». De to spørsmålene trekker i hver sin retning, og
valget mellom dem er hele grunnen til at faget har to representasjoner.

En graf er bare noder og kanter, skrevet $G = (V, E)$ . Selve tegningen med
sirkler og streker er ikke noe datamaskinen har; den må ha grafen som tall i
minnet. Det finnes to standardformer, og eksamen forventer at du kjenner
styrkene og svakhetene til begge.

Vi skriver $V$ for antall noder og $E$ for antall kanter, rett inn i
kjøretidsuttrykkene: $\Theta(V + E)$ , $\Theta(V^2)$ . Det er skrivemåten
læreboka og løsningsforslagene bruker, og den du skal levere.

Graf, rettet og urettet

G = (V, E)

Nabomatrise

u

Naboliste

\Theta(V + E)

Glissen og tett graf

V(V-1)/2

✏️Eksempel 1: Hvilken representasjon skal bysykkelsystemet bruke?

Systemet har $V = 640$ stativer og $E = 1\,730$ strekninger, og skal gjøre to
ting: (i) svare på «finnes strekningen fra stativ $u$ til stativ $v$ ?» noen
tusen ganger i timen, og (ii) kjøre en traversering over hele nettet hvert
kvarter for å finne stativer som er blitt frakoblet.

Hvilken representasjon bør velges, og hva koster de to oppgavene i hver av dem?

Naboliste.

Plassen. Nabomatrisen bruker $640^2 = 409\,600$ celler. Nabolista bruker
$640$ hoder pluss $2 \cdot 1\,730 = 3\,460$ poster, altså $4\,100$ poster — rundt
hundre ganger mindre. Grafen er glissen: hvert stativ har i snitt
$2 \cdot 1730 / 640 \approx 5{,}4$ naboer av 639 mulige.

Traverseringen, som er den tunge jobben, er $\Theta(V + E) = \Theta(640 + 1730)$
med naboliste. Med nabomatrise må traverseringen lese hele raden til hver node
for å finne naboene, og blir $\Theta(V^2) = \Theta(409\,600)$ — over to
størrelsesordener dyrere.

Kantoppslaget er det eneste matrisen vinner: $O(1)$ mot «let gjennom
nabolista til $u$ », som i snitt er rundt 5 sammenligninger her. Noen tusen
oppslag i timen à 5 sammenligninger er ingenting mot en kvarterlig traversering
som blir hundre ganger dyrere.

Konklusjonen i én linje: naboliste, fordi grafen er glissen og
hovedoperasjonen er en traversering.

📝Oppgave 1

(Innstegsoppgave, sjanger D — definisjon med egne ord, altså én presis setning
med hovedpoenget først.) En sambandsgruppe har fem radiopunkter, og disse
direkte sambandene: A–B, A–C, B–C, B–D, C–E og D–E.

a) Skriv nabolista for grafen, med naboene i alfabetisk rekkefølge.
b) Hvor mange celler har nabomatrisen, og hvor mange av dem er 1?
c) Hva er plassforbruket til de to representasjonene uttrykt i $V$ og $E$ ?

📝Oppgave 2

Sjanger E

To grafer har begge $V = 2000$ noder. Graf 1 er et veinett
med $E = 4\,800$ kanter. Graf 2 er en interessekonflikt-graf der nesten alle par
er koblet, med $E = 1\,900\,000$ kanter.

a) Hvor mange celler bruker en nabomatrise for hver av dem?
b) Hvor mange poster bruker en naboliste for hver av dem, dersom grafene er
urettede?
c) Hvilken representasjon velger du for hver graf, og hva er det avgjørende
argumentet?

Bredde-først: færrest kanter, lag for lag (~14 min)

En beredskapsvakt skal varsle et nett av kontrollrom. Hvert rom kan ringe sine
naboer, og vakta vil vite hvor mange ledd varselet må gjennom for å nå fram til
hvert enkelt rom. Ikke hvor lang tid det tar, ikke hvor mange kilometer — hvor
mange ledd.

Det er akkurat det bredde-først-søket gjør. Det starter i kilden, tar alle
naboene først, deretter alle naboene til dem, og så videre. Nodene faller i
lag etter hvor mange kanter unna kilden de ligger, og feltet v.d holder
det tallet.

Merk deg dette nå, for det er en fast eksamensfelle: BFS gir korteste vei
målt i antall kanter, ikke i vekt. En omvei på tre korte strekninger kan
godt være lettere enn én lang direkte kant, og da svarer BFS feil på
vekt-spørsmålet. Vektede korteste veier krever Dijkstra eller Bellman-Ford
fra kap. 4.3.

📜Pseudokode-kontrakt: `BFS`

Antagelser om representasjon. Grafen

G = (V, E)

er gitt som nabolister;
Adj[u] gjennomløpes i den rekkefølgen lista er oppgitt. Hver node v har tre
felt: fargen v.farge (hvit = ikke oppdaget, grå = i køen, svart = ferdig),
avstanden v.d og forgjengeren v.pi. Køen er en FIFO-kø fra
kap. 3.5. Grafen kan være rettet eller urettet.

Prebetingelse: s er en node i G. Postbetingelse: for hver node v
som er nåbar fra s er v.d antall kanter i den korteste stien fra s til
v, og v.pi er nodens forgjenger i den stien. Noder som ikke er nåbare,
beholder v.d = uendelig og v.pi = NIL.

BFS(G, s)
  Input:  graf G som nabolister, kildenode s
  Output: v.d og v.pi satt for hver node v
  for hver node u i V minus {s}
      u.farge = hvit
      u.d     = uendelig
      u.pi    = NIL
  s.farge = graa
  s.d     = 0
  s.pi    = NIL
  Q = tom ko
  Enqueue(Q, s)
  while Q ikke er tom
      u = Dequeue(Q)
      for hver v i Adj[u]
          if v.farge == hvit
              v.farge = graa
              v.d     = u.d + 1
              v.pi    = u
              Enqueue(Q, v)
      u.farge = svart
  Kjoretid: Theta(V + E)

Grunnideen i én setning: køen holder alltid nodene i ikke-synkende
d-rekkefølge, så når en node blir oppdaget for første gang, er den oppdaget
langs en sti med færrest mulig kanter.

Kjøretid $\Theta(V + E)$ : hver node legges i køen og tas ut nøyaktig én
gang, siden fargen sperrer for gjentakelse, og nabolista til hver node
gjennomløpes nøyaktig én gang — summen av alle nabolistelengder er $E$ i en
rettet graf og $2E$ i en urettet.

✏️Eksempel 2: BFS gjennom kollektivnettet

Seks holdeplasser henger sammen slik nabolistene under viser. Rekkefølgen i
listene er den systemet faktisk lagrer, og den skal følges.

A: B, C
B: A, C, D
C: A, B, E
D: B, E, F
E: C, D, F
F: D, E

Kjør BFS fra A. Oppgi v.d for hver node og rekkefølgen nodene tas ut av
køen i.

Sporingstavlen. Én rad per gang en node tas ut av køen. Køen står oppgitt
etter hvert steg, med fronten først.

Steg	Tas ut av køen	`d`	Nye noder som legges i køen	Køen etter steget
1	`A`	0	B (d=1, pi=A), C (d=1, pi=A)	`B, C`
2	`B`	1	D (d=2, pi=B)	`C, D`
3	`C`	1	E (d=2, pi=C)	`D, E`
4	`D`	2	F (d=3, pi=D)	`E, F`
5	`E`	2	-	`F`
6	`F`	3	-	`(tom)`

På eksamen leverer du bare linja under — tavlen er her for å vise hvordan du
kommer dit.
A.d = 0, B.d = 1, C.d = 1, D.d = 2, E.d = 2, F.d = 3
Blir også besøksrekkefølgen etterspurt: A, B, C, D, E, F.
Legg merke til hvorfor E fikk d = 2 og ikke d = 3. E ble oppdaget
fra C i steg 3, ikke fra D i steg 4. Da D senere så på E, var E
allerede grå, og BFS rører ikke en node som er oppdaget. Det er nettopp det

som gjør at d-verdien blir den minste mulige.
Fellenote. Fellen her er å svare på et vekt-spørsmål med BFS-tallene.

BFS gir færrest kanter, ikke minst vekt: hadde strekningen A–C tatt 40

minutter og A–B–C 12 minutter til sammen, ville BFS fortsatt gitt C.d = 1

langs den trege kanten.

Typiske feil i BFS

- Å tro at BFS gir korteste vei i vekt. Den gir færrest kanter.
Kontrollen: står det tall på kantene i oppgaven, og spørres det om «korteste»
eller «billigste» vei, er BFS feil verktøy — da skal du til
kap. 4.3.
- Å oppdatere d på en node som allerede er oppdaget. Testen er
if v.farge == hvit, ikke «hvis den nye d er mindre». En node som er grå
eller svart, har allerede sin endelige d.
- Å oppgi $O(V^2)$ som kjøretid uten forbehold. Med nabolister er BFS
$\Theta(V + E)$ . $\Theta(V^2)$ er det du får hvis grafen er lagret som
nabomatrise, fordi du da må lese en hel rad for å finne naboene til én node.
Oppgi representasjonen når du oppgir kjøretiden.
- Å bytte om køen og stakken. BFS bruker kø (først inn, først ut). Bruker
du stakk, har du skrevet DFS — og fått en helt annen besøksrekkefølge.

📝Oppgave 3

Eksamensnivå, sjanger C

Et sykkelveinett har sju kryss med
nabolistene under. Rekkefølgen i listene skal følges.

A: B, D
B: A, C, E
C: B, F
D: A, E
E: B, D, F, G
F: C, E, G
G: E, F

Kjør BFS fra A. Oppgaven ber om d-verdiene og besøksrekkefølgen, ikke om
en forklaring av algoritmen.

📝Oppgave 4

Sjanger F

En student skriver: «Siden BFS finner korteste vei fra
kilden, kan vi bruke den til å finne den raskeste bussruten mellom to
holdeplasser når hver strekning har oppgitt kjøretid.»

Stemmer dette? Begrunn.

Dybde-først: klokka, tidene og de fire kanttypene (~16 min)

— naturlig pausepunkt —

Der BFS sprer seg utover i lag, går dybde-først-søket så langt det kan i
én retning før det snur. Det er akkurat oppførselen du får når en prosedyre
kaller seg selv: den nye noden tar over, og den forrige må vente til den nye er
ferdig med alt sitt.

Den ventingen er det som gjør DFS verdifullt. Underveis fører algoritmen en
klokke som tikker ett hakk hver gang noe skjer, og hver node får to
tidsstempler: ett når den blir oppdaget, og ett når den er helt ferdig.

To ord må på plass før pseudokoden, for de brukes uten forklaring i
oppgavetekstene:

- Finish-tid er tidspunktet DFS er ferdig med en node — ikke da den ble
funnet, men da den og alt som ligger under den er utforsket ferdig. Feltet
heter v.f.
- Kantklassifisering er å sette merkelapp på hver kant ut fra hva slags node
den peker på i det øyeblikket algoritmen ser på den. Fire merkelapper finnes,
og hvilken en kant får, avgjøres av fargen på nodene, ikke av hvordan grafen
ser ut på papiret.

Discover-tid og finish-tid

V

📜Pseudokode-kontrakt: `DFS`

Antagelser om representasjon. Grafen

G = (V, E)

er gitt som nabolister som
gjennomløpes i oppgitt rekkefølge, og den ytre løkka går gjennom nodene i
oppgitt rekkefølge. Hver node v har feltene v.farge, v.d, v.f og
v.pi. tid er en global teller. Merk at v.d her betyr discover-tid, ikke
avstand som i BFS.

Prebetingelse: ingen. Postbetingelse: hver node har fått v.d og v.f
med $1 \le v.d < v.f \le 2V$ , alle $2V$ tidene er forskjellige, og hver kant er
klassifisert.

DFS(G)
  Input:  graf G som nabolister
  Output: v.d, v.f og v.pi satt for hver node v
  for hver node u i V
      u.farge = hvit
      u.pi    = NIL
  tid = 0
  for hver node u i V
      if u.farge == hvit
          DFS-Visit(G, u)

DFS-Visit(G, u)
  tid     = tid + 1
  u.d     = tid
  u.farge = graa
  for hver v i Adj[u]
      if v.farge == hvit
          v.pi = u
          DFS-Visit(G, v)
  tid     = tid + 1
  u.f     = tid
  u.farge = svart
  Kjoretid totalt: Theta(V + E)

Grunnideen i én setning: en node blir svart først når hele det nåbare
området under den er ferdig utforsket, og derfor forteller finish-tidene noe om
avhengighetene i grafen som discover-tidene ikke gjør.

Kjøretid $\Theta(V + E)$ : de to initialiseringsløkkene er $\Theta(V)$ , og
DFS-Visit kalles nøyaktig én gang per node fordi noden farges grå med det
samme — summen av nabolistegjennomløpene over alle kallene er $\Theta(E)$ .

Den ytre løkka er ikke pynt. Den er grunnen til at kjøretiden har
$V$ -leddet: også noder ingen kan nå fra den første startnoden må innom. Uten den
ville DFS bare dekket ett område av grafen.

Kantklassifisering

Merkelappen DFS gir en kant u -> v ut fra fargen på v i det øyeblikket kanten blir sett på. - Trekant (tree edge): v var hvit, og DFS gikk langs kanten. Navnet betyr «kant i dybde-først-treet» — det har ingenting med geometriske trekanter å gjøre. - Tilbakekant (back edge): v var grå, altså en node algoritmen ennå står inne i. Kanten peker bakover til en forfar. - Forlengs kant (forward edge): v var svart og v.d > u.d — kanten peker framover til en etterkommer som allerede er ferdig. - Krysskant (cross edge): v var svart og v.d < u.d — kanten går til en node i en annen gren eller et annet tre, som ble ferdig før u ble oppdaget. Klassifiseringen avhenger av rekkefølgen på nabolistene og på den ytre løkka: samme graf kan gi ulike merkelapper med en annen rekkefølge. Ett unntak finnes, og det er det viktigste: finnes det en tilbakekant, finnes det en sykel — og omvendt, uansett rekkefølge.

✏️Eksempel 3: DFS med alle fire kanttypene

En rettet graf beskriver hvilke saksdokumenter som henviser til hvilke. Noden
A er hoveddokumentet.

A: B, C, D, E
B: E
C: E
D: F
E: B
F: (ingen)

Kjør DFS med den ytre løkka i rekkefølgen A, B, C, D, E, F. Oppgi v.d og
v.f for hver node, og klassifiser hver kant.

Sporingstavlen. Radene med klokkeslett i parentes er kanter som blir sett på
uten at klokka tikker.

Klokke	Hendelse	Hva skjer
1	oppdager `A`	`A.d` = 1, farge grå
(1)	ser på kanten `A->B`	B er hvit — trekant
2	oppdager `B`	`B.d` = 2, farge grå
(2)	ser på kanten `B->E`	E er hvit — trekant
3	oppdager `E`	`E.d` = 3, farge grå
(3)	ser på kanten `E->B`	B er grå — tilbakekant (sykel)
4	ferdig med `E`	`E.f` = 4, farge svart
5	ferdig med `B`	`B.f` = 5, farge svart
(5)	ser på kanten `A->C`	C er hvit — trekant
6	oppdager `C`	`C.d` = 6, farge grå
(6)	ser på kanten `C->E`	E er svart og `E.d`=3 er mindre enn `C.d`=6 — krysskant
7	ferdig med `C`	`C.f` = 7, farge svart
(7)	ser på kanten `A->D`	D er hvit — trekant
8	oppdager `D`	`D.d` = 8, farge grå
(8)	ser på kanten `D->F`	F er hvit — trekant
9	oppdager `F`	`F.d` = 9, farge grå
10	ferdig med `F`	`F.f` = 10, farge svart
11	ferdig med `D`	`D.f` = 11, farge svart
(11)	ser på kanten `A->E`	E er svart og `E.d`=3 er større enn `A.d`=1 — forlengs kant
12	ferdig med `A`	`A.f` = 12, farge svart

På eksamen leverer du bare linjene under — tavlen er her for å vise hvordan du
kommer dit.
Tidene, oppgitt som d/f: A: 1/12, B: 2/5, C: 6/7, D: 8/11, E: 3/4, F: 9/10
Kantklassifiseringen: A->B trekant, B->E trekant, E->B tilbakekant,
A->C trekant, C->E krysskant, A->D trekant, D->F trekant, A->E
forlengs kant
Hvorfor C->E og A->E får ulik merkelapp selv om begge peker på den samme
svarte noden: A ble oppdaget på tidspunkt 1, altså før E, så E ligger
under A i treet og kanten peker framover. C ble oppdaget på tidspunkt 6,
altså etter at E var ferdig, så kanten krysser over til en annen gren.
Sammenligningen er alltid mellom u.d og v.d.
Fellenote. Fellen er å lese av tallene i feil rekkefølge når oppgaven bare
spør om finish-tidene: da er svaret E: 4, B: 5, C: 7, F: 10, D: 11, A: 12 — og
ingenting mer.

Tilbakekant

\Theta(V + E)

📝Oppgave 5

Eksamensnivå, sjanger C

En rettet saksflyt har nabolistene under. Den ytre
løkka går i rekkefølgen A, B, C, D, E, F.

A: B, D
B: C
C: A, E
D: C, E
E: F
F: (ingen)

a) Oppgi v.d og v.f for hver node.
b) Hvilke noder har DFS ferdigstilt før D i det hele tatt blir oppdaget?

📝Oppgave 6

Eksamensnivå, sjanger C

Bruk grafen og tidene fra oppgave 5.

a) Klassifiser hver av de sju kantene som trekant, tilbakekant, forlengs
kant eller krysskant.
b) Hva forteller klassifiseringen deg om grafen har en sykel?

Topologisk sortering: rekkefølgen som holder (~14 min)

En montasjeleder på en trafostasjon har ni arbeidssteg og en liste over hva som
må være ferdig før hva. Ingen av kravene er tidsangivelser — de sier bare
«dette før dette». Spørsmålet er om det finnes en rekkefølge som holder alle
kravene, og i så fall hvilken.

Tegn hvert arbeidssteg som en node og hvert krav som en rettet kant fra det som
må komme først til det som må komme etterpå. Da er spørsmålet en topologisk
sortering av grafen. Og her kommer den ene setningen som er verdt mest i dette
kapitlet: den finner du ved å kjøre DFS og ordne nodene etter synkende
finish-tid.

Hvorfor virker det? Fordi en node først blir ferdig når alt den peker på er
ferdig. Da har alt som skal komme etter den, allerede fått en lavere
finish-tid — og «høyest finish-tid først» blir nettopp riktig rekkefølge.

Rettet asyklisk graf (DAG)

\Theta(V + E)

Topologisk sortering

\Theta(V + E)

📜Pseudokode-kontrakt: `Topological-Sort`

Antagelser om representasjon. G er en rettet asyklisk graf gitt som
nabolister. Vi bruker DFS fra kontrakten over, med den ene endringen at hver
node settes fremst i en lenket liste i det øyeblikket den ferdigstilles.
Lista må støtte innsetting fremst i

O(1)

Prebetingelse: G har ingen sykel. Er den betingelsen brutt, finnes det
ingen topologisk sortering, og algoritmen skal i stedet melde fra — noe den kan
gjøre gratis, siden DFS da vil finne en tilbakekant.
Postbetingelse: lista inneholder alle nodene, og for hver kant u -> v står
u før v.

Topological-Sort(G)
  Input:  rettet asyklisk graf G som nabolister
  Output: en lenket liste med alle nodene i topologisk orden
  L = tom lenket liste
  kjor DFS(G), men med denne linjen lagt til i DFS-Visit:
      naar u.f er satt (noden blir svart):
          sett u fremst i L
  return L
  Kjoretid: Theta(V + E)

Invarianten i én setning: når u settes fremst i lista, står allerede alle
noder som er nåbare fra u, i lista — de ble ferdige før u, og havner derfor
bak den.

Kjøretid $\Theta(V + E)$ : algoritmen er én DFS pluss én
innsetting-fremst per node, og hver innsetting er $O(1)$ , altså $\Theta(V)$ til
sammen. Å sortere etter finish-tid i etterkant er heller ikke nødvendig —
rekkefølgen faller ut av seg selv.

✏️Eksempel 4: Montasjerekkefølgen på trafostasjonen

Sju arbeidssteg A til G har disse kravene, oppgitt som nabolister der A: C, D
betyr at A må være ferdig før både C og D kan begynne:

A: C, D
B: D, E
C: F
D: F, G
E: G
F: (ingen)
G: F

Den ytre løkka i DFS går i rekkefølgen A, B, C, D, E, F, G.

a) Finn en topologisk sortering.
b) En kollega foreslår å bruke rekkefølgen nodene ble oppdaget i i
stedet. Vis at det ikke virker.

a) Sporingstavlen.

Klokke	Hendelse	Hva skjer
1	oppdager `A`	`A.d` = 1, farge grå
(1)	ser på kanten `A->C`	C er hvit — trekant
2	oppdager `C`	`C.d` = 2, farge grå
(2)	ser på kanten `C->F`	F er hvit — trekant
3	oppdager `F`	`F.d` = 3, farge grå
4	ferdig med `F`	`F.f` = 4, farge svart
5	ferdig med `C`	`C.f` = 5, farge svart
(5)	ser på kanten `A->D`	D er hvit — trekant
6	oppdager `D`	`D.d` = 6, farge grå
(6)	ser på kanten `D->F`	F er svart og `F.d`=3 er mindre enn `D.d`=6 — krysskant
(6)	ser på kanten `D->G`	G er hvit — trekant
7	oppdager `G`	`G.d` = 7, farge grå
(7)	ser på kanten `G->F`	F er svart og `F.d`=3 er mindre enn `G.d`=7 — krysskant
8	ferdig med `G`	`G.f` = 8, farge svart
9	ferdig med `D`	`D.f` = 9, farge svart
10	ferdig med `A`	`A.f` = 10, farge svart
11	oppdager `B`	`B.d` = 11, farge grå
(11)	ser på kanten `B->D`	D er svart og `D.d`=6 er mindre enn `B.d`=11 — krysskant
(11)	ser på kanten `B->E`	E er hvit — trekant
12	oppdager `E`	`E.d` = 12, farge grå
(12)	ser på kanten `E->G`	G er svart og `G.d`=7 er mindre enn `E.d`=12 — krysskant
13	ferdig med `E`	`E.f` = 13, farge svart
14	ferdig med `B`	`B.f` = 14, farge svart

Ingen tilbakekant ble funnet, så grafen er en DAG og en sortering finnes.
På eksamen leverer du bare linja under — tavlen er her for å vise hvordan du
kommer dit.
Synkende finish-tid: B (14), E (13), A (10), D (9), G (8), C (5), F (4)
altså rekkefølgen B, E, A, D, G, C, F.
Kontrollen du bør gjøre på papiret: gå gjennom hver kant og sjekk at den
peker framover. A->C: A på plass 3, C på plass 6. A->D: 3 før 4. B->D: 1
før 4. B->E: 1 før 2. C->F: 6 før 7. D->F: 4 før 7. D->G: 4 før 5.
E->G: 2 før 5. G->F: 5 før 7. Alle ni peker framover.
b) Discover-tidene gir rekkefølgen A (1), C (2), F (3), D (6), G (7),
B (11), E (12), altså A, C, F, D, G, B, E. Den er ulovlig, og det holder å
peke på én kant: D->F krever at D kommer før F, men F står på plass 3 og D på
plass 4. Tre andre kanter peker også bakover i denne rekkefølgen: B->D,
E->G og G->F.
Fellen er #11 — å blande topologisk sortering med starttid. Ordningen er
synkende finish-tid.
Merk at svaret ikke er entydig. Denne grafen har 21 gyldige topologiske
ordninger; DFS gir deg én av dem, og den er like riktig som de andre. Blir du
bedt om «en topologisk sortering», er én lovlig rekkefølge hele svaret.

Typiske feil

- Å sortere etter starttid. Felle #11 — å blande topologisk sortering
med starttid. Det er synkende finish-tid som gir ordningen. Kontrollen tar
ti sekunder: skriv opp rekkefølgen din og se om noen kant peker bakover.
- Å tro at svaret er entydig. De fleste DAG-er har mange gyldige ordninger.
Blir du bedt om «en topologisk sortering», er én lovlig rekkefølge hele
svaret; du skal ikke lete etter «den riktige».
- Å topologisk sortere en graf med sykel. Da finnes det ingen ordning.
DFS avslører det ved å finne en tilbakekant, og det svaret — «grafen har en
sykel, så ingen topologisk sortering finnes» — er det riktige.
- Å velge feil kanttype. Merkelappen bestemmes av fargen på noden kanten
peker på, ikke av hvordan grafen ser ut når den er tegnet pent. Forlengs kant
og krysskant skilles på om u.d er mindre eller større enn v.d.
- Å hoppe over den ytre løkka i DFS. Uten den blir bare det området som er
nåbart fra den første noden, dekket. I eksempelet over ville B og E aldri
fått tider, og sorteringen ville manglet to steg.

📝Oppgave 7

Sjanger D

a) Definér topologisk sortering.
b) Forklar i to setninger hvordan DFS gir en, og hvorfor det virker.
c) Hva er kjøretiden, og hva kreves av grafen?

📝Oppgave 8

Eksamensnivå, sjanger F

En kandidat skriver i besvarelsen
sin: «Topologisk sortering ordner nodene etter starttid fra DFS, altså etter
v.d stigende.»

a) Stemmer dette? Svar ja eller nei først.
b) Gi et konkret moteksempel eller en presis begrunnelse.
c) Hva er den riktige regelen?

📝Oppgave 9

Eksamensnivå, sjanger C

En godkjenningsflyt har sju trinn med disse kravene,
der A: B, E betyr at A må godkjennes før B og E:

A: B, E
B: C, F
C: D
D: (ingen)
E: C, F
F: D, G
G: (ingen)

Den ytre løkka går i rekkefølgen A, B, C, D, E, F, G.

a) Er dette en DAG? Begrunn med DFS.
b) Oppgi finish-tidene og en topologisk sortering.
c) Kan trinn E behandles før trinn B? Kan D behandles før F?

Kjøretidene samlet (~4 min)

Dette er puggeflaten fra kapitlet. Eksamen er uten hjelpemidler, så tabellen
skal sitte utenat.

Operasjon	Kjøretid	Plass	Krav og egenskap
Nabomatrise, kantoppslag	$O(1)$	$\Theta(V^2)$	best i tette grafer
Naboliste, kantoppslag	tid proporsjonal med graden til `u`	$\Theta(V+E)$	best i glisne grafer; standardvalget
Naboliste, gå gjennom naboene til `u`	proporsjonalt med antall naboer	—	dette er det traverseringene gjør
`BFS(G, s)`	$\Theta(V+E)$	$O(V)$ for køen	gir færrest kanter, ikke minst vekt
`DFS(G)`	$\Theta(V+E)$	$O(V)$ for rekursjonsstakken	gir `d`- og `f`-tider og kantklassifisering
`Topological-Sort(G)`	$\Theta(V+E)$	$O(V)$	krever DAG; synkende finish-tid
Sykeltest med `DFS`	$\Theta(V+E)$	$O(V)$	sykel finnes nøyaktig når en tilbakekant finnes

Alle kjøretidene forutsetter naboliste. Med nabomatrise blir både BFS og
DFS

\Theta(V^2)

, fordi hver node krever at du leser en hel rad for å finne
naboene. Oppgi derfor representasjonen når du oppgir kjøretiden — det er en
setning som ofte er forskjellen mellom full og delvis uttelling.

Begrepsbank

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

Grad, inn-grad og ut-grad

2E

Sti og sykel

\Theta(V + E)

Nåbarhet

s

`BFS`

\Theta(V + E)

`DFS`

\Theta(V + E)

`Topological-Sort`

\Theta(V + E)

Forgjengerfeltet `v.pi`

O(V)

BFS-treet og DFS-skogen

Trestrukturen pi -feltene danner etter en traversering. BFS fra én kilde gir ett tre som dekker alt nåbart derfra, og dybden til en node i treet er nøyaktig v.d . DFS med den ytre løkka gir én skog : ett tre per gang løkka måtte starte et nytt søk. Antall trær i skogen er antall ganger DFS-Visit ble kalt fra den ytre løkka.

Hvit, grå og svart

De tre tilstandene en node går gjennom under en traversering. Hvit = ikke oppdaget ennå. Grå = oppdaget, men ikke ferdigbehandlet (i køen i BFS, på rekursjonsstakken i DFS). Svart = ferdig. Fargen er det som gjør at en traversering terminerer i en graf med sykler, og i DFS er den også det som avgjør kantklassifiseringen. Et par grå noder forbundet med en kant betyr alltid en sykel.

Forlengs kant

En kant u -> v der v var svart og v.d > u.d, altså en snarvei ned til en node som allerede er ferdig utforsket lenger nede i samme tre. Forlengs kanter forekommer bare i rettede grafer, og de sier ingenting om sykler. Skillet mot krysskant er ren tallsammenligning: forlengs når u.d er minst, kryss når v.d er minst. Merkelappen avhenger av rekkefølgen på nabolistene — samme graf kan gi en annen klassifisering med en annen rekkefølge.

Krysskant

En kant u -> v der v var svart og v.d < u.d, altså en kant over til en node som ble ferdig før u i det hele tatt ble oppdaget. Krysskanter går enten mellom to grener i samme dybde-først-tre eller mellom to ulike trær i skogen. Som forlengs kanter sier de ingenting om sykler — det er kun tilbakekanten som gjør det. I en urettet graf finnes de ikke i det hele tatt: klassifiserer du hver kant den første gangen den blir sett på, får du bare trekanter og tilbakekanter.

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.