5.4 SCC og komponentgraf (kondensasjon) — UiO-signatur

Sterkt sammenhengende komponenter (SCC) og komponentgrafen — UiOs signaturverktøy for reachability-resonnement, der komponentgrafen alltid er en DAG.

55 min

9 oppgaver

SCCkomponentgraf (kondensasjon)UiO-signatur

Din fremgang i kapitlet

0 / 9 oppgaver

Kapitlets plass i kurset

Bygger på

5.2BFS og DFS — traversering

Brukes videre i

5.5DRILL — Grafalgoritmer i pseudokode: mønstergjenkjenning

Dette er kapitlet der toppkarakterene skilles.

Sterkt sammenhengende komponenter, forkortet SCC, og komponentgrafen er
belagt i 3 av 7 sett (43 %) — lavere enn traversering, som er i alle sju. Men
frekvensen forteller ikke hele historien. SCC er UiOs signaturverktøy, og det
kommer aldri som «finn de sterkt sammenhengende komponentene». Det kommer som en
oppgavetekst om nettsider, om gater eller om et bytte-nettverk, der du selv må se
at spørsmålet handler om hvem som kan nå hvem. Klarer du det, er resten
mekanisk. Klarer du det ikke, skriver du en løsning som er kvadratisk der den
kunne vært lineær, og mister halve poengsummen på den ene oppgaven som skiller
sjiktene.

Sjangeren er H — grafalgoritme i pseudokode, altså at du får problemet
beskrevet i ord og skal skrive algoritmen selv, med oppgitt kjøretid. Sjanger H
står i hvert eneste sett med to eller tre oppgaver, og SCC-oppgaven er som regel
en av de siste og tyngste.

Prioriteten er «kunne», nivå 2 av tre: stoff du skal beherske og kunne skrive
ned, uten at det er det første du pugger. Men det er nivå 2 med høyest
differensiering i hele grafdelen — det er her forskjellen mellom en god og en
utmerket besvarelse blir synlig.

Tre setninger er hele kapitlet. Lærer du bare disse, har du det viktigste:

1. Finn rundturer — grupper der alle når hverandre — er SCC-er med mer enn én
node.
2. Minste startmengde — færrest mulig noder å starte fra for å nå alt — er
antall komponenter med inngrad 0 i komponentgrafen.
3. Hvor alt ender opp er komponentene med utgrad 0.

Alt sammen i $O(|V| + |E|)$ .

Slik er kapitlet lagt opp (55 min):

Løkke	Innhold	Tid
1	SCC, komponentgrafen og algoritmen	ca. 14 min
2	Inngrad 0: den minste startmengden	ca. 18 min
3	Utgrad 0: hvor alt ender opp	ca. 15 min
4	Poengtrappen, og hva du ikke skal bruke tid på	ca. 8 min

Forkunnskaper — sist du var her

Dette kapitlet bygger rett oppå traverseringen, så her er de tre resultatene du
trenger, ferdig oppfrisket. Trenger du mer enn oppfriskningen, står de i sin
helhet i kap. 5.2 og kap. 5.1.

1. DFS-full koster $O(|V| + |E|)$ . Med en ytre løkke over alle noder og et
felles besokt-felt besøkes hver node én gang og hver kant ses på én gang per
retning. Én DFS fra én node koster $O(|E|)$ ; forskjellen er initialiseringen
og nodene uten kanter, og å blande dem er felle #6.

2. Den ytre løkka er det som gjør en traversering komplett. Uten den
behandles bare komponenten du startet i. I dette kapitlet kjører vi to
gjennomløp, og begge har en slik ytre løkke.

3. I en rettet graf har hver node inngrad og utgrad. Inngrad er antall kanter
inn til noden, utgrad antall kanter ut fra den. Hele kapitlet handler om
de to tallene, men målt på komponenter i stedet for på enkeltnoder.

Fra kap. 5.3 tar vi med tanken om at komponenter kan telles
med én traversering — her blir den bare litt mer krevende, fordi kantene har
retning. Og fra kap. 1.2: kjøretider begrunnes ved
løkketelling, ikke ved påstand.

Notasjons- og pseudokodeliste

Løkke 1 — hvem kan nå hverandre begge veier? (ca. 14 min)

Et bysentrum har lagt om til enveiskjøring. Et budfirma vil vite hvilke kryss som
henger sammen begge veier: fra hvilke kryss kan bilen kjøre til et annet kryss
og tilbake igjen, uten å bryte skiltingen?

Det er ikke det samme som at gatene «henger sammen». Ser du bort fra retningene,
er hele sentrum ett nett. Men med retningene kan du fint komme deg fra torget til
havna uten å kunne kjøre tilbake. Nettopp den forskjellen er hele kapitlet, og
det er derfor urettede komponenter fra kap. 5.3 ikke svarer
på spørsmålet.

Vi trenger et begrep for «gruppene som henger sammen begge veier». Det heter
sterkt sammenhengende komponent, forkortet SCC, og hverdagsversjonen er:
hvem kan nå hverandre begge veier?

Sterkt sammenhengende komponent (SCC)

En maksimal mengde noder i en rettet graf der det finnes en rettet vei fra hver node til hver av de andre — begge veier, for hvert par. «Maksimal» betyr at du ikke kan legge til én node til uten å ødelegge egenskapen. En enkelt node uten noen rundtur er en fullverdig SCC med bare seg selv i, og det er den vanligste misforståelsen: SCC betyr ikke «stor gruppe». En SCC med mer enn én node betyr derimot at det finnes en rundtur gjennom alle nodene i den.

Komponentgraf (kondensasjon)

K_i

📜Komponentgrafen er alltid en DAG

Komponentgrafen til en hvilken som helst rettet graf inneholder ingen rettede
sykler. Den er alltid en DAG, som er standardforkortelsen for en rettet
asyklisk graf, altså en rettet graf uten rundturer.

Intuisjonen i én setning: hadde det gått en rundtur mellom to komponenter,
ville alle nodene i begge nådd hverandre begge veier, og da hadde de per
definisjon vært én komponent, ikke to.

Dette er kjent stoff, og det skal du ikke bevise på eksamen. Resultatet kan
brukes fritt som en kjent egenskap. Å bruke ti minutter av en firetimers eksamen
på å bevise det, er ti minutter tatt fra oppgaver som gir poeng — og
sensorveiledningene forventer det ikke. Sett gjerne av én linje til intuisjonen
over, ikke mer.

Konsekvensen du faktisk bruker: i en DAG finnes det alltid minst én komponent
med inngrad 0 og minst én med utgrad 0. Det er de to tallene resten av
kapitlet handler om.

📜Pseudokode-kontrakt: `StronglyConnectedComponents`

Antagelser om representasjon. G er en rettet graf gitt som nabolister:
v-ens naboliste inneholder nodene v peker på. Hver node v har feltet
v.besokt. Vi kan bygge den snudde grafen G_R ved å gå gjennom alle kanter én
gang.

Prebetingelse: ingen. Postbetingelse: returverdien er en liste av
mengder, der hver mengde er én SCC, og hver node ligger i nøyaktig én av dem.

Procedure StronglyConnectedComponents(G)
  Input:  rettet graf G = (V, E) som nabolister
  Output: liste med SCC-ene i G, hver som en mengde noder
  for hver node v i V:
      v.besokt = usant
  Ferdig = tom liste
  for hver node v i V:
      if v.besokt er usant:
          DFSFerdig(v, Ferdig)
  G_R = G med alle kanter snudd
  for hver node v i V:
      v.besokt = usant
  Komponenter = tom liste
  for hver node v i Ferdig i OMVENDT rekkefolge:
      if v.besokt er usant:
          K = tom mengde
          SamleVisit(v, G_R, K)
          legg K bakerst i Komponenter
  return Komponenter

Grunnideen i én setning: rekkefølgen nodene blir ferdige i under det
første gjennomløpet, sier hvilken komponent som ligger «først» i grafen, og
starter du så en DFS i den snudde grafen fra den siste som ble ferdig, kan du
bare nå noder i din egen komponent — så alt den samler inn, er nøyaktig én SCC.

Kjøretid: $O(|V| + |E|)$ . Gjennomløp 1 er en DFS-full, altså
$O(|V| + |E|)$ ; å snu grafen er én gjennomgang av alle kanter, $O(|V| + |E|)$ ;
gjennomløp 2 er en ny DFS-full, $O(|V| + |E|)$ . Tre lineære pass etter hverandre
er fremdeles lineært.

På eksamen holder det som regel å beskrive ideen i ord — to DFS-gjennomløp,
det andre i den snudde grafen i synkende ferdigrekkefølge — sammen med
kjøretiden. Kravet er at forklaringen er entydig og presis, ikke at den er
syntaktisk pseudokode.

📜Pseudokode-kontrakt: hjelpeprosedyrene

De to gjennomløpene er hver sin lille DFS. Den eneste forskjellen fra en vanlig
DFSVisit er hva de noterer underveis.

Procedure DFSFerdig(v, Ferdig)
  Input:  node v i G, listen Ferdig
  Output: alle noder som nas fra v er besokt, og lagt i Ferdig i ferdigrekkefolge
  v.besokt = sant
  for hver nabo u av v i G:
      if u.besokt er usant:
          DFSFerdig(u, Ferdig)
  legg v bakerst i Ferdig

Procedure SamleVisit(v, G_R, K)
  Input:  node v, den snudde grafen G_R, mengden K under oppbygging
  Output: alle noder som nas fra v i G_R er lagt i K
  v.besokt = sant
  legg v i K
  for hver nabo u av v i G_R:
      if u.besokt er usant:
          SamleVisit(u, G_R, K)

Legg merke til den ene linja som gjør hele forskjellen: i DFSFerdig legges
noden i Ferdig etter løkka, ikke før. En node blir «ferdig» først når alle
utveier fra den er utforsket. Legger du den inn før løkka, får du
besøksrekkefølgen i stedet, og hele algoritmen slutter å virke.

