6.1 Topologisk sortering og DAG-egenskaper

Topologisk sortering med Kahns algoritme (inngrad-0-kø) og sykeldeteksjon i rettet graf — det foretrukne verktøyet for avhengighetsproblemer.

45 min

7 oppgaver

Topologisk sorteringDAG-egenskaper

Din fremgang i kapitlet

0 / 7 oppgaver

Kapitlets plass i kurset

Bygger på

5.2BFS og DFS — traversering

Brukes videre i

6.2Korteste vei — BFS, Dijkstra, DAG og reversert graf

Topologisk sortering er med i 5 av de 7 settene i arkivet (71 %), og den kommer
i to former:

- Sjanger H — grafalgoritme i pseudokode, altså at du selv skriver algoritmen
og oppgir kjøretiden. Innpakningen er nesten alltid den samme: et sett
avhengigheter, og spørsmålet «i hvilken rekkefølge kan dette gjøres — eller
er det umulig?»
- Sjanger F — matriseavkryssing, altså at du krysser av hvilken algoritme som
passer hvilken graftype. Der dukker topologisk sortering opp som svaret på
«korteste vei i en vektet DAG», som du møter i
kap. 6.2.

Det er verdt å merke seg mønsteret, for det er halve jobben på eksamen: ser du
ordene «avhengigheter», «må gjøres før», «installasjonsrekkefølge» eller «finnes
det en sirkulær avhengighet?», er svaret topologisk sortering. Du trenger ikke
oppfinne noe — du skal gjenkjenne, skrive ned Kahns algoritme og oppgi
$O(|V| + |E|)$ .

Prioritet: kunne (nivå 2 av tre — «må sitte» er nivå 1, «kjenne til» er
nivå 3). Det betyr at du skal kunne utføre og skrive algoritmen sikkert, men at
dette ikke er et av de fire temaene som kommer i hvert eneste sett.

Slik er kapitlet lagt opp (45 min): tre løkker med teori, gjennomkjørt
eksempel og oppgaver, og et pausepunkt etter løkke 2.

Forkunnskaper

- kap. 5.1 — grafnotasjonen $G = (V, E)$ , nabolister og
begrepet inngrad (hvor mange kanter som peker inn til en node).
- kap. 5.2 — BFS og DFS. Kahns algoritme har samme form som
en BFS: en kø, ett element av gangen.
- kap. 1.2 — løkketelling. Kjøretiden $O(|V| + |E|)$ leses
ut av at hver node og hver kant berøres én gang.

Har du ikke jobbet med nøstede strukturer i kode før, er
Nøstede lister og ordbøker et mykt sted å begynne — en
naboliste er akkurat det: en liste av lister.

Notasjons- og pseudokodeliste

Løkke 1 — huset som må bygges i riktig rekkefølge (ca. 12 min)

Et modulbygg settes opp av åtte arbeidslag. Grunnmuren må stå før gulvmodulene
kan legges, gulvmodulene før heissjakten kan reises, og fasadekledningen kan først
komme når både taket og heissjakten er ferdige. Ingen av lagene bryr seg om noe
annet enn sine egne forutsetninger.

Spørsmålet byggelederen sitter med, er ikke vanskelig å formulere: finnes det en
rekkefølge der hvert lag kan gjøre jobben sin uten å vente på noe som ikke er
gjort? Og hvis den finnes — hvordan finner vi den, uten å prøve oss fram?

Dette er et grafproblem. Hvert arbeidslag er en node, og en pil fra $u$ til $v$
betyr « $u$ må være ferdig før $v$ kan starte». Da er spørsmålet: kan nodene stilles
opp på en linje slik at alle pilene peker framover?

DAG (rettet asyklisk graf)

En rettet graf uten sykler: du kan aldri følge pilene fra en node og komme tilbake til den samme noden igjen. Forkortelsen kommer fra engelsk «directed acyclic graph». Ordet asyklisk betyr nettopp «uten sykel». Enhver avhengighetsstruktur som faktisk lar seg gjennomføre, er en DAG — og motsatt: er den ikke en DAG, finnes det en gruppe oppgaver som alle venter på hverandre.

Topologisk rekkefølge

u

Inngrad

|E|

📜Topologisk rekkefølge finnes hvis og bare hvis grafen er en DAG

En rettet graf har en topologisk rekkefølge nøyaktig når den ikke har noen
sykel.

Den ene veien er lett å se: har grafen en sykel $v_1 \to v_2 \to \ldots \to v_1$ ,
måtte $v_1$ kommet før $v_2$ , som måtte kommet før $v_1$ . Det er umulig.

Den andre veien er selve algoritmen: Kahns metode konstruerer en rekkefølge så
lenge grafen er asyklisk, og stopper med noder til overs hvis den ikke er det. Du
trenger ikke bevise dette på eksamen, men du skal kunne bruke begge retningene:
«ingen lovlig rekkefølge» og «grafen har en sykel» er det samme utsagnet.

✏️Eksempel 1: Kahns algoritme på modulbygget

Arbeidslagene er $A$ = grunnmur, $B$ = gulvmoduler, $C$ = bæresøyler,
$D$ = veggmoduler, $E$ = trapperom, $F$ = tak, $G$ = heissjakt og
$H$ = fasadekledning. Avhengighetene er

A -> B, A -> C, B -> D, C -> D, C -> E, D -> F, E -> F, B -> G,
G -> H, F -> H.

Finn en lovlig rekkefølge, eller vis at ingen finnes.

Steg 0 — inngradstabellen. Tell hvor mange piler som peker inn til hver node:

A=0, B=1, C=1, D=2, E=1, F=2, G=1, H=2

Kontrollregning: summen er $0+1+1+2+1+2+1+2 = 10$ , og grafen har 10 kanter. Stemmer.

Bare $A$ har inngrad 0, så køen starter som A.

Sporingen. Køen holdes i alfabetisk rekkefølge her, slik at sporingen er
mulig å gjenskape nøyaktig. Det er ikke et krav i algoritmen — enhver rekkefølge i
køen gir en lovlig topologisk rekkefølge.

Steg	Plukket	Naboers inngrad senkes	Inngrader etter	Kø etter	Rekkefølge så langt
1	A	`B: 1 -> 0`, `C: 1 -> 0`	`A=0, B=0, C=0, D=2, E=1, F=2, G=1, H=2`	`B, C`	`A`
2	B	`D: 2 -> 1`, `G: 1 -> 0`	`A=0, B=0, C=0, D=1, E=1, F=2, G=0, H=2`	`C, G`	`A, B`
3	C	`D: 1 -> 0`, `E: 1 -> 0`	`A=0, B=0, C=0, D=0, E=0, F=2, G=0, H=2`	`D, E, G`	`A, B, C`
4	D	`F: 2 -> 1`	`A=0, B=0, C=0, D=0, E=0, F=1, G=0, H=2`	`E, G`	`A, B, C, D`
5	E	`F: 1 -> 0`	`A=0, B=0, C=0, D=0, E=0, F=0, G=0, H=2`	`F, G`	`A, B, C, D, E`
6	F	`H: 2 -> 1`	`A=0, B=0, C=0, D=0, E=0, F=0, G=0, H=1`	`G`	`A, B, C, D, E, F`
7	G	`H: 1 -> 0`	`A=0, B=0, C=0, D=0, E=0, F=0, G=0, H=0`	`H`	`A, B, C, D, E, F, G`
8	H	ingen	`A=0, B=0, C=0, D=0, E=0, F=0, G=0, H=0`	`tom`	`A, B, C, D, E, F, G, H`

Sluttilstand — dette er svaret du leverer:

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

Alle 8 nodene ble prosessert, så grafen er en DAG, og rekkefølgen er lovlig.
Kontrollen som tar ti sekunder: gå gjennom hver kant og sjekk at venstre node
står før høyre i svaret ditt. A -> B: ja. B -> G: ja. F -> H: ja. Alle ti
kanter peker framover.
Fellenote. Fella her er å tro at rekkefølgen er entydig. Prøv å plukke

C

før

B

i steg 2 — begge har inngrad 0 der — og du får A, C, B, E, D, F, G, H, som er
like riktig. Sensor sjekker at kantene peker framover, ikke at du traff «fasiten».

📝Oppgave 1

(Innstegsoppgave, sjanger H — grafalgoritme, altså at du gjenkjenner problemet og
bruker riktig algoritme.) En rettet graf har nodene $P, Q, R, S$ og kantene
P -> R, Q -> R, R -> S.

a) Skriv opp inngraden til hver node.
b) Hvilke noder kan Kahns algoritme starte med?
c) Skriv opp to forskjellige lovlige topologiske rekkefølger.

Løkke 2 — algoritmen skrevet ned (ca. 15 min)

Sporingen i eksempel 1 er hele algoritmen. Nå skal den skrives ned slik du må
kunne den på eksamen: som en Procedure med input, output og oppgitt kjøretid.

Metoden heter Kahns algoritme etter Arthur Kahn, som beskrev den i 1962. Ideen
er den samme som byggelederens: gjør alt som kan gjøres nå, og se hva som blir
klart av det.

📜Pseudokode-kontrakt: `TopologiskSortering`

Antagelser om representasjon. Grafen

G = (V, E)

er gitt som nabolister:
G.naboer(v) gir alle noder w med en kant v -> w, og en gjennomgang av alle
nabolister koster

O(|V| + |E|)

til sammen. inngrad er et array indeksert på
node. Køen er en vanlig kø med

O(1)

innsetting og uttak.

Prebetingelse: ingen — algoritmen virker på enhver rettet graf.
Postbetingelse: returverdien er enten en lovlig topologisk rekkefølge med alle
$|V|$ nodene, eller meldingen «syklisk».

Procedure TopologiskSortering(G)
  Input:  rettet graf G = (V, E) som nabolister
  Output: en liste med alle nodene i topologisk rekkefolge,
          eller meldingen «syklisk» hvis ingen slik rekkefolge finnes
  for hver v i V:
      inngrad[v] = 0
  for hver v i V:
      for hver w i G.naboer(v):
          inngrad[w] = inngrad[w] + 1
  Ko = tom ko
  for hver v i V:
      if inngrad[v] er 0:
          Ko.leggTil(v)
  rekkefolge = tom liste
  while Ko er ikke tom:
      v = Ko.taUt()
      rekkefolge.leggTilBakerst(v)
      for hver w i G.naboer(v):
          inngrad[w] = inngrad[w] - 1
          if inngrad[w] er 0:
              Ko.leggTil(w)
  if lengden av rekkefolge er ulik |V|:
      return «syklisk»
  return rekkefolge

Grunnideen i én setning: en node kan trygt plasseres i rekkefølgen så snart
alt som må komme før den, allerede er plassert — og det ser du på at inngraden er
falt til null.

Kjøretid: $O(|V| + |E|)$ . Tell løkkene: den første går over alle noder,
$O(|V|)$ . Den andre går over alle nabolister, altså hver kant én gang,
$O(|E|)$ . Den tredje går over alle noder igjen, $O(|V|)$ . while-løkka tar hver
node ut av køen nøyaktig én gang (en node legges i køen bare når inngraden når
null, og den når null bare én gang), og for hver av dem gås nabolisten gjennom én
gang — til sammen $O(|V|)$ uttak og $O(|E|)$ kantbehandlinger. Summen er
$O(|V| + |E|)$ , ikke et produkt: løkkene står etter hverandre, ikke inni
hverandre.

Legg merke til hvorfor køen er der. Uten den måtte du lete gjennom hele
inngradstabellen etter en null hver eneste runde — $|V|$ runder à $O(|V|)$ leting,
altså $O(|V|^2)$ . Køen husker hvem som ble klar, og det er hele forskjellen
mellom en lineær og en kvadratisk løsning.

Merk også at det står kø, ikke stack. Begge virker. En stack gir en annen
lovlig rekkefølge, ikke en gal en. Skriver du stack i besvarelsen din, er det
riktig så lenge du er konsekvent.

✏️Eksempel 2: Hvorfor $O(|V| + |E|)$ og ikke $O(|V| \cdot |E|)$

En medstudent hevder at Kahns algoritme er $O(|V| \cdot |E|)$ , «fordi
while-løkka går over alle nodene, og inni den går vi gjennom kantene». Vis at
det er feil, ved å telle nøyaktig hvor mange ganger hver linje utføres på
modulbygget fra eksempel 1.

Feilen ligger i ordet «kantene». Den indre løkka går ikke gjennom alle
kantene for hver node — den går gjennom nabolista til nettopp den noden som
ble tatt ut.

Tellingen for modulbygget ( $|V| = 8$ , $|E| = 10$ ):

Node tatt ut	Antall naboer	Kantbehandlinger
A	2 (B, C)	2
B	2 (D, G)	2
C	2 (D, E)	2
D	1 (F)	1
E	1 (F)	1
F	1 (H)	1
G	1 (H)	1
H	0	0
Sum	10

Summen er 10 — nøyaktig

|E|

. Det er ikke tilfeldig: hver kant v -> w ligger i
nøyaktig én naboliste (nemlig

v

sin), og den lista gås gjennom nøyaktig én gang,
den gangen

v

tas ut av køen.
Konklusjonen: while-løkka koster

O(|V|)

uttak pluss

O(|E|)

kantbehandlinger, ikke

O(|V|)

ganger

O(|E|)

. Kjøretiden er

O(|V| + |E|)

.
Dette er et generelt mønster som går igjen i hele grafdelen av faget: når en
løkke over noder inneholder en løkke over den nodens naboer, blir summen

O(|V| + |E|)

— ikke et produkt. Samme argument gir kjøretiden til BFS, DFS og
komponentsøk i kap. 5.2.
Poengtrapp-notat. På eksamen er det å oppgi

O(|V| \cdot |E|)

her et rent

tap: kjøretiden matcher ikke algoritmen du faktisk ga, og det er en av de tre
tingene sensorveiledningene nevner eksplisitt at det trekkes for.

📝Oppgave 2

Sjanger H

En rettet graf har nodene $A$ til $F$ og kantene
A -> C, B -> C, C -> D, C -> E, D -> F, E -> F.

a) Skriv opp inngradstabellen, og kontrollér den mot antall kanter.
b) Håndkjør Kahns algoritme og oppgi rekkefølgen. Bruk alfabetisk rekkefølge i
køen.
c) Hvor mange forskjellige lovlige topologiske rekkefølger har denne grafen?

— naturlig pausepunkt —

Du har nå metoden og kjøretiden. Resten av kapitlet handler om det som gjør
topologisk sortering til en eksamensoppgave: hva algoritmen svarer når det
ikke finnes noen rekkefølge, og hvordan du kjenner igjen at det er dette
verktøyet oppgaven ber om.

Løkke 3 — når det ikke finnes noen rekkefølge (ca. 12 min)

Halvparten av eksamensoppgavene på dette temaet spør ikke bare om rekkefølgen. De
spør: finnes det en i det hele tatt? Formuleringen er gjerne «meld fra hvis en
sirkulær avhengighet gjør det umulig».

Det gode med Kahns algoritme er at du får svaret gratis. Du trenger ikke en egen
sykeldeteksjon — du trenger bare å telle.

📜Sykeldeteksjon: tell hvor mange noder som ble prosessert

Kjør Kahns algoritme til køen er tom. Hvis rekkefølgen inneholder færre enn
$|V|$ noder, har grafen en sykel, og ingen topologisk rekkefølge finnes.

Hvorfor det stemmer: en node blir liggende igjen bare hvis inngraden aldri når
null, altså hvis den har en forgjenger som selv aldri ble tatt ut. Følger du den
kjeden bakover i en endelig graf, må du før eller siden komme tilbake til en node
du har vært innom — og det er en sykel.

Bonusen: nodene som ble liggende igjen, er nøyaktig de nodene som ligger på
eller nedstrøms for en sykel. Du kan altså peke på hvor problemet er, ikke bare si
at det finnes. Det er verdt et delpoeng når oppgaven ber om at algoritmen skal
«melde fra».

✏️Eksempel 3: En syklisk avhengighet i et rørsystem

Et anlegg pumper væske gjennom seks trinn. Trinn $A$ mater $B$ og $E$ , $B$ mater
$C$ , $C$ mater $D$ , $D$ mater tilbake til $B$ (en returledning som ble koblet
feil), og $E$ mater $F$ .

Kantene er A -> B, B -> C, C -> D, D -> B, A -> E, E -> F.

Kan trinnene settes i drift i en rekkefølge der hvert trinn har væske når det
starter? Håndkjør Kahns algoritme.

Inngradstabellen: A=0, B=2, C=1, D=1, E=1, F=1. Summen er 6, og grafen har 6
kanter. Bare

A

har inngrad 0.

Steg	Plukket	Naboers inngrad senkes	Inngrader etter	Kø etter	Rekkefølge så langt
1	A	`B: 2 -> 1`, `E: 1 -> 0`	`A=0, B=1, C=1, D=1, E=0, F=1`	`E`	`A`
2	E	`F: 1 -> 0`	`A=0, B=1, C=1, D=1, E=0, F=0`	`F`	`A, E`
3	F	ingen	`A=0, B=1, C=1, D=1, E=0, F=0`	`tom`	`A, E, F`

Sluttilstand — dette er svaret du leverer:

syklisk — ingen topologisk rekkefolge finnes

Tellingen som avgjør: algoritmen prosesserte 3 noder (

A

E

F

), men
grafen har 6. Siden

3 \neq 6

, er grafen ikke en DAG.

Hvor sykelen er. Nodene som ble liggende igjen, er $B$ , $C$ og $D$ — med

inngradene B=1, C=1, D=1 når køen gikk tom. Ingen av dem nådde null, fordi

$B$ venter på $D$ , $D$ venter på $C$ , og $C$ venter på $B$ . Det er sykelen
B -> C -> D -> B, altså returledningen.

Merk at $E$ og $F$ ble prosessert helt normalt. En sykel ett sted i grafen
ødelegger ikke for resten — men den gjør at hele grafen mangler en topologisk
rekkefølge, fordi rekkefølgen må inneholde alle nodene.
Fellenote. Den vanligste feilen her er å levere A, E, F som svar. Det er

ikke en topologisk rekkefølge av grafen — det er tre noder av seks. Algoritmen
skal melde fra, og en besvarelse som ikke sjekker antallet, mister som regel
et helt delpoeng selv om pseudokoden ellers er riktig.

📝Oppgave 3

Sjanger H

Fem oppgaver i et prosjekt har avhengighetene
A -> B, B -> C, C -> E, E -> B, A -> D, D -> E.

a) Håndkjør Kahns algoritme og oppgi hva den svarer.
b) Hvilke noder ble liggende igjen, og hva forteller det deg?
c) Én kant må fjernes for at rekkefølgen skal bli mulig. Hvilken, og hva blir
rekkefølgen da?

Typiske feil

- Å ikke melde fra om sykelen. Kjører du Kahn uten å sammenligne lengden på
rekkefølgen med $|V|$ , leverer du en ufullstendig liste som om den var et svar.
Oppgaveteksten ber nesten alltid eksplisitt om at algoritmen skal si fra. Dette
er felle #1 i bokas feilregister i sin generelle form — å ikke gjøre den
jobben oppgaven faktisk ber om.
- Å bruke DFS uten tilstander til å oppdage sykler. En vanlig DFS med bare
«besøkt / ikke besøkt» kan ikke skille en sykel fra en node du når på to
ulike stier. Du trenger tre tilstander, se avsnittet under.
- Å anta at en topologisk rekkefølge finnes. «Sortér oppgavene topologisk og
utfør dem» er ikke et svar hvis grafen kan ha en sykel. Skriv sjekken.
- Å oppgi $O(|V| \cdot |E|)$ eller $O(|V|^2)$ . Med kø er Kahn
$O(|V| + |E|)$ . Kvadratisk blir den bare hvis du leter etter inngrad-0-noder på
nytt hver runde — og da har du faktisk skrevet en tregere algoritme, som koster
poeng i poengtrappen.
- Å blande retningen. u -> v betyr « $u$ først». Snur du regelen, får du en
rekkefølge der alle kantene peker bakover — teknisk sett den omvendte
topologiske rekkefølgen, men galt svar på oppgaven som ble stilt.

Og den gjennomgående: å ikke definere hva $n$ er. I grafoppgaver skriver du
$|V|$ og $|E|$ , ikke $n$ . Bruker du likevel $n$ , må du si hva det står for. Det er
felle #10 — kjøretid oppgitt uten at størrelsene er definert.

Løkke 4 — de to alternativene, og hva sensor egentlig ser etter (ca. 10 min)

Kahn er ikke den eneste veien. To alternativer nevnes i pensum, og begge kan gi
full uttelling hvis de er presist beskrevet.

DFS med tre tilstander. Gi hver node en av tilstandene uoppdaget, under
prosessering og ferdig. Gjør en dybde-først-traversering; møter du en node som
er under prosessering, har du funnet en sykel. Er alle ferdige, gir nodene i
omvendt rekkefølge av når de ble ferdige, en topologisk rekkefølge. Kjøretiden
er den samme, $O(|V| + |E|)$ .

Grunnen til at de tre tilstandene er nødvendige: en node som er ferdig, kan du
godt møte på nytt — det betyr bare at to stier fører til samme sted. En node som
er under prosessering, ligger derimot på stien du står på akkurat nå, og da har
du gått i ring.

Sterkt sammenhengende komponenter. En rettet graf har en sykel hvis og bare
hvis minst én sterkt sammenhengende komponent inneholder mer enn én node. Det
gir en sykel-test i $O(|V| + |E|)$ , og du får i tillegg vite hvilke noder som
henger sammen. Se kap. 5.4.

Kan dette gjøres raskere? Nei. Du må se på hver kant minst én gang for å vite
at den peker riktig vei, så $O(|V| + |E|)$ er nedre grense for problemet. Alle tre
metodene treffer den. Når tre metoder har samme kjøretid, velger du den du kan
skrive presist — og det er poenget sensorveiledningene gjentar: en klar forklaring
er verdt mer enn en uklar pseudokode.

✏️Eksempel 4: Eksamensnivå — installasjonsrekkefølge med feilmelding

Et system skal installere $n$ programpakker. Hver pakke kan kreve at andre pakker
er installert først. Skriv en algoritme som enten gir en installasjonsrekkefølge,
eller melder at kravene er umulige å oppfylle. Oppgi antagelser og kjøretid, og si
hvorfor kjøretiden ikke kan bli lavere.

Problemet navngitt. Dette er en avhengighetsstruktur der noe må komme før noe
annet, og spørsmålet er om det finnes en lovlig rekkefølge. Det er topologisk
sortering, og sykeltesten er innebygd.

Antagelser om representasjon. Pakkene er nodene i en rettet graf
$G = (V, E)$ med $|V| = n$ pakker; en kant p -> q betyr at p må installeres før
q. Grafen er gitt som nabolister, slik at G.naboer(p) gir alle pakker som
venter på p. Antall avhengigheter er $|E|$ .

Algoritmen.

Procedure Installasjonsrekkefolge(G)
  Input:  rettet graf G = (V, E) over pakker; kant p -> q betyr «p foer q»
  Output: en installasjonsrekkefolge, eller meldingen «sirkulaer avhengighet»
  for hver v i V:
      inngrad[v] = 0
  for hver v i V:
      for hver w i G.naboer(v):
          inngrad[w] = inngrad[w] + 1
  Ko = tom ko
  for hver v i V:
      if inngrad[v] er 0:
          Ko.leggTil(v)
  rekkefolge = tom liste
  while Ko er ikke tom:
      v = Ko.taUt()
      rekkefolge.leggTilBakerst(v)
      for hver w i G.naboer(v):
          inngrad[w] = inngrad[w] - 1
          if inngrad[w] er 0:
              Ko.leggTil(w)
  if lengden av rekkefolge er ulik |V|:
      return «sirkulaer avhengighet», og de gjenvaerende nodene
  return rekkefolge

Kjøretid: $O(|V| + |E|)$ , der $|V| = n$ er antall pakker og $|E|$ er antall
avhengigheter. Hver node tas ut av køen én gang, og hver kant behandles én gang.

