5.1 Grafrepresentasjon og grunnbegreper

Et par $G = (V, E)$, der $V$ er en mengde noder og $E$ er en mengde
kanter. Hver kant forbinder to noder.

Grafens to størrelser er $|V|$ (antall noder) og $|E|$ (antall kanter), og
alle kjøretider for grafalgoritmer oppgis i begge — for eksempel
$O(|V| + |E|)$. Å oppgi en grafkjøretid som «$O(n)$» uten å si hva $n$ er,
er en fast trekkgrunn.

En graf der kantene ikke har retning: kanten $(u, v)$ er den samme som
$(v, u)$, og du kan gå begge veier.

Fibernett, veinett uten enveiskjøring og vennelister er urettede. I en
naboliste betyr det at hver kant står to ganger — én gang under hver av
de to endene.

En graf der hver kant har en retning: $(u, v)$ går fra $u$ til $v$, og sier
ingenting om veien tilbake.

Lenker mellom nettsider, avhengigheter mellom programvarepakker og
enveiskjørte gater er rettede. Her deles graden i inngrad og utgrad,
og en naboliste inneholder hver kant nøyaktig én gang.

En graf der hver kant i tillegg har et tall — en vekt — som kan bety
avstand, reisetid, kostnad eller kapasitet.

En uvektet graf er en der alle kanter teller likt. Skillet er avgjørende for
hvilken algoritme som er riktig: i en uvektet graf finner en enkel
traversering korteste vei målt i antall kanter, mens vektede grafer krever
andre verktøy (de kommer i Del 6). Alle grafene i Del 5 er uvektede.

En graf uten løkker (en kant fra en node til seg selv) og uten
parallelle kanter (to eller flere kanter mellom det samme nodeparet).

Nesten alt du møter på eksamen er enkelt, og det er derfor grensen
$\displaystyle |E| \le \frac{|V| \cdot (|V| - 1)}{2}$ gjelder. Merk at «enkel» ikke sier
noe som helst om grafen er sammenhengende, eller om den har sykler — det er
tre uavhengige spørsmål, og en avkryssingsoppgave spør gjerne om alle tre på
samme graf.

Antall kanter som møter en node, skrevet $\text{grad}(v)$. I en naboliste er
det ganske enkelt lengden på nodens egen linje.

Gradsummen over alle noder er alltid $2|E|$ i en urettet graf, fordi hver
kant har to ender. Bruk det som kontrollregning: får du en gradsum som er et
oddetall, har du telt feil.

I en rettet graf splittes graden i to: $\text{inngrad}(v)$ er antall
kanter som peker inn til $v$, og $\text{utgrad}(v)$ er antall kanter som
peker ut fra $v$.

Her er summen $\sum \text{inngrad}(v) = \sum \text{utgrad}(v) = |E|$ —
altså $|E|$, ikke $2|E|$, fordi hver rettet kant bidrar med én inngrad og én
utgrad. Å bruke $2|E|$-regelen på en rettet graf er en klassisk bom. Inngrad
0 og utgrad 0 blir dessuten helt sentrale begreper i
kap. 5.4.

En rekke noder der hvert par etter hverandre er forbundet med en kant, og
ingen node gjentas. Lengden på stien er antall kanter i den, ikke antall
noder.

En sti fra $u$ til $v$ er svaret på «kommer jeg fram?». At det finnes en sti
sier ingenting om at den er kortest — å finne den korteste er en egen
oppgave, og verktøyet kommer i kap. 5.2.

En sti som starter og ender i samme node, og som ellers ikke gjentar noen
node. I en urettet graf krever en sykel minst tre kanter, siden det å gå fram
og tilbake over den samme kanten ikke teller.

En sykel betyr at det finnes minst to ulike veier mellom to av nodene — altså
en omvei. En graf uten sykler kalles asyklisk.

En urettet graf der det finnes en sti mellom hvert par av noder.

Er den ikke sammenhengende, deler den seg i flere biter. Merk at én eneste
node uten kanter er nok til å ødelegge sammenhengen: en graf med 500 noder
som alle henger sammen, pluss én ensom node, er ikke sammenhengende.

En maksimal bit av grafen der alle nodene kan nå hverandre. En
sammenhengende graf har nøyaktig én komponent; en graf med tre atskilte øyer
har tre.

En node helt uten kanter er en komponent for seg selv. Å telle
komponenter er en egen algoritmeoppgave, og den kommer i
kap. 5.3 — her skal du bare kunne se dem.

En urettet graf som er sammenhengende og uten sykler.

Kjennetegnet du kan regne på: et tre har nøyaktig $|E| = |V| - 1$ kanter.
Begge kravene må være oppfylt — en graf med $|V| - 1$ kanter som ikke henger
sammen, er ikke et tre. Legger du én kant til et tre, får du nøyaktig én
sykel; fjerner du én kant, faller treet i to komponenter.

Grafen lagret som én liste per node, med nodens naboer i.

Plass: $O(|V| + |E|)$ — én listeoverskrift per node, pluss én oppføring
per kantende (i en urettet graf står hver kant to ganger, men $2|E|$ er
fortsatt $O(|E|)$).
Ramse opp naboene til v: $O(\text{grad}(v))$ — du leser bare nodens
egen linje.
Spørre om kanten (u, v) finnes: $O(\text{grad}(u))$ — du må lete
gjennom linja.

Dette er standardvalget i IN2010, og grunnen til at grafkjøretider skrives
$O(|V| + |E|)$.

Grafen lagret som en tabell $M$ med $|V|$ rader og $|V|$ kolonner, der
$M[u][v] = 1$ hvis kanten finnes og 0 ellers. I en urettet graf er tabellen
speilsymmetrisk om diagonalen.

Plass: $O(|V|^2)$ — uansett hvor få kanter grafen har.
Spørre om kanten (u, v) finnes: $O(1)$ — ett direkte oppslag.
Ramse opp naboene til v: $O(|V|)$ — du må lese hele raden, også de
nullene som ikke er naboer.

Lønner seg når grafen er tett (nesten alle mulige kanter finnes) og
algoritmen stiller mange kantspørsmål.

I en Del 2-besvarelse skriver du hvilken representasjon du antar, og
hvilke felter en node har. En typisk formulering er: «Grafen er gitt som
nabolister; hver node v har feltet v.naboer.»

Sensor binder seg ikke til én representasjon — nabolister, nabomatrise og
objektstil godtas alle. Men uten antagelsen kan ikke kjøretiden din
kontrolleres mot algoritmen, og det trekkes. Regelen koster deg én linje og
er blant de billigste poengene i hele Del 2.

I en urettet graf er $\sum_{v \in V} \text{grad}(v) = 2|E|$.

Navnet kommer av at antall håndtrykk i et rom alltid telles dobbelt hvis du
spør hver person hvor mange hender de tok. Konsekvensene du bruker på
eksamen: gradsummen er alltid et partall, og $|E|$ finnes ved å dele den på
2. I en rettet graf gjelder i stedet
$\sum \text{inngrad}(v) = \sum \text{utgrad}(v) = |E|$.

For $|V| = 6$ gir det 15 kanter; for $|V| = 10$ gir det 45. En graf som
nærmer seg denne grensen kalles tett, og da — og først da — kan
nabomatrisen forsvares på plass. I en rettet enkel graf er grensen det
dobbelte, $|V| \cdot (|V| - 1)$.

En graf er tett når $|E|$ er i nærheten av $|V|^2$, og tynn når $|E|$
er nærmere $|V|$.

Nesten alle grafer i praksis er tynne: veinett, vennelister, lenkegrafer og
avhengighetsgrafer har alle en grad som er begrenset uansett hvor store de
blir. Det er hovedgrunnen til at naboliste er standardvalget, og til at
$O(|V| + |E|)$ er den kjøretiden du sikter mot.

Spørsmålet «går det en kant mellom disse to nodene?».

Nabomatrise: $O(1)$ — ett direkte oppslag i celle $(u, v)$.
Naboliste: $O(\text{grad}(u))$ — du må lete gjennom u-linja.

Dette er den ene operasjonen matrisen vinner klart på, og derfor det ene
argumentet for å velge den.

Å ramse opp alle nodene som deler en kant med v. Dette er den operasjonen
alle grafalgoritmer i faget bruker mest.

Naboliste: $O(\text{grad}(v))$ — du leser bare nodens egen linje.
Nabomatrise: $O(|V|)$ — du må lese hele raden, også alle nullene.

Summert over alle noder blir det $O(|V| + |E|)$ for nabolisten og $O(|V|^2)$
for matrisen. Det er nøyaktig derfor kjøretidene i resten av Del 5 skrives
$O(|V| + |E|)$, og hvorfor de blir $O(|V|^2)$ hvis du antar nabomatrise.