Kjøretid: samlet over alle kallene er begge $O(|V| + |E|)$ — hver node
besøkes én gang og hver kant følges én gang, akkurat som i en vanlig DFS-full.

Rekursjonsdybde: $O(|V|)$ i verste fall, når grafen er én lang kjede. Det er
verdt en setning i besvarelsen; en iterativ variant med eksplisitt stakk gjør
nøyaktig det samme.

✏️Eksempel 1: Enveiskjørt sentrum — tre grupper på rad

Åtte kryss i et sentrum er forbundet med enveiskjørte gater. Nabolistene viser
hvilke kryss du kan kjøre til fra hvert kryss:

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

Kjør StronglyConnectedComponents, bygg komponentgrafen, og svar på hvilke
grupper av kryss som henger sammen begge veier.

Problemet navngitt: dette er «hvem når hvem begge veier» i en rettet graf,
altså sterkt sammenhengende komponenter. Antagelser: grafen er gitt som
nabolister, og naboene besøkes i alfabetisk rekkefølge, slik at kjøringen blir
entydig.

Gjennomløp 1 — DFS over $G$ , noter ferdigrekkefølgen:

Hendelse	Node	Ferdignummer
ny DFS-start (ytre løkke)	A	-
besøker	A	-
besøker	B	-
besøker	C	-
besøker	D	-
besøker	E	-
besøker	F	-
besøker	G	-
besøker	H	-
ferdig (kallet returnerer)	H	1
ferdig (kallet returnerer)	G	2
ferdig (kallet returnerer)	F	3
ferdig (kallet returnerer)	E	4
ferdig (kallet returnerer)	D	5
ferdig (kallet returnerer)	C	6
ferdig (kallet returnerer)	B	7
ferdig (kallet returnerer)	A	8

- ferdigrekkefølge (først ferdig først): H, G, F, E, D, C, B, A
- SYNKENDE ferdigrekkefølge (den gjennomløp 2 bruker): A, B, C, D, E, F, G, H
Den snudde grafen $G_R$ :

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

Gjennomløp 2 — DFS i $G_R$ i synkende ferdigrekkefølge:

Nr.	Startnode	Noder samlet inn	= SCC
1	A	A, B, C	K1
2	D	D, E	K2
3	F	F, G, H	K3

- antall SCC: 3
- K1 = {A, B, C} (3 noder)
- K2 = {D, E} (2 noder)
- K3 = {F, G, H} (3 noder)
Komponentgrafen (kondensasjonen):

K1 = {A, B, C}: K2
K2 = {D, E}: K3
K3 = {F, G, H}: (ingen utkanter)

Komponent	Noder	Inngrad	Utgrad
K1	A, B, C	0	1
K2	D, E	1	1
K3	F, G, H	1	0

- komponenter med inngrad 0 (minste startmengde): 1 — K1 = {A, B, C}
- komponenter med utgrad 0: 1 — K3 = {F, G, H}
- komponenter med mer enn en node (= det finnes en rundtur): 3 — {A, B, C}; {D, E}; {F, G, H}
- er komponentgrafen en DAG: JA
Svaret budfirmaet skal ha: tre grupper henger sammen begge veier — kryssene

A, B og C; kryssene D og E; kryssene F, G og H. Innenfor hver gruppe kommer du
alltid tilbake dit du startet. Mellom gruppene går trafikken bare én vei.

Kontroll — hvem nås fra hvem:

Startnode	Når disse nodene	Antall
A	A, B, C, D, E, F, G, H	8
B	A, B, C, D, E, F, G, H	8
C	A, B, C, D, E, F, G, H	8
D	D, E, F, G, H	5
E	D, E, F, G, H	5
F	F, G, H	3
G	F, G, H	3
H	F, G, H	3

- velger vi EN node fra hver inngrad-0-komponent (A), når vi 8 av 8 noder: ALLE

Les kontrolltabellen én gang til. Alle nodene i samme SCC har nøyaktig samme
rad — de når det samme, fordi de når hverandre. Det er hele grunnen til at
komponentgrafen er et brukbart svar på reachability-spørsmål: åtte spørsmål er
redusert til tre.
Kjøretid: $O(|V| + |E|)$ , her $|V| = 8$ og $|E| = 10$ .

Fellenote. Fella her er felle #1 — naiv full traversering der én kjøring
holdt. Åtte separate DFS-er, én fra hvert kryss, ville gitt den samme
kontrolltabellen på $O(|V| \cdot (|V| + |E|))$ . Én SCC-kjøring gir den på
$O(|V| + |E|)$ .

📝Oppgave 1

(Innstegsoppgave, sjanger H — grafalgoritme i pseudokode, altså at du får
problemet i ord og skal svare med algoritmen og kjøretiden. Her holder det å lese
av strukturen.) Et varslingssystem har fem enheter. Hver enhet varsler videre til
enhetene i sin naboliste, og varsler går bare én vei:

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

a) Finnes det noen rundtur i dette systemet?
b) Hvor mange sterkt sammenhengende komponenter har grafen, og hvilke noder
ligger i hver?
c) Hva er den minste mengden enheter du må varsle for at alle skal få
beskjed?

📝Oppgave 2

Sjanger H

Fire påstander om sterkt sammenhengende komponenter. Avgjør om hver
er sann eller usann, og begrunn med én setning.

a) En rettet graf der alle nodene henger sammen når du ser bort fra
retningene, har alltid nøyaktig én SCC.
b) En SCC kan bestå av bare én node.
c) Komponentgrafen kan inneholde en rettet sykel hvis den opprinnelige grafen
har mange sykler.
d) Hvis to noder ligger i samme SCC, når de nøyaktig de samme nodene i resten
av grafen.

Løkke 2 — den minste startmengden (ca. 18 min)

— naturlig pausepunkt —

Nå kommer den oppgaveformen som faktisk står i settene. Den ser slik ut:

Et nettsted består av sider som lenker til hverandre. Alle lenkene er
enveiskjørte: at side A lenker til side B, betyr ikke at B lenker tilbake.
Hvor få sider må du legge inn i menyen for at en besøkende skal kunne komme
seg til hver eneste side ved å klikke seg videre?

Ingen steder står ordet «komponent». Det står ikke «SCC», og det står ikke
«graf». Jobben din er å se at dette er et spørsmål om hvem som kan nås fra
hvem, og at svaret ligger i komponentgrafen.

Tenk gjennom hvorfor. Ligger to sider i samme SCC, spiller det ingen rolle
hvilken av dem du velger — de når nøyaktig det samme. Så valget står egentlig
mellom komponenter, ikke mellom sider. Og i komponentgrafen, som er en DAG,
finnes det komponenter ingen kant peker inn i. Dem kan du umulig nå utenfra, så
hver av dem må du starte i. Alle andre komponenter kan du følge en kant bakover
fra, og til slutt havner du i en komponent uten innkommende kanter.

Det gir svaret, og det er verdt å lære ordrett: antall noder du minst må starte
fra, er antall komponenter med inngrad 0 i komponentgrafen.

📜De tre reachability-mønstrene

Tre spørsmål dekker så godt som alle SCC-oppgavene. «Reachability» betyr her
ganske enkelt hvem som kan nås fra hvem.

1. «Finn gruppene der alle når hverandre» — rundturer. Svaret er SCC-ene med
mer enn én node. Signalord i oppgaveteksten: rundtur, sirkel, «kommer tilbake
til», «kan bytte med hverandre», gjensidig.

2. «Hvor få må jeg starte fra for å nå alt?» — startmengden. Svaret er
antall komponenter med inngrad 0 i komponentgrafen, og én vilkårlig node fra
hver av dem er et gyldig valg. Signalord: «minste antall», «hvor få sider i
menyen», «hvor mange må varsles først».

Hvorfor tallet er riktig, begge veier. Det er nok: fra en komponent med
inngrad 0 kan du følge kanter framover, og siden komponentgrafen er en DAG uten
rundturer, når du til slutt alt som ligger nedstrøms — og hver eneste komponent
har en vei bakover til minst én inngrad-0-komponent. Og færre går ikke: en
komponent med inngrad 0 kan per definisjon ikke nås fra noen annen komponent, så
den må ha en startnode i seg selv.

3. «Hvem ender alt opp i?» — slukene. Svaret er komponentene med utgrad 0.
Er det nøyaktig én slik komponent, nås den fra samtlige noder i grafen, og da
har du funnet gruppen «alle andre til slutt kommer fram til». Er det flere, finnes
ingen slik gruppe. Signalord: «hvor havner alt», «hvilke sider kan man ikke komme
seg videre fra».

Speilbildet, som ofte spørres om i samme oppgave: finnes det én node som
når alle andre? Ja, hvis og bare hvis komponentgrafen har nøyaktig én
komponent med inngrad 0 — da er hvilken som helst node i den et gyldig svar.

Kjøretid for alle tre: $O(|V| + |E|)$ . Du kjører SCC én gang, bygger
komponentgrafen med én gjennomgang av kantene, og teller inngrader og utgrader.

✏️Eksempel 2: Nettstedet — hvor få sider må ligge i menyen?

Et nettsted har åtte sider. Nabolistene viser hvilke sider hver side lenker
til:

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

Hvor få sider må ligge i menyen for at en besøkende skal kunne klikke seg videre
til hver eneste side? Oppgi algoritmen, svaret og kjøretiden.

Problemet navngitt: dette er reachability i en rettet graf — «hvor få
startpunkter trengs for å nå alt». Verktøyet er SCC pluss komponentgrafen, og
svaret er antall komponenter med inngrad 0.

Antagelser om representasjon: nabolister der v-ens liste inneholder sidene
v lenker til; naboene besøkes i alfabetisk rekkefølge.

Gjennomløp 1 — DFS over $G$ , noter ferdigrekkefølgen:

