Sist endret: 23.09.2016  
 

Løsningsforslag - Maks flyt og NPC

[Oppgave] [Levering] [Løsningsforslag]

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

Å bruke færrest mulig noder fra start til slutt.
Å få flyten mellom hver node til å være maksimal
Å finne en flyt av maksimal verdi gjennom et nettverk
Å opprettholde flyten

Din kommentar:
LF-forklaring:

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

$c(s,v_1) = 11$, $f(s, v_1) = 16$
$c(s,v_1) = 16$, $f(s, v_1) = 11$
$c(s,v_1) = 4$, $f(s, v_1) = 16$
$c(s,v_1) = 16$, $f(s, v_1) = 11/16$

Din kommentar:
LF-forklaring:

[ feil ]c) Hva er galt med dette flytnettverket?



(4.8 %)

$f(v_3, v_4) = 0$
$f(v_1, v_3) != -f(v_3, v_1)$
Det går ikke maksflyt igjennom det.
Flyten er ikke opprettholdt.

Din kommentar:
LF-forklaring:

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

0
-1
-7
7

Din kommentar:
LF-forklaring:

[ feil ]e) Hva er galt med dette flytnettverket?



(4.8 %)

$f(v_3, v_4) = 0$
$f(v_1, v_3) != -f(v_3, v_1)$
Det går ikke maksflyt igjennom det.
Flyten er ikke opprettholdt.

Din kommentar:
LF-forklaring:

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

0
1
-1
7
-7

Din kommentar:
LF-forklaring:

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



(4.8 %)

26
20
62
144

Din kommentar:
LF-forklaring:

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

$v_1$, $v_2$, $t$
$s$, $v_3$, $v_4$, $t$
$s$, $v_1$, $v_2$, $t$
$s$, $v_1$, $v_3$, $v_2$, $t$

Din kommentar:
LF-forklaring:

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

20
26
62
32

Din kommentar:
LF-forklaring:

Oppgave 2

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

Sant
Usant

Din kommentar:
LF-forklaring: $T = V - S$ er korrekt.

[ feil ]b) Hva er et minimalt snitt? (4.8 %)

En partisjonering av noder slik at mengden $S$ blir minst mulig.
En partisjonering av noder slik at færrest mulig kanter går mellom delmengdene.
En partisjonering av noder slik at kapasiteten til snittet er minst mulig.

Din kommentar:
LF-forklaring:

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

Sant
Usant

Din kommentar:
LF-forklaring:

Oppgave 3

[ riktig ]a) P $\subseteq$ NP (4.8 %)

sant
usant
uvisst

Din kommentar:
LF-forklaring: P kan løses i polynomisk tid, og kan dermed også sjekkes for korrekthet i polynomisk tid

[ feil ]b) P $\subseteq$ NPC (4.8 %)

sant
usant
uvisst

Din kommentar:
LF-forklaring: Hvis P er i NPC kan NP reduseres til P i polynomisk tid - hvilket ikke stemmer.

[ feil ]c) NP $\subseteq$ NPC (4.8 %)

sant
usant
uvisst

Din kommentar:
LF-forklaring: Dette ville medført P=NP (husk P er i NP)

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

sant
usant
uvisst

Din kommentar:
LF-forklaring: Dette gjelder kun for problemer i NPC.

Oppgave 4

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

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

Hvis du kan transformere alle instanser $x$ av $X$ til tilsvarende instanser $y$ av $Y$ i polynomisk tid, og vet at løsningen på $y$ alltid kan transformeres til løsningen på $x$, kan du si at $X$ tilhører klassen P.
Hvis du kan transformere noen instanser $x$ av $X$ til tilsvarende instanser $y$ av $Y$ i polynomisk tid, og vet at løsningen på $y$ alltid kan tranformeres til løsningen på $x$, kan du si at $X$ tilhører klassen P.
Hvis du ikke kan transformere noen instanser av $X$ til instanser av $Y$ i polynomisk tid, kan du si at $X$ tilhører klassen NPC.

Din kommentar:
LF-forklaring:

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

Hvis du kan transformere alle instanser $x$ av $X$ til tilsvarende instanser $z$ av $Z$ i polynomisk tid, og vet at løsningen på $z$ alltid kan transformeres til løsningen på $x$, kan du si at $X$ tilhører klassen NPC.
Hvis du kan transformere alle instanser $z$ av $Z$ til tilsvarende instanser $x$ av $X$ i polynomisk tid, og vet at løsningen på $x$ alltid kan transformeres til løsningen på $z$, kan du si at $X$ tilhører klassen NPC.
Hvis du ikke kan transformere noen instanser av $Z$ til instanser av $X$, kan du si at $X$ tilhører klassen P.

Din kommentar:
LF-forklaring:

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.

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

Reduser $A$ til $B$
Reduser $A$ til $C$
Reduser $B$ til $A$
Reduser $B$ til $C$
Reduser $C$ til $A$
Reduser $C$ til $B$
Umulig å avgjøre

Din kommentar:
LF-forklaring:

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

Reduser $A$ til $B$
Reduser $A$ til $C$
Reduser $B$ til $A$
Reduser $B$ til $C$
Reduser $C$ til $A$
Reduser $C$ til $B$
Umulig å avgjøre

Din kommentar:
LF-forklaring:

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

Reduser $A$ til $B$
Reduser $A$ til $C$
Reduser $B$ til $A$
Reduser $B$ til $C$
Reduser $C$ til $A$
Reduser $C$ til $B$
Umulig å avgjøre

Din kommentar:
LF-forklaring: