Sist endret: 23.09.2016  
 

Løsningsforslag - Minimale spenntrær

[Oppgave] [Levering] [Løsningsforslag]

Innleveringsfrist: 30.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

[ riktig ]a) 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. Hvor mange broer vil du trenge dersom det er n øyer? (10 %)

n-1
n
n*lg(n)
n2-1
n2

Din kommentar:
LF-forklaring: Du bygger et minimalt spenntre, og det har n-1 kanter.

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

[ riktig ]c) Hvis kanten E er den kanten med lavest vekt i en sammenhengende graf, så er E med i ett og bare ett minimalt spenntre i grafen. (10 %)

Sant
Usant

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

[ riktig ]d) Hvis kanten E har lavere vekt enn alle de andre kantene i en sammenhengende graf, så er E med i alle minimale spenntrær i grafen. (10 %)

Sant
Usant

Din kommentar:
LF-forklaring: Dette fremgår av Kruskals algoritme, som alltid velger den kanten med lavest vekt først.

[ riktig ]e) Hvis alle kantene i en sammenhengende graf har forskjellige vekter, vil grafen kun ha ett minimalt spenntre. (10 %)

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.

[ feil ]f) Dersom kantene i en sammenhengende graf ikke har forskjellige vekter, vil denne grafen nødvendigvis ha flere minimale spenntrær. (10 %)

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 ev = 2. Vi antar også at kanten mellom nodene C og D har vekten fv = 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.

[ feil ]g) Bilde av graf
Tegn et minimalt spenntre for denne grafen. Hvilke kantvekter inneholder det minimale spenntreet?
(10 %)

1, 2, 5, 7, 8, 9
1, 4, 5, 3, 9
1, 2, 3, 4, 6, 8
1, 3, 4, 6, 8

Din kommentar:
LF-forklaring:

[ feil ]h) Bilde av tre
Bruk figuren over for å svare på resten av 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 leksikalsk verdi (det som kommer først i alfabetet).
Det minimale spenntreet for grafen består av kantene?
(10 %)

(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:

[ riktig ]i) Hvis man bruker Prims algoritme med startnode j, da velges (d,b) som kant nummer ? (10 %)

5
6
7
8
9

Din kommentar:
LF-forklaring:

[ feil ]j) Hvis man bruker Kruskals algoritme, hvilken kant blir lagt til etter (a,d)? (10 %)

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

Din kommentar:
LF-forklaring: