22 Vandringer i grafer Flashcards
vandringer og stier
En vandring (eng: walk) eller tur av lengde n i en graf er en sekvens av noder og kanter på formen
v0 e1 v1 e2 v2 … en vn
hvor ei er en kant som forbinder vi-1 og v1 for i ∈ {1, 2, …, n}. Vi sier at sekvensen går fra v0 til vn. Hvis ingen node forekommer mer enn én gang, kalles den en sti (eng: path).
kretser og sykler
En vandring hvor den første og siste noden sammenfaller kalles lukket (eng: closed). En lukket vandring hvor ingen kant forekommer mer enn én gang kalles en krets (eng: circuit). En sti v1 v2 … vn med minst tre noder, sammen med kanten som forbinder vn og v1, kalles en lukket sti (eng: closed path) eller en sykel (eng: cycle) av lengde n. En graf uten sykler kalles asyklisk (eng: acyclic).
sammenhengende
En graf er sammenhengende (eng: connected) hvis det finnes en sti mellom alle par av noder i grafen, det vil si at det er mulig å komme fra enhver node til enhver annen node ved å følge kantene.
tre
Et tree (eng: tree) er en sammenhengede, asyklisk graf. En node med grad én i et tre kalles en løvnode (eng: leaf node). En graf hvor alle komponentene er trær kalles en skog (eng: forest).
Eulervei/Eulerkrets
La G være en sammenhengende graf. En Eulervei (eng: Euler trail) er en vandring som inneholder hver kant fra G nøyaktig én gang. En Eulerkrets (eng: Euler circuit) er en Eulervei hvor den første og den siste noden sammenfaller. En sammenhengende graf som har en Eulerkrets kalles en Eulersk graf.
Hamiltonsti/Hamiltonsykel
La G være en sammenhengende graf. En Hamiltonsti (eng: Hamiltonian path) er en sti som inneholder hver node fra G nøyaktig én gang. En Hamiltosykel (eng: Hamiltonian cycle) er en sykel som inneholder hver node fra G nøyaktig én gang. En graf som har en Hamiltonsykel kalles Hamiltonsk (eng: Hamiltonian).
