Grafer, träd och cykler Flashcards
Vad är en väg?
Sekvens av angränsande bågar.
Vad är en cykel?
Väg som startar och slutar i samma nod.
Vad är en enkel väg?
En väg som inte innehåller några cykler.
Vad är en sammanhängande graf?
En graf som har en väg mellan varje nod par.
Vad är ett träd?
En sammanhängande graf utan cykler.
Vad är en fullständig graf?
En graf som har en båge mellan varje par av noder.
Vad är en tudelad graf?
En graf där alla bågar går från en nodmängd till en annan.
Vad är en plan graf?
En graf som kan ritas så att inga bågar korsar varandra.
Vad är en Eulercykel?
En cykel (startar och slutar i samma nod) som använder varje båge exakt en gång.
Vad är en Hamilitoncykel?
En cykel (startar och slutar i samma nod) som passerar varje nod exakt engång.
Vad är en nods valens?
Det antal bågar som anlsuter till noden.
Hur vet man ifall en graf har en Eulercykel?
Om alla noder har en jämnvalens.
Hur sätter man upp ett 1-träd och vad används det till?
Exkludera startnoden och finn ett MST. Inkludera sedan två billigaste bågarna till startnoden. Används som undergräns för TSP.
Vad är TSP?
Handelsresandeproblemet. Besök varje nod i grafen exakt en gång.
Vad är ett reduktionstest?
Försök minska problemstorleken för ett TSP. Tex har en nod bara två i valens måste båda bågarna vara med.
Vad är ett MST?
Ett uppspännande träd är en sammanhängande delgraf med minimalt antal bågar. (Alla noder måste inkluderas)
Hur finner man ett MST?
Kruskals-metod: Ta med billigate återstående båge förutsatt att ingen cykel skapas.
Prims-metod: Ta med billigaste båge som utökar delträdet.
Vad är brevbärarproblemet?
Finn en brevbärartur som är en cykel som använder varje båge minst en gång.
Vad är kinesiska brevbärarproblemet?
Finn den billigaste brevbärarturen.
När finns en Eulercykel i en graf?
Om.m grafen är sammanhängande och alla dess noder har jämn valens.
Vad är en oberoende nodmängd?
Mängd noder sådan att det inte finns någon direkt båge mellan två noder i mängden.
Vad är en nodövertäckning?
Är en nodmängd sådan att varje båge i grafen ansluter till minst en nod i nodmängden.
Vad är ett klick?
Nodmängden som spänner upp fullständig subgraf, dvs en nodmängd med direkt direktbågar mellan varje par av noder.
Vad är en bågövertäckning?
Den bågmängden sådan att varje nod i grafen ansluter till minst en båge i mängden.
