Sist endret: 23.09.2016  
 

Teorioppgave - Maks flyt og NPC

[Oppgave] [Levering] [Løsningsforslag]

Innleveringsfrist: 20.11.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) Hva er maks flyt-problemet? (4.8 %)


b) Hva betyr notasjonen 11/16 mellom node $s$ og $v_1$? (4.8 %)


c) Hva er galt med dette flytnettverket?



(4.8 %)


d) Hva er $f(v_3, v_2)$ i dette flytnettverket? (4.8 %)


e) Hva er galt med dette flytnettverket?



(4.8 %)


f) Hva er $c_f(v_3, v_2)$ i dette flytnettverket? (4.8 %)


g) Hvor stor er flyten $|f|$ i følgende graf?



(4.8 %)


h) Hvilke av disse stiene er en flytforøkende sti (augmenting path)? (4.8 %)


i) Hva er maks flyt mellom $s$ og $t$? (4.8 %)


Ønsker gjennomgang: (Sett kryss dersom du ønsker at oppgaven ovenfor skal bli gjennomgått på øvingsforelesning)

Oppgave 2

a) Et snitt $(S, T)$ av et nettverk er en partisjonering av nodene $V$ i et nettverk slik at $s \in S$ og $t \in T$ og gjelder $T = V + S$. (4.8 %)


b) Hva er et minimalt snitt? (4.8 %)


c) Kapasiteten til det minimale snittet trenger ikke nødvendigvis være lik den maksimale flyten for et gitt nettverk. (4.8 %)


Ønsker gjennomgang: (Sett kryss dersom du ønsker at oppgaven ovenfor skal bli gjennomgått på øvingsforelesning)

Oppgave 3

a) P $\subseteq$ NP (4.8 %)


b) P $\subseteq$ NPC (4.8 %)


c) NP $\subseteq$ NPC (4.8 %)


d) Dersom vi kan vise at et problem i NP kan løses i polynomisk tid må P=NP. (4.8 %)


Ønsker gjennomgang: (Sett kryss dersom du ønsker at oppgaven ovenfor skal bli gjennomgått på øvingsforelesning)

Oppgave 4

Du får oppgitt et problem $X$, og ønsker å finne ut hvilken kompleksitetsklasse problemet tilhører. Hvilke utsagn er sanne?

a) Du sammenlikner $X$ med problemet $Y$, som kan løses i polynomisk tid. (4.8 %)


b) Du sammenlikner $X$ med problemet $Z$, som er NP-komplett. (4.8 %)


Ønsker gjennomgang: (Sett kryss dersom du ønsker at oppgaven ovenfor skal bli gjennomgått på øvingsforelesning)

Oppgave 5

Du har problemene $A$, $B$ og $C$. Alle tre er i NP. Du vet at $A$ er i P og $B$ er i NPC. I denne oppgaven menes det med "reduksjon" en reduksjon i polynomisk tid.

a) Hvilken av følgende reduksjoner viser at C er i P? (4.8 %)


b) Hvilken av følgende reduksjoner viser at C er i NPC? (4.8 %)


c) Hvilken av følgende reduksjoner viser at P=NP? (4.8 %)


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