[Oppgave] [Levering] [Løsningsforslag]
Innleveringsfrist: 23.10.2017 15:00
Du er logget inn og får derfor se om du har svart riktig/feil på de enkelte oppgavene. LF-svar er markert med grønt og feil svar er markert med rødt.
Hvis dere er uenige i fasit, oppfordres dere til å diskutere dette på Piazza.
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 %)
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 %)
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.)
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 %)
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 %)