22 Vandringer i grafer Flashcards
22.1 Vandringer og stier
En vandring eller tur av lengde n i en graf er en sekvens av noder og kanter på formen
v0e1v1e2v2 … envn
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.
22.2 Kretser og sykler
En vandring hvor den første og siste noden sammenfaller kalles lukket. En lukket vandring hvor ingen kant forekommer mer enn én gang kalles en krets. En sti v1v2 … vn med minst tre noder, sammen med kanten som forbinder vn og v1, kalles en lukket sti eller en sykel av lengde n. En graf uten sykler kalles asyklisk.
22.3 Sammenhengende graf
En graf er sammenhengende 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.
22.4 Tre
Et tre er en sammenhengede, asyklisk graf. En node med grad én i et tre kalles en løvnode. En graf hvor alle komponentene er trær kalles en skog.
22.5 Eulervei / Eulerkrets
La G være en sammenhengende graf. En Eulervei er en vandring som inneholder hver kant fra G nøyaktig én gang. En Eulerkrets er en Eulervei hvor den første og den siste noden sammenfaller. En sammenhengende graf som har en Eulerkrets kalles en Eulersk graf.
22.6 Hamiltonsti / Hamiltonsykel
La G være en sammenhengende graf. En Hamiltonsti er en sti som inneholder hver node fra G nøyaktig én gang. En Hamiltonsykel er en sykel som inneholder hver node fra G nøyaktig én gang. En graf som har en Hamiltonsykel kalles Hamiltonsk.
