Sist endret: 17.08.2010

Løsningsforslag - Topologisk sortering og minimale spenntrær

Innleveringsfrist: 30.09.2011 10: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å algdats nyhetsgruppe. Denne nyhetsgruppen har også et webgrensesnitt.

Oppgave 1

Relevant pensum: 22.4 Topologisk sortering. (22.1-22.3) (Cormen), 3.6 Directed Acyclic Graphs and Topological Ordering (Kleinberg)

I første deloppgave undersøker algoritmen grafens noder i omvendt alfabetisk rekkefølge. I grafen vil også en nodes naboer behandles i omvendt alfabetisk rekkefølge.

a) Hvilken topologisk sortering vil Topological-Sort(G) komme fram til på grafen over? Bruk versjonen av topologisk sortering som benytter seg av DFS. (12.5 %)

m,n,p,o,q,s,r,t
p,n,o,s,m,r,q,t
p,n,m,s,r,t,q,o

Din kommentar:
LF-forklaring:	Kjør topologisk sortering der med alfabetisk prioritering på DFS-søket. Da finner du ut at alternativ 2 stemmer.

b) I dette søket er kanten (O,R) en : (7.5 %)

Tre - kant? (Tree edge)
Tilbake - kant? (Back edge)
Framover - kant? (Forward edge)
Kryss - kant? (Cross edge)

Din kommentar:
LF-forklaring:	(O,R) er ikke i dybde - først skogen, og selv om R er en etterkommer av O er ikke dette en Forward edge da kanten går mellom to trær i dybde først skogen.

Gitt følgende kode:

DFS(G):
    i = 0
    for vertex in G.V:
        if not vertex.visited:
            i += 1
            DFS-VISIT(G, vertex)
    return i

(DFS-VISIT(G, vertex) kjører et standard dybde-først søk fra node vertex i graf G)

c) Hva gjør koden? (10 %)

Teller antall sykler i grafen.
Teller antall noder.
Teller antall trær i dybdeførst skogen.
Teller antall framoverkanter i grafen.

Din kommentar:
LF-forklaring:	Merk her at det var DFS[G] vi spurte om, ikke DFS-visit[G]. Da får vi at det blir lagt til en på i hver gang DFS-søket må starte fra en ny node som ikke har vært besøkt tidligere. Dette fører til at man teller antall trær i dybdeførst-skogen, eller med andre ord, hvor mange ganger DFS-søket må starte fra en ny node.

Oppgave 2

Et lite land langt, langt borte består av en mengde øyer. Innbyggerne har lenge samlet inn penger for å få veiforbindelse i mellom alle øyene. Prislappen på broene er kun avhengig av broenes lengder og de ønsker derfor å binde i sammen broene med kortest mulig samlet brolengde.

a) Hvor mange broer vil du trenge dersom det er n øyer? (2.5 %)

n-1
n
n*lg(n)
n^2 - 1
n^2]

Din kommentar:
LF-forklaring:

En venn av deg hevder at du har en algoritme som kan løse dette problemet i O(n*lg(n)) tid, der n er antall øyer. Du er kanskje litt mer tvilende og mener at kjøretiden vil bli O(n^2).

b) Hvem har rett? (10 %)

Kameraten din
Du

Din kommentar:
LF-forklaring:	Dette er en minimal-spenntre oppgave på en tett graf (\|E\| = \|V\|^2), og dermed kan vi ikke gjøre noe bedre enn O(V^2).

c) Gitt en urettet, vektet, sammenhengende graf G = (V,E). Hvordan skal vi gå frem for å finne et spenntre som minimerer vekten på den dyreste kanten i treet? (Treets totale vekt er uvesentlig.) (10 %)

Prims algoritme
Kruskals algoritme
Begge deler fungerer
Ingen fungerer, vi trenger en annen algoritme.

Din kommentar:
LF-forklaring:	Se løsningsforslag på oppgave 2, eksamen august 1992.

I figuren over er det tegnet en graf med tilhørende minimalt spenntre. Ta utganspunkt i definisjonene gitt i kapittel 23 (Cormen) og kapittel 4. og svar på følgende spørsmål.