Hvorfor dette er lavest mulig. Enhver korrekt algoritme må lese hver
avhengighet minst én gang — en avhengighet den ikke har sett, kan være den som
gjør rekkefølgen umulig. Det gir $\Omega(|V| + |E|)$ som nedre grense, og Kahn
treffer den. Det er derfor dette svaret ligger øverst i poengtrappen: en løsning
som prøver seg fram med permutasjoner, eller som leter gjennom inngradstabellen
hver runde ( $O(|V|^2)$ ), er korrekt, men tregere — og «lavere kjøretid er mer
poenggivende» er den mest gjentatte poengregelen i faget.

Det siste delpoenget ligger i returlinja: at algoritmen ikke bare svarer
«umulig», men også peker på hvilke pakker som inngår i den sirkulære
avhengigheten. Det er gratis — det er nettopp nodene som ble liggende igjen.

📝Oppgave 4

Sjanger F

Sett
kryss for hvert utsagn: sant eller usant?

a) Enhver rettet graf har minst én topologisk rekkefølge.
b) En DAG kan ha flere forskjellige topologiske rekkefølger.
c) Kahns algoritme er $O(|V| + |E|)$ når køen er en vanlig kø.
d) Hvis Kahns algoritme prosesserer alle nodene, er grafen en DAG.
e) En urettet graf kan sorteres topologisk.

📝Oppgave 5

Sjanger H

Skriv ErDAG(G) — en prosedyre som returnerer sant hvis den
rettede grafen G er asyklisk, og usant ellers. Oppgi antagelser om
representasjon og kjøretid.

Forklar til slutt med én setning hvorfor du ikke trenger å lete etter selve
sykelen for å svare.

📝Oppgave 6

Sjanger H, krevende

En DAG kan ha mange lovlige topologiske rekkefølger. Skriv
en algoritme som avgjør om rekkefølgen er entydig, altså om det finnes
nøyaktig én.

a) Formulér betingelsen for entydighet i én setning.
b) Skriv algoritmen i pseudokode, og oppgi kjøretiden.
c) Sjekk betingelsen på grafen med kantene A -> B, B -> C, C -> D,
A -> C, B -> D.

📝Oppgave 7

Sjanger H, krevende

I et byggeprosjekt med $|V|$ oppgaver og $|E|$
avhengigheter vil prosjektlederen vite, for én bestemt oppgave $t$ , hvor mange
andre oppgaver som må være ferdige før $t$ kan starte — direkte eller indirekte.

a) En kollega foreslår: «kjør en søking fra hver node og se om den når $t$ ».
Hva blir kjøretiden?
b) Gi en løsning med lavere kjøretid, og oppgi den.
c) Hvor mange er svaret for oppgave $F$ i modulbygget fra eksempel 1?

Begrepsbank

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

Kahns algoritme

O(|V| + |E|)

Sykel i rettet graf

O(|V| + |E|)

DFS med tre tilstander

O(|V| + |E|)

Kildenode og sluttnode

En kildenode har inngrad 0 — ingenting peker inn til den. En sluttnode har utgrad 0 — den peker ikke videre. Enhver ikke-tom DAG har minst én av hver. Kahns algoritme starter alltid i kildenodene, og de siste nodene i rekkefølgen er alltid sluttnoder.

Hvorfor køen gjør Kahn lineær

|V|

Kø eller stack i Kahns algoritme

Begge virker, og begge gir en lovlig topologisk rekkefølge — de gir bare forskjellige rekkefølger. Køen gir en «bredde-først»-aktig rekkefølge, stacken en «dybde-først»-aktig. Sensor godtar enhver lovlig rekkefølge, så velg den du klarer å skrive konsekvent.

Entydig topologisk rekkefølge

O(|V| + |E|)

Reversert graf

G^R

Kjøretiden

O(|V| + |E|)

— hva den betyr

|E|

Vektet DAG og korteste vei

O(|V| + |E|)

Mønstergjenkjenning: når er svaret topologisk sortering?

O(|V| + |E|)

Summen av inngrader

\sum_{v \in V} \text{inngrad}(v) = |E|

Repetisjon — kapitlet på ett kort

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 Universitetet i Oslo. Dette er ikke offisielt studiemateriell. Les mer.