Opgaven W11

Opgaven W11
1. Beschouw de volgende instantie van SAT:
X = {x1 , x2 , x3 , x4 } en C = (x1 ∨ x
¯3 ) ∧ (¯
x1 ∨ x4 ) ∧ (x2 ∨ x3 ∨ x
¯4 ) ∧ (¯
x1 ∨ x2 ∨ x
¯ 3 ∨ x4 )
a) Is er een waarde-toekenning aan de variabelen waarvoor C waar is?
b) Construeer een zin C 0 met precies drie literals per clause die waar is d.e.s.d. als
C waar is.
c) Laat zien dat 3-SAT, de versie van SAT met precies drie literals in elke clause,
NP-volledig is.
2. Het probleem VERTEX COVER is als volgt gedefini¨eerd:
Gegeven: Ongerichte graaf G=(V,E) en een integer k.
Probleem: Heeft G een vertex cover ter grootte k? (Een vertex cover is een verzameling knopen, zdd voor elke tak geldt dat deze grenst aan tenminste ´e´en van de
knopen in de verzameling.
Het probleem INDEPENDENT SET is als volgt gedefini¨eerd:
Gegeven: Ongerichte graaf G=(V,E) en een integer k.
Probleem: Heeft G een independent set ter grootte k? (Een independent set is een
verzameling knopen, zdd er geen tak bestaat tussen twee knopen uit de verzameling.
a) Toon aan dat voor een ongerichte graaf G = (V, E) de volgende beweringen
equivalent zijn:
(1) W ⊆ V is een vertex cover;
(2) V − W is een independent set;
¯ (G
¯ = (V¯ , E)
¯ met V¯ = V
(3) V − W is een clique in de complementaire graaf G
¯
en {v, w} ∈ E d.e.s.d. als {v, w} ∈
/ E).
b) Toon aan dat INDEPENDENT SET en VERTEX COVER NP-volledig zijn.
3. Het probleem HAMILTONIAN CYCLE is als volgt gedefini¨eerd:
Gegeven: Gerichte graaf G=(V,A) en een integer k.
Probleem: Heeft G een cycle die elke knoop precies ´e´en keer aandoet?
Toon aan dat HAMILTONIAN CYCLE polynomiaal reduceerbaar is tot TSP
4. Het probleem PARTITIE is als volgt gedefini¨eerd:
Gegeven: Positieve integers a1 , a2 , . . . , an
P
P
Probleem: Is er een deelverzameling S ⊂ {1, . . . , n} zodanig dat j∈S aj = j6∈S aj ?
Het probleem 0-1 KNAPSACK is als volgt gedefini¨eerd:
Gegeven: Positieve integers c1 , c2 , . . . , cm en een positief geheel getal k
P
Is er een vector x ∈ {0, 1}m zodanig dat m
j=1 cj xj = k?
Het probleem PARTITIE is NP-volledig. Laat zien dat 0-1 KNAPSACK NP-volledig
is.
1

Download Report