Hendelse	Node	Ferdignummer
ny DFS-start (ytre løkke)	A	-
besøker	A	-
besøker	B	-
ferdig (kallet returnerer)	B	1
besøker	E	-
besøker	F	-
ferdig (kallet returnerer)	F	2
besøker	G	-
besøker	H	-
ferdig (kallet returnerer)	H	3
ferdig (kallet returnerer)	G	4
ferdig (kallet returnerer)	E	5
ferdig (kallet returnerer)	A	6
ny DFS-start (ytre løkke)	C	-
besøker	C	-
besøker	D	-
ferdig (kallet returnerer)	D	7
ferdig (kallet returnerer)	C	8

- ferdigrekkefølge (først ferdig først): B, F, H, G, E, A, D, C
- SYNKENDE ferdigrekkefølge (den gjennomløp 2 bruker): C, D, A, E, G, H, F, B
Den snudde grafen $G_R$ :

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

Gjennomløp 2 — DFS i $G_R$ i synkende ferdigrekkefølge:

Nr.	Startnode	Noder samlet inn	= SCC
1	C	C, D	K1
2	A	A, B	K2
3	E	E, F	K3
4	G	G, H	K4

- antall SCC: 4
- K1 = {C, D} (2 noder)
- K2 = {A, B} (2 noder)
- K3 = {E, F} (2 noder)
- K4 = {G, H} (2 noder)
Komponentgrafen (kondensasjonen):

K1 = {C, D}: K3
K2 = {A, B}: K3
K3 = {E, F}: K4
K4 = {G, H}: (ingen utkanter)

Komponent	Noder	Inngrad	Utgrad
K1	C, D	0	1
K2	A, B	0	1
K3	E, F	2	1
K4	G, H	1	0

- komponenter med inngrad 0 (minste startmengde): 2 — K1 = {C, D}, K2 = {A, B}
- komponenter med utgrad 0: 1 — K4 = {G, H}
- komponenter med mer enn en node (= det finnes en rundtur): 4 — {C, D}; {A, B}; {E, F}; {G, H}
- er komponentgrafen en DAG: JA
Svaret: to sider må ligge i menyen. For eksempel C og A — eller D og B, det

spiller ingen rolle hvilken av de to i hver komponent du velger.
Kontroll — hvem nås fra hvem:

Startnode	Når disse nodene	Antall
A	A, B, E, F, G, H	6
B	A, B, E, F, G, H	6
C	C, D, E, F, G, H	6
D	C, D, E, F, G, H	6
E	E, F, G, H	4
F	E, F, G, H	4
G	G, H	2
H	G, H	2

- velger vi EN node fra hver inngrad-0-komponent (C, A), når vi 8 av 8 noder: ALLE

Se hva kontrolltabellen sier om hvorfor ÉN side ikke holder. Ingen enkeltrad

har 8. Den beste enkeltsiden når seks av åtte, og de to som mangler, ligger i den
andre inngrad-0-komponenten — dit går det ingen lenke utenfra i det hele tatt.
Det er den konkrete versjonen av argumentet «en komponent med inngrad 0 kan ikke
nås utenfra, så den må ha en startnode i seg selv».
Kjøretid: $O(|V| + |E|)$ , her $|V| = 8$ og $|E| = 11$ . To DFS-gjennomløp,
én snuing av grafen og én gjennomgang av kantene for å telle inngrader — fire

lineære pass.
Fellenote. Fella her er felle #1 — å teste hver side for seg med en ny
traversering. Det gir riktig svar på $O(|V| \cdot (|V| + |E|))$ , og på en oppgave
der sensor oppgir at lavere kjøretid gir mer uttelling, koster det merkbart. Den
nest vanligste er å telle utgrad 0 i stedet for inngrad 0 og svare «én» — les

spørsmålet en gang til før du teller.

📝Oppgave 3

Sjanger H

En varekjede har ni sentrallagre. Et lager kan sende varer videre
til lagrene i sin naboliste, men ikke motsatt vei:

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

a) Finn alle sterkt sammenhengende komponentene.
b) Sett opp komponentgrafen med inngrad og utgrad per komponent.
c) Hvor få lagre må få en leveranse utenfra for at varer skal kunne nå alle
ni? Hvilke?

📝Oppgave 4

Sjanger H

Skriv MinimumStartSet(G), som returnerer det minste antallet noder
man må starte i for å nå alle noder i en rettet graf G. Du kan bruke
StronglyConnectedComponents(G) som en ferdig byggekloss.

Oppgi antagelser om representasjon, kjøretid, og én setning om hvorfor tallet er
riktig.

📝Oppgave 5

Sjanger H

Bruk resultatet ditt fra oppgave 3, altså varekjeden med de ni
sentrallagrene.

a) Hvilke grupper av lagre kan sende varer til hverandre begge veier?
b) Ett av de ni lagrene ligger i en komponent helt alene. Hvilket, og hva
betyr det praktisk?
c) Er det riktig å si at «det finnes tre rundturer i systemet»? Begrunn.

Løkke 3 — hvor alt ender opp (ca. 15 min)

— naturlig pausepunkt —

