Begrepp - Kapitel 6 Flashcards
Nod/Hörn
En knutpunkt
Kant/Båge
En förbindelse
Grad
Antalet kanter som går ut från noden
Granne
Två noder som har en kant mellan sig är grannar i grafen
Stig
En väg som är sluten, det vill säga börjar och slutar i samma nod
Cykel
En sluten stig
Sammanhängande komponent
En graf som inte är sammanhängande sönderfaller i ett antal sammanhängande komponenter, det vill säga delar som var och en är sammanhängande men som saknar förbindelser sinsemellan
Komplett graf
En graf är komplett om varje par av noder är förbundna men en kant
Delgraf
En delgraf till en graf G är en graf G’ som utförs av en delmängd av G:s noder och kanter
Bipartit graf
En graf är bipartit om nodmängden kan delas upp i två disjunkta delmängder sådana att alla kanter går mellan vänster och höger nodmängd
Riktad graf
Om kanterna i en graf går att passera år ett håll har man en riktad graf
Hamiltoncykel
En sluten hamiltonstig.
Hamiltonstig är en stig som besöker varje hörn i grafen exakt en gång
Eulerkrets
En sluten eulerväg.
Eulerväg är en väg som går längs varje kant i grafen exakt en gång
Isomorfi
Likhet mellan grafer
Grannmatris
Ett sätt att representera grafer i dator.
I grannmatrisen ger varje hörn en rad och en kolumn.
