Sist endret: 23.09.2016  
 

Teorioppgave - Traversering av grafer (graf algoritmer)

[Oppgave] [Levering] [Løsningsforslag]

Innleveringsfrist: 23.10.2017 15:00

NB! Du er ikke innlogget. Logg inn for å få frem det du har skrevet tidligere.
Dersom du har levert øvingen fra før, vil det du har levert bli slettet dersom du klikker på 'Vis alternativer'

NB! Det du skriver i tekstfeltene blir ikke vurdert som en del av besvarelsen. De er kun til eget bruk, før du velger 'Vis alternativer'.

Oppgave 1

For hele den følgende oppgaven brukes notasjonen $G = (V,E)$ for å representere en graf $G$. $V$ er mengden noder, $E$ er mengden kanter.

a) Gitt at $|V| = |E|$. Hvordan kan grafen $G$ lagres mest plasseffektivt i denne situasjonen? (7.1 %)


b) Gitt to noder, $u, v \in V$. Hvor lang tid vil det ta å sjekke om det finnes en kant, $e \in E$, som går fra $u$ til $v$ gitt at grafen $G$ er representert ved hjelp nabolister?
Anta at du ikke vet noe om hvor mange kanter eller hvor mange noder det finnes i $G$.
(7.1 %)


c) Hvor lang tid vil tilsvarende oppslag ta hvis $G$ var representert ved hjelp av en nabomatrise? (7.1 %)


Ønsker gjennomgang: (Sett kryss dersom du ønsker at oppgaven ovenfor skal bli gjennomgått på øvingsforelesning)

Oppgave 2

Følgende oppgaver omhandler pensum dekket i kapitlene 22.2 (Breadth-first search) og 22.3 (Depth-first search).

a) For hvilket av alternativene under er vi garantert at bredde-først-søk finner korteste vei i en vilkårlig sammenhengende graf? (7.1 %)


b) Et bredde-først-søk implementeres vanligvis ved hjelp av ekø (queue)? (7.1 %)


c) Et dypde-først-søk kan brukes til å klassifisere kantene i en graf.
Hvilken av følgende kanttyper betegner en kant som går fra en forgjenger (ancestor) til en etterkommer (descendant)?
(7.1 %)


d) Hver gang vi kommer til en node i et dypde-først-søk som allerede er farget svart vet vi at kanten vi brukte for å komme oss hit må være en cross edge. (7.1 %)


Ønsker gjennomgang: (Sett kryss dersom du ønsker at oppgaven ovenfor skal bli gjennomgått på øvingsforelesning)

Oppgave 3

Følgende graf er brukt på alle deloppgaver:



Følgende 5 sekvenser er 5 mulige måter å traversere grafen på:

1. Q,E,W,T,U,I,O,A,D,P,S,F,Y,R
2. Q,E,R,W,Y,T,I,O,U,P,A,D,S,F
3. Q,E,W,T,U,I,O,A,D,F,P,S,Y,R
4. Q,E,R,W,Y,O,I,T,U,A,P,D,S,F
5. Q,E,R,W,Y,T,I,O,U,A,P,S,D,F

Anta at alle konflikter løses ved hjelp av leksikografisk ordning (ved eventuelle konflikter velges den noden med bokstav tidligst i alfabetet, altså A før B, B før C osv.)

a) Hvilken av seksvensene tilsvarer et bredde-først-søk? (7.1 %)


b) Hvilken av sekvensene tilsvarer et dypde-først-søk? (7.1 %)


c) Hvilken klassifikasjon vil kanten mellom node P og O få ved et dybde-først-søk? (7.1 %)


d) Hvilken klassifikasjon vil kanten mellom node O og Y få ved et dybde-først-søk? (7.1 %)


e) Hvilken klassifikasjon vil kanten mellom node I og P få ved et dybde-først-søk? (7.1 %)


Ønsker gjennomgang: (Sett kryss dersom du ønsker at oppgaven ovenfor skal bli gjennomgått på øvingsforelesning)

Oppgave 4

Følgende graf er brukt på alle deloppgaver:


a) Hvilke av følgende alternativ er en gyldig topologisk sortering av grafen? (7.1 %)


b) Du ønsker å lage en topologisk sortering av en graf $G=(V,E)$.
Hvilke av følgende kriterier må være sanne (for grafen $G$) for at det skal finnes en topologisk sortering?
(7.1 %)


Ønsker gjennomgang: (Sett kryss dersom du ønsker at oppgaven ovenfor skal bli gjennomgått på øvingsforelesning)

Stikkord til forelesning

Du får mer utbytte av en forelesning dersom du på forhånd vet helt overfladisk hva den handler om. Du bør ane hva stikkordene for neste forelesning betyr.
Skriv gjerne ned kommentarer til stikkordene for neste forelesning og se over dem på neste teoriøving.

Kommentarer til stikkordene er kun til eget bruk og blir ikke vurdert av andre.

Det er ikke lagt inn noen stikkord for neste forelesning.


Eventuelt tidligere innlevering vil bli OVERSKREVET om du klikker på 'Vis alternativer'.