Snu spørsmålet. I stedet for «hvor må jeg starte for å nå alt?» spør vi «hvor
havner alt til slutt?».

Et saksbehandlingssystem videresender saker mellom kontorer. Noen kontorer sender
videre, noen sender fram og tilbake seg imellom, og noen sender ikke videre i det
hele tatt — der blir saken liggende. Ledelsen vil vite hvor sakene ender opp.

I komponentgrafen er svaret en komponent med utgrad 0: en gruppe du ikke
kommer deg ut av. Og siden komponentgrafen er en DAG, finnes det alltid minst én
slik. Følger du kanter framover, kan du ikke gå i ring, så du må før eller siden
stoppe et sted.

Er det nøyaktig én komponent med utgrad 0, når alle noder i grafen den.
Argumentet er det samme, speilvendt: start hvor som helst, følg kanter framover,
og du stopper i en utgrad-0-komponent — og finnes det bare én, er det den. Er det
flere, finnes det ingen gruppe «alt ender i»: hvilken du havner i, avhenger av
hvor du startet.

Dette er felle-paret du må holde fra hverandre, og det er verdt å skrive det opp
på arket før du begynner å telle:

Spørsmålet i oppgaveteksten	Tell
«hvor få må jeg starte fra for å nå alt?»	komponenter med inngrad 0
«finnes det én som når alle andre?»	ja, hvis det er nøyaktig én inngrad-0-komponent
«hvor ender alt opp?»	komponenter med utgrad 0
«finnes det én alle andre kommer fram til?»	ja, hvis det er nøyaktig én utgrad-0-komponent

Inngrad 0 i komponentgrafen

En komponent som ingen kant peker inn til. Den kan ikke nås fra noen annen del av grafen. Antall slike komponenter er den minste startmengden : så mange noder må du minst starte fra for å nå alt, og én vilkårlig node fra hver av dem holder. Er det nøyaktig én, finnes det én enkelt node som når samtlige andre.

Utgrad 0 i komponentgrafen

En komponent uten utgående kanter — en gruppe du ikke kommer deg ut av igjen. I en DAG finnes det alltid minst én. Er det nøyaktig én slik komponent, nås den fra hver eneste node i grafen: den er der alt ender opp. Er det flere, finnes ingen slik gruppe. Å forveksle utgrad 0 med inngrad 0 er den vanligste enkeltfeilen i SCC-oppgaver.

✏️Eksempel 3: Saksflyten — to steder saken kan bli liggende

Ni kontorer videresender saker slik nabolistene viser. En kant fra X til Y betyr
at kontor X kan sende en sak videre til kontor Y:

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

a) Finn SCC-ene og komponentgrafen.
b) Hvor kan en sak ende opp?
c) Finnes det ett kontor alle saker til slutt havner hos?

Problemet navngitt: reachability i en rettet graf — SCC pluss komponentgraf,
og deretter avlesning av utgrad 0.

Gjennomløp 1 — DFS over $G$ , noter ferdigrekkefølgen:

Hendelse	Node	Ferdignummer
ny DFS-start (ytre løkke)	A	-
besøker	A	-
besøker	B	-
besøker	C	-
besøker	D	-
besøker	E	-
besøker	F	-
ferdig (kallet returnerer)	F	1
ferdig (kallet returnerer)	E	2
besøker	G	-
ferdig (kallet returnerer)	G	3
ferdig (kallet returnerer)	D	4
ferdig (kallet returnerer)	C	5
besøker	H	-
besøker	I	-
ferdig (kallet returnerer)	I	6
ferdig (kallet returnerer)	H	7
ferdig (kallet returnerer)	B	8
ferdig (kallet returnerer)	A	9

- ferdigrekkefølge (først ferdig først): F, E, G, D, C, I, H, B, A
- SYNKENDE ferdigrekkefølge (den gjennomløp 2 bruker): A, B, H, I, C, D, G, E, F
Den snudde grafen $G_R$ :

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

Gjennomløp 2 — DFS i $G_R$ i synkende ferdigrekkefølge:

Nr.	Startnode	Noder samlet inn	= SCC
1	A	A, B, C	K1
2	H	H, I	K2
3	D	D, E, F	K3
4	G	G	K4

- antall SCC: 4
- K1 = {A, B, C} (3 noder)
- K2 = {H, I} (2 noder)
- K3 = {D, E, F} (3 noder)
- K4 = {G} (1 node)
a) Komponentgrafen (kondensasjonen):

K1 = {A, B, C}: K2 -> K3
K2 = {H, I}: (ingen utkanter)
K3 = {D, E, F}: K4
K4 = {G}: (ingen utkanter)

Komponent	Noder	Inngrad	Utgrad
K1	A, B, C	0	2
K2	H, I	1	0
K3	D, E, F	1	1
K4	G	1	0

