Föreläsning 4 - grafer

Question 1

Vad är en tudelad graf?

Answer 1

En graf där noder kan delas i två nodmängder där inga noder i samma mängd är närliggande (båge emellan)

Question 2

Vad är en plan graf?

Answer 2

En graf som kan ritas så inga bågar korsas

Question 3

Vad avgör en grafs minsta nodfärgning?

Answer 3

Antalet nodfärger kan inte vara fler än antalet noder i den minst klicken (men kan vara större)

Question 4

Vad avgör en grafs minsta bågfärgning?

Answer 4

Noden med högst valens anger minsta antal färger (möjligt högre, testa!)

Question 5

Vad är en Eulercykel? Hur beräknas den?

Answer 5

En cykel som passerar alla bågar exakt en gång. Går endast då alla nåder har jämn valens

Question 6

Vad är en Hamiltoncykel?

Answer 6

En cykel som passerar alla noder exakt en gång

Question 7

Vad är billigaste uppspännande träd och hur löses det?

Answer 7

Billigaste väg att besöka varje nod. Löses med Kruskals eller Prims metod

Question 8

Vad är handelsresandeproblemet och hur löses det?

Answer 8

Kortaste rundtur som besöker alla noder. I lösningen har varje nod valens 2. Löses med 1-träd sen justera till valens 2 för varje nod. HAMILTONCYKEL

Question 9

Vad är kinesiska brevbärarproblemet och hur löses det?

Answer 9

Kortaste rundtur där varje båge besöks minst en gång. EULERCYKEL => Alla noder ska ha jämn valens