Sist endret: 23.09.2016  
 

Løsningsforslag - Traversering av grafer (graf algoritmer)

[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.

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.

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

Nabolister
En lenket liste
En nabomatrise
Alle alternativene er like plasseffektive

Din kommentar:
LF-forklaring: Se Cormen s. 590

[ feil ]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 %)

$O(1)$
$O(|V|)$
$O(|E|)$
$O(|E| + |V|)$
$O(min(|V|,|E|))$

Din kommentar:
LF-forklaring: EDIT: Tidligere riktig løsning ($O(|V|)$) var ikke helt riktig. I situasjoner hvor vi ikke har en sammenhengende graf vil antall kanter være mindre enn antall noder.
I denne situasjonen vil $O(|E|)$ være riktig svar. Oppgaven spesifiserer at vi ikke vet noe om forholdet mellom antall noder og antall kanter i grafen.
GAMMEL FASIT: Nabolisten til node $u$ kan finnes i konstant tid. Deretter kjører vi lineærsøk gjennom nabolisten til $u$ helt til vi finner $v$,
eventuelt kommer til enden av listen uten å finne $v$.

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

$O(1)$
$O(|V|)$
$O(|E|)$
$O(|E| + |V|)$

Din kommentar:
LF-forklaring: Se Cormen s. 590

Oppgave 2

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

[ feil ]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 %)

Alle kantene har lik vekt
Alle kantene har lik ikke-negativ vekt
Ingen negative kanter

Din kommentar:
LF-forklaring: Hvis vi kan ha negative kanter blir korteste vei udefinert. Bredde-først-søk vil finne korteste vei der alle kanter har lik vekt (den ser egentlig bort fra vekt og finner korteste vei i antall kanter).

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

Sant
Usant

Din kommentar:
LF-forklaring:

[ feil ]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 %)

Tree edge
Back edge
Cross edge

Din kommentar:
LF-forklaring: Se Cormen s. 609

[ feil ]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 %)

Sant
Usant

Din kommentar:
LF-forklaring: Dette er ikke alltid sant. Det kan også være en forward edge.

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.)

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

1
2
3
4
5

Din kommentar:
LF-forklaring:

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

1
2
3
4
5

Din kommentar:
LF-forklaring:

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

Tree edge
Forward edge
Back edge
Cross edge

Din kommentar:
LF-forklaring: Kan sees ved å fargelegge grafen under kjøringen av DFS. Vil da se at kanten traverseres fra node P til node O på ettidspunkt hvor node O er grå.

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

Tree edge
Forward edge
Back edge
Cross edge

Din kommentar:
LF-forklaring: Node Y besøkes for første gang fra node O.

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

Tree edge
Forward edge
Back edge
Cross edge

Din kommentar:
LF-forklaring:

Oppgave 4

Følgende graf er brukt på alle deloppgaver:


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

A, B, F, G, C, H, I, D, E
A, E, D, C, I, H, B, F, G
E, A, I, D, C, H, B, F, G
E, A, D, C, I, H, B, G, F

Din kommentar:
LF-forklaring:

[ riktig ]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 %)

Den må være rettet og asyklisk (en DAG)
Den må ha positive kantvekter
Alle kantvektene må være like
Alle alternative over er riktige

Din kommentar:
LF-forklaring: Se Cormen kapittel 22.4 (s. 612)