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.
Incidensmatris
Ett sätt att representera grafer i dator.
En incidentmatris för en graf är en matris där det finns en rad för varje hörn och en kolumn för varje kant.
Träd
Sammanhängande grafer utan cykler
Bredden-först
Vid bredden-först startar man i roten av ett träd (eller delträd) som ska sökas igenom. Man går i tur och ordning till de hörn som är på nivå 1 under roten. När det inte finns fler sådana hörn fortsätter man med hörnen på nivå 2. Fortsätt nedåt, nivå för nivå tills hela träden har sökts igenom (eller man har funnit det man söker efter)
Djupet-först
Vid djupet-först startar man i roten och går därifrån till den första grannen på nivå 1. Därifrån fortsätter man till första granne på nivå 2 och så vidare nedåt i trädet tills man når ett löv. Då backar man uppåt tills man finner någon ny väg nedåt man inte tidigare har besökt, och följer på samma sätt denna väg i botten, backar upp igen, etc. Så håller man på tills man har besökt samtliga noder i grafen (eller om man har funnit det man söker efter).
Binära träd
Ett rotat träd där varje hörn har plats för exakt två barn, varav ett till vänster och ett till höger
Inordning
Denna ordning specificeras rekursivt. Börja med att gå igenom vänster delträd i inordning. Ta sedan roten. Avsluta med att gå igenom höger delträd i inordning.
Preordning
Börja med roten. Gå sedan igenom vänster delträd i preordning. Avsluta med att gå igenom höger delträd i preordning.
Postordning
Börja med att gå igenom vänster delträd i postordning. Gå sedan igenom höger delträd i postordning. Avsluta med roten.