d) Gitt subsettet A bestående av kantene (J,N),(N,K),(N,O) og subsettet B = (C,G),(G,H),(G,L),(H,Q). Hvilket av følgende utsagn er riktige? (5 %)

B er et subsett av det minimale spenntreet.
Kanten (J,E) er en trygg kant for A
Kanten (N,K) er en trygg kant for B
Kanten (J,M) er en trygg kant for A

Din kommentar:
LF-forklaring:	Kanten (J,M) kan legges til A slik at A union med (J,M) fortsatt er et subsett av det minimale spenntreet. Og er derfor per definisjon en trygg kant.

Oppgave 3

Minimale spenntrær

Er følgende utsagn sanne eller usanne?

a) Hvis kanten E er den kanten med lavest vekt i en sammenhengende graf, så er E med i ett og bare ett MST i grafen. (5 %)

Sant
Usant

Din kommentar:
LF-forklaring:	E kan være med i flere MST

b) Hvis kanten E har lavere vekt enn alle de andre kantene i en sammenhengende graf, så er E med i alle MST i grafen (5 %)

Sant
Usant

Din kommentar:
LF-forklaring:	Se Kruskals algoritme.

c) Hvis alle kantene i en sammenhengende graf har forskjellige vekter, vil grafen kun ha ett minimalt spenntre. (5 %)

Sant
Usant

Din kommentar:

LF-forklaring:

Vi beviser dette ved motbevis. Hvis utsagnet ikke er sant, vil det si at det finnes en vekt e mellom node A og B som kan erstattes med en annen vekt f mellom node A og C. f kan ikke ha en mindre verdi enn e (ellers vil ikke treet som inneholder e være et minimalt spenntre), så verdien til f er nødvendigvis lik verdien til e. Men siden alle vektene er distinkte er ikke dette mulig. Derfor er utsagnet sant.

d) Dersom kantene i en sammenhengende graf ikke har forskjellige vekter, vil denne grafen nødvendigvis ha flere minimale spenntrær. (5 %)

Sant
Usant

Din kommentar:

LF-forklaring:

Det holder å bevise at dette er usant for minst ett tilfelle: Vi antar at kanten mellom nodene A og B har vekten e_v = 2. Vi antar også at kanten mellom nodene C og D har vekten f_v = 2. A og C, A og D, B og C, B og D har ingen vekt mellom hverandre. 2 er verdien til den minste vekten i grafen. Det minimale spenntreet til denne grafen vil inneholde både e og f. Hvis vi også antar at alle kantene utenom e og f har distinkte vekter, kan vi konkludere med at grafen kun har ett minimalt spenntre, selv om ikke alle vektene i grafen er distinkte.

Oppgave 4

Bruk figuren over for å svare på spørsmålene. Hvis du under kjøring av Prims eller Kruskals algoritme kan velge mellom to eller flere kanter med lik vekt skal du velge den som er mellom noder av lavest leksikals verdi.

a) Det minimale spenntreet for grafen består av kantene? (7.5 %)

(a,f),(d,f),(b,d),(g,d),(b,c),(c,e),(c,h),(h,j),(i,j)
(b,e),(c,e),(c,h),(h,j),(i,j),(b,d),(a,d),(a,f),(h,g)
(a,f),(a,d),(a,b),(c,b),(c,e),(c,h),(h,g),(h,j),(i,j)
(i,j),(h,j),(c,h),(c,e),(c,b),(a,f),(a,d),(b,d),(d,g)

Din kommentar:
LF-forklaring:

b) Hvis man bruker Prims algoritme med startnode j, da velges (d,b) som kant nummer? (7.5 %)

5
6
7
8
9

Din kommentar:
LF-forklaring:

c) Hvis man bruker Kruskals algoritme, hvilken kant blir lagt til etter (a,d)? (7.5 %)

(b,e)
(b,c)
(i,j)
(d,g)
(h,j)

Din kommentar:
LF-forklaring: