GRAFER

Question 1

Hva er en vektet graf?

Answer 1

En graf, der kantene har en verdi/kostnad knyttet til seg

Question 2

Hva er parallelle kanter?

Answer 2

Flere enn én kant mellom to noder.

Question 3

Hva er (enkle) løkker?

Answer 3

En kan som starter og slutter i samme node

Question 4

Hva er en enkel graf?

Answer 4

En graf som er urettet, uvektet, ingen løkker og ingen parallelle kanter.

Question 5

Hva er en rettet graf?

Answer 5

En graf der kantene har en retning

Question 6

Hva er en sti?

Answer 6

En sekvens av noder i grafen forbundet av kanter, der ingen noder gjentas.
Eks: A,B,C,D

Question 7

Hva er en vei?

Answer 7

En sekvens av noder i grafen forbundet av kanter, der ingen kanter gjentas.
Eks. A, B, C, A, D

Question 8

Kan en rettet graf ha sykler?

Answer 8

Ja, men da må kantene peke i “riktig” retning.

Question 9

Hva er graden til en node?

Answer 9

Hvor mange kanter den er koblet til.

Question 10

I en rettet grad skiller vi mellom to forskjellige grader, i tillegg til hovedgraden (samme som i urettet graf). Hva kalles disse?

Answer 10

Inn-grad og ut-grad

Question 11

Hva er en komplett graf?

Answer 11

En graf med en kant mellom hvert par av noder.

Question 12

Tre måter man kan representere grafer på?

Answer 12

Objektorientert (klasser)
Nabo-matrise
Nabo-liste

Question 13

Hva er en eulerkrets?

Answer 13

En krets som besøker alle kanter nøyaktig en gang, og som starter og slutter i samme node.

Question 14

Hva er en hamiltonsykel?

Answer 14

En sykel som besøker alle nodene i grafen nøyaktig én gang. Det må være en kant fra siste node til den første noden.

Question 15

Hva er O-notasjonen til både DFS og BFS?

Answer 15

O( |V| + |E| )

Question 16

Hva er en sammenhengende graf?

Answer 16

En graf der alle nodene er sammenkoblet

Question 17

Hvordan kan man enkelt se om en graf inneholder en sykel?

Answer 17

Hvis en graf har flere kanter enn noder

Question 18

Hvor mange kanter har spenntrær?

Answer 18

|V| - 1, der V er node

Question 19

Hvordan kan man finne den korteste stien mellom to noder på en uvektet graf?

Answer 19

Ved gjøre et BF-søk

Question 20

Når burde man bruke Dijkstra-algoritmen?

Answer 20

For å finne den korteste (billigste) stien mellom to noder i en vektet graf.

Question 21

Hva gjør Bellman-Ford-algoritmen?

Answer 21

Finner den korteste (billigste) stien mellom to noder i vektede grafer med negative kanter.

Question 22

Hva vil det si at en graf er x-node-sammenhengende?

Answer 22

At vi må fjerne x antall noder for at grafen ikke lenger er sammenhengende

Question 23

Hva er separasjonsnoder?

Answer 23

Noder som ved fjerning fører til at grafen ikke lenger er sammenhengende. Et kritisk punkt.

Question 24

Hvordan itererer primsalgoritmen gjennom en graf?

Answer 24

Ved å legge til noder basert på den billigste kanten. Treet vil alltid være sammenhengende

Question 25

Hvordan itererer Kruskals-algoritme gjennom en graf?

Answer 25

Kobler to og to noder sammen basert på de billigste kantene mellom to forskjellige trær.

Question 26

Hvordan vet vi at en node er en separasjonsnode?

Answer 26

Dersom node v sine etterkommere ikke har en back-edge til en forgjenger av v, er v en separasjonsnode

Question 27

Hva vil sterkt sammenhengende komponenter si?

Answer 27

Der hvor alle par av noder kan nå hverandre i en graf, vil disse være et sterkt sammenhengende komponent. Disse må være maksimale, det vil si at de ikke forblir sterkt sammenhengende om man tar med en node eller kant til.

Question 28

Hvordan kan man finne de sterkt sammenhengende komponentene i en graf?

Answer 28

Ved å bruke DFS to ganger. En på den vanlige grafen, og en på den reverserte (der kantene er reversert)