- komponenter med inngrad 0 (minste startmengde): 1 — K1 = {A, B, C}
- komponenter med utgrad 0: 2 — K2 = {H, I}, K4 = {G}
- komponenter med mer enn en node (= det finnes en rundtur): 3 — {A, B, C}; {H, I}; {D, E, F}
- er komponentgrafen en DAG: JA
b) To steder. En sak kan bli liggende hos H og I, som sender fram og tilbake
mellom seg og ikke videre, eller hos G, som ikke sender videre i det hele tatt.

Det er de to komponentene med utgrad 0.
c) Nei. Fordi det er to utgrad-0-komponenter, finnes det ikke ett kontor

alle saker havner hos. Hvor saken ender, avhenger av hvilken vei den ble sendt

fra K1: gikk den til H, kommer den aldri til G, og omvendt. Kontrolltabellen

viser det direkte:

Startnode	Når disse nodene	Antall
A	A, B, C, D, E, F, G, H, I	9
B	A, B, C, D, E, F, G, H, I	9
C	A, B, C, D, E, F, G, H, I	9
D	D, E, F, G	4
E	D, E, F, G	4
F	D, E, F, G	4
G	G	1
H	H, I	2
I	H, I	2

- velger vi EN node fra hver inngrad-0-komponent (A), når vi 9 av 9 noder: ALLE
Merk kontrasten mellom b) og c). Det er én komponent med inngrad 0, så ett
enkelt kontor — A, B eller C — kan nå samtlige ni. Men det er to med utgrad 0,
så det finnes ikke noe enkelt kontor som samtlige ni når. De to spørsmålene er speilbilder,
og de har ulike svar i den samme grafen. Det er nettopp derfor forvekslingen er

så dyr.
Kjøretid: $O(|V| + |E|)$ , her $|V| = 9$ og $|E| = 11$ .
Fellenote. Fella her er å svare på c) ved å lete etter en node med utgrad 0 i
den opprinnelige grafen. Her ville du funnet G og trodd du var i mål — men H
og I har begge utgående kanter og er likevel et endepunkt, fordi kantene deres

bare peker på hverandre. Spørsmålet skal alltid stilles i komponentgrafen.

📝Oppgave 6

Sjanger H

Fortsett på saksflyten fra eksempel 3.

a) Hvorfor er ikke G alene svaret på «hvor ender alt opp?», selv om G er det
eneste kontoret uten utgående kant?
b) Ledelsen vil endre systemet slik at det finnes ett sted alle saker
havner. Foreslå én enkelt ny videresending, altså én ny rettet kant, som gjør
det, og forklar hvorfor den virker.
c) Hva skjer med antall SCC-er hvis du i stedet legger til kanten fra G
tilbake til A?

Løkke 4 — poengtrappen, og hva du ikke skal bruke tid på (ca. 8 min)

To ting avgjør uttellingen på en SCC-oppgave, og begge handler om tidsbruk.

Det første er poengtrappen. Sensorveiledningene sier det ofte rett ut: lavere
kjøretid gir mer uttelling på samme oppgave. En SCC-oppgave har alltid en naiv
løsning som virker — kjør en DFS fra hver node og noter hvem den når. Den er
$O(|V| \cdot (|V| + |E|))$ og gir riktig svar. Den lineære løsningen gir samme
svar på $O(|V| + |E|)$ . Sensor gir mer for den siste, og på en graf med en million
noder er forskjellen ikke akademisk.

Det andre er hva du ikke skal skrive. At komponentgrafen er en DAG, er kjent
stoff. Du skal ikke bevise det. Du skal heller ikke skrive ut Kosarajus algoritme
i detalj hvis oppgaven bare spør om et tall — det holder å si «kjør SCC, bygg
komponentgrafen, tell komponenter med inngrad 0, $O(|V| + |E|)$ ». Minutter brukt
på et unødvendig bevis er minutter tatt fra de siste oppgavene i Del 2.

Sjekklista på 30 sekunder, før du forlater en SCC-oppgave:

- Har jeg navngitt problemet som reachability og sagt hvilket verktøy jeg bruker?
- Har jeg oppgitt hva jeg antar om representasjonen?
- Teller jeg inngrad 0 eller utgrad 0 — og er det det spørsmålet ba om?
- Har jeg oppgitt kjøretiden, og er $|V|$ og $|E|$ definert?
- Har jeg sagt at $O(|V| + |E|)$ er lavest mulig, og hvorfor?

Typiske feil

De fire feilene under står for det meste av poengtapet i denne sjangeren.

- Å traversere fra hver node i stedet for å kjøre SCC én gang. Dette er felle
#1 — naiv full traversering der én kjøring holdt. Løsningen er riktig, men
$O(|V| \cdot (|V| + |E|))$ i stedet for $O(|V| + |E|)$ , og poengtrappen er
eksplisitt: den koster deg typisk halve uttellingen på oppgaven.
- Å bevise at komponentgrafen er en DAG. Resultatet er kjent og kan brukes
fritt. Beviset gir ingen ekstra poeng, og det tar tid du trenger andre steder.
Én setning med intuisjonen holder mer enn nok.
- Å forveksle inngrad 0 med utgrad 0. Inngrad 0 svarer på «hvor må jeg
starte»; utgrad 0 svarer på «hvor ender alt opp». Kontrollen: les spørsmålet
én gang til og spør deg om du leter etter et startpunkt eller et endepunkt.
- Å tro at SCC er det samme som «henger sammen». En graf kan være svakt
sammenhengende — den henger sammen når du ser bort fra retningene — og likevel
ha mange SCC-er. Eksempel 1 er nettopp det: ett sammenhengende gatenett, tre
SCC-er.

Og den stille: å oppgi kjøretiden $O(|E|)$ fordi «det er én DFS». Det er to
DFS-full-gjennomløp med ytre løkker, pluss en snuing av grafen. Riktig svar er
$O(|V| + |E|)$ , og å bruke $|V|$ og $|E|$ uten å definere dem er felle #10.

📝Oppgave 7

Eksamensnivå, sjanger H

En kollega løser oppgaven «finn det minste antallet
sider man må legge i menyen for å nå alle sider» slik:

«Jeg kjører en DFS fra hver side og noterer hvor mange sider den når. Så velger
jeg den siden som når flest. Er det fortsatt sider igjen som ikke nås, velger
jeg den som når flest av dem, og fortsetter til alt er dekket. Kjøretiden er
$O(|E|)$ , siden DFS er $O(|E|)$ .»

a) Hvilken kjøretid har framgangsmåten faktisk?
b) Gir den alltid riktig svar?
c) Skriv den lineære løsningen, med alle fire leddene sensor ser etter, og
forklar hvorfor den er lavest mulig.

📝Oppgave 8

Eksamensnivå, sjanger H

En kommune driver et bytte-nettverk for
ettromsleiligheter. En rettet kant fra X til Y betyr at beboeren i X er villig til
å flytte inn i Y.

Skriv en algoritme som finner alle grupper der beboerne kan bytte innbyrdes,
altså grupper der hver beboer kan nå hver av de andre langs villighetskantene.
Oppgi antagelser, kjøretid, og forklar hvorfor grupper med bare én beboer ikke
skal være med i svaret.

Forklar til slutt hva svaret hadde blitt hvis nettverket ikke hadde inneholdt en
eneste rundtur.

📝Oppgave 9

Eksamensnivå, sjanger H

Samme nettsted som i eksempel 2, men nå spør
redaktøren om noe annet: finnes det én enkelt side som en besøkende kan starte
på og derfra nå hver eneste andre side? Og hvis ikke — hva er det minste
antallet lenker man må legge til for at det skal bli mulig?

a) Svar på begge spørsmålene for nettstedet i eksempel 2.
b) Formulér den generelle regelen for når svaret på det første spørsmålet er
ja.
c) Skriv algoritmen som avgjør det, med kjøretid.

Begrepsbank

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

SCC-algoritmen — to DFS-gjennomløp

G

Ferdigrekkefølge

Rekkefølgen nodene blir ferdige i under en DFS: en node er ferdig når kallet returnerer, altså når alle utveier fra den er utforsket. Det er ikke det samme som besøksrekkefølgen. I pseudokoden er forskjellen én linje: noden legges i lista etter naboløkka, ikke før. Bytter du om på det, slutter SCC-algoritmen å virke.

Den snudde grafen

G_R

G

Komponentgrafen er en DAG

Kondensasjonen av en hvilken som helst rettet graf er alltid en rettet asyklisk graf — en DAG, altså uten rundturer. Konsekvensen du bruker: det finnes alltid minst én komponent med inngrad 0 og minst én med utgrad 0. Resultatet er kjent og skal ikke bevises på eksamen; én setning med intuisjonen er nok.

Rundtur og SCC-størrelse

En SCC med mer enn én node betyr at det finnes en rettet rundtur gjennom nodene i den. En SCC med én node betyr at noden ikke ligger på noen rundtur. Derfor: spørsmålet «finn alle grupper der alle nås av alle» besvares med SCC-ene av størrelse minst 2. I en graf helt uten rundturer er hver node sin egen SCC, og svaret er den tomme lista.

Sterkt kontra svakt sammenhengende

Sterkt sammenhengende: det finnes en rettet vei begge veier mellom hvert par noder. Svakt sammenhengende: grafen henger sammen når du ser bort fra retningene. En svakt sammenhengende graf kan ha mange SCC-er — et enveiskjørt gatenett er det klassiske eksempelet. Å blande de to er en fast trekkgrunn.

Naiv reachability

O(|V| \cdot (|V| + |E|))

Poengtrappen på SCC-oppgaver

O(|V| + |E|)

Feltet `v.komp`

O(|V|)

Sjanger H — grafalgoritme i pseudokode

Del 2-sjangeren der du får et problem i ord og skal skrive grafalgoritmen selv, med kjøretid. I hvert eneste sett, med to eller tre oppgaver; SCC-oppgaven er gjerne blant de siste og tyngste. Full uttelling krever fire ledd: problemet navngitt, antagelser om representasjon oppgitt, algoritmen (pseudokode eller en klar forklaring i ord), og kjøretid som matcher koden med størrelsene definert.

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.