Sist endret: 23.09.2016  
 

Teorioppgave - Minimale spenntrær

[Oppgave] [Levering] [Løsningsforslag]

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

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


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


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


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


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


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


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


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


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


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


Ø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'.