Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
7 Cards in this Set
- Front
- Back
|
Vad är en graf och vad består den av? |
Ett ordnat par av två ändliga mängder V och E V är G:s hörnmängd, noderna E är G:s kantmängd och består av två hörn |
|
|
Vad innebär det att två hörn är grannar? |
Att de är förbundna med en kant |
|
|
Hur kan en graf representeras? |
(1) Genom att man skriver upp mängden V och delmängden E (2) Genom att man ritar en figur (3) Genom att man använder en grann- eller incidensmatris |
|
|
Vilka är de olika sätten att röra sig i en graf?
|
(1) Vandring - förflyttning mellan hörn via kanter (2) Väg - vandring som inte använder samma kant flera gånger (3) Stig - väg som inte använder samma hörn flera gånger (4) Krets - väg (använder inte samma kant) som börjar och slutar i samma hörn (5) Cykel - stig (använder inte samma hörn) som börjar och slutar i samma hörn |
|
|
Vad är en Eulerkrets och Hamiltoncykel? |
En Eulerkrets använder alla kanter i en graf En Hamiltoncykel passerar alla hörn i en graf |
|
|
Vad krävs för att två grafer ska vara isomorfa? |
Två grafer är isomorfa om de har: - Lika många hörn - Lika många kanter - Hörn som motsvarar varandra har lika många grannar - För varje sätt vi kan "gå" mellan hörn i G1 finns ett motsvarande sätt att gå i G2 |
|
|
Vad är ett träd? Vilka algoritmer kan användas för genomsökning av ett träd? |
Ett träd är en sammanhängande graf utan cykler Kan genomsökas med bredden först-sökning och djupet först-sökning |
