IB107 úkol 3, příklad 2 Odevzdání: 8. 12. 2023, 23:59
Jméno: Nadšený Poník UČO: 1234567
list učo body
Oblast strojově snímaných informací. Své učo a číslo listu vyplňte
zleva dle vzoru číslic. Jinak do této oblasti nezasahujte.
2. [3 body] Uvažujme konečné orientované grafy, jejichž hrany jsou ohodnocené nezápornými
celými čísly. Problém jednoduché cesty dané délky je problém rozhodnout, zda v takovém grafu
existuje jednoduchá cesta (tj. cesta, která každý vrchol navštíví nejvýše jednou) z daného vrcholu s
do daného vrcholu t, jejíž délka (myšleno součet ohodnocení hran na cestě) je právě daná hodnota k.
Tento problém ztotožníme s množinou
JCDD = { G, s, t, k | G je graf, ve kterém existuje jednoduchá cesta z s do t délky k}.
Dokažte, že JCDD je NP-úplný.
Příslušnost do NP. Problém JCDD je rozhodován nedeterministickým Turingovým strojem, který
pracuje následovně. Stroj nejprve deterministicky ověří, zda vstup je kódem nějaké čtveřice G, s, t, k,
kde G je orientovaný graf, s, t jsou jeho vrcholy, a k je nezáporné číslo menší nebo rovno součtu
ohodnocení všech hran v G. Pokud tomu tak není, ihned zamítne. V opačném případě nedeterministicky
vybere sekvenci nejvýše n − 1 hran, kde n je počet vrcholů G, a ověří, že tyto vrcholy tvoří
jednoduchou cestu z s do t délky k. Pokud ano, stroj akceptuje, jinak zamítá. Všechny uvedené kroky
lze na Turingově stroji implementovat v polynomiálním čase, tedy uvedený stroj má polynomiální
časovou složitost. Je zjevné, že tento Turingův stroj akceptuje právě JCDD.
NP-těžkost. Ukážeme, že SUBSET-SUM ≤p JCDD, kde SUBSET-SUM je NP-úplný problém rozhodnout,
zda pro danou konečnou multimnožinu S obsahující přirozená čísla existuje multimnožina
Y ⊆ S, jejíž součet je dané přirozené číslo o.
SUBSET-SUM = { S, o | S = {x1, . . . , xm} a pro nějaké {y1, . . . , yn} ⊆ S platí Σn
i=1yi = o}.
Uvažme funkci f definovanou vztahem
f(x) =



s t
2
, s, t, 1 pokud x není očekávaného tvaru S, o ,
G, v0, vm, o pokud x = S, o a S = {x1, . . . , xm},
kde G je následující graf:
v0
u1
v1
u2
v2
u3
. . . vm
um
x1
0 0
x2
0 0
x3
0 0
xm
0 0
Funkce f je zjevně totálně vyčíslitelná deterministickým strojem s polynomiální časovou složitostí.
Zbývá ukázat, že x ∈ SUBSET-SUM ⇐⇒ f(x) ∈ JCDD.
“=⇒” Pokud x ∈ SUBSET-SUM, pak x = S, o , kde S = {x1, . . . , xm} a existuje Y = {y1, . . . , yn} ⊆
S splňující Σn
i=1yi = o. V generovaném grafu G uvažme cestu z v0 do vm takovou, že pro každé
1 ≤ i ≤ m využijeme hranu vi−1
xi
−→ vi pokud xi ∈ Y a hrany vi−1
0
−→ ui
0
−→ vi jinak. Tím
dostáváme jednoduchou cestu z v0 do vm délky o. Tedy f(x) = G, v0, vm, o ∈ JCDD.
“⇐=” Nechť f(x) ∈ JCDD. Z definice f je jasné, že x = S, o a f(x) = G, v0, vm, o . Uvažme
jednoduchou cestu v grafu G z v0 do vm délky o. Multimnožinu Y zkonstruujeme tak, aby
obsahovala právě všechna xi > 0 taková, že hrana vi−1
xi
−→ vi leží na této cestě. Z konstrukce
plyne, že Y ⊆ S a součet všech prvků v Y je právě o. Tedy x = S, o ∈ SUBSET-SUM.
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.