Begreper & referanser
Alle nøkkelbegrepene, formlene og referansene fra Grafer og traversering, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.
Begreper
Sentrale begreper fra kapittelet med korte definisjoner.
En grafrepresentasjon der hver node har en liste over sine naboer. Plass , god for glisne grafer.
En -tabell der celle angir om kanten finnes (eller dens vekt). Konstant kantoppslag, plass .
En traversering som utforsker grafen lagvis fra en kilde med en kø, og finner korteste vei i antall kanter.
En traversering som graver så langt den kan før den rygger tilbake. Gir oppdagings- og ferdigtider.
En lineær ordning av nodene i en rettet asyklisk graf der hver kant peker framover.
En rettet asyklisk graf — en rettet graf uten sykler. Tillater alltid en topologisk sortering.
En maksimal mengde noder der alle kan nå alle andre langs rettede kanter.
I DFS en kant til en forfar i søketreet; eksistensen av en tilbakekant betyr at grafen har en sykel.
Formler
Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.
Plass for nabolister vs. nabomatrise
Nabolister er kompakte for glisne grafer; nabomatrisen gir konstant-tids kantoppslag, men bruker kvadratisk plass uansett tetthet.
Kjøretid for BFS og DFS
Begge traverseringene besøker hver node én gang og utforsker hver kant et konstant antall ganger — lineært i grafens størrelse med nabolister.
Parentes-teoremet
Oppdagings- og ferdigtidene i DFS er korrekt parentes-strukturert: intervaller overlapper aldri delvis. Grunnlaget for at DFS gir en gyldig topologisk orden.
Topologisk sortering
En lineær orden av nodene i en rettet asyklisk graf der hver kant peker framover. Finnes hvis og bare hvis grafen ikke har en sykel.
Hvit-sti-teoremet
I DFS blir en etterkommer av nøyaktig når det finnes en sti av uoppdagede (hvite) noder fra til idet oppdages.
Læringsmål
Hva du skal kunne etter å ha lest kapittelet.
- 01Velge mellom naboliste og nabomatrise ut fra om grafen er glissen eller tett, og begrunne valget med plassforbruk
- 02Kjøre BFS på en graf med en kø, lese av lagene, og forklare hvorfor BFS gir korteste vei i antall kanter
- 03Kjøre DFS med oppdagings- og ferdigtider, og forklare parentes-teoremet, hvit-sti-teoremet og hva en tilbakekant betyr
- 04Finne en topologisk orden i en DAG via DFS-ferdigtider, og forklare hvordan to runder DFS gir sterkt sammenhengende komponenter