IB102 – úkol 11, příklad 1 Odevzdání: 15. 12. 2014
Vypracoval(a): UČO:
Skupina:
1. [2 body] Dokažte, že problém rozhodnout, zda v daném orientovaném grafu existují
alespoň 2 různé hamiltonovské cesty z vrcholu s do vrcholu t (lišící se alespoň jednou
hranou), je NP-těžký. Jinak řečeno, dokažte, že jazyk 2-HAMPATH definovaný níže zadává
NP-těžký problém.
2-HAMPATH = { G, s, t | G je orientovaný graf obsahující alespoň 2 různé
hamiltonovské cesty z s do t}
V důkazu můžete využít faktu, že problém hamiltonovské cesty (definovaný níže) je
NP-úplný:
HAMPATH = { G, s, t | G je orientovaný graf obsahující hamiltonovskou cestu z s do t}.
Bonus [1 bod] Dokažte, že problém 2-HAMPATH je dokonce NP-úplný. Tedy dokažte
navíc, že 2-HAMPATH ∈ NP.
Bonus [1 bod] Dokažte, že jazyk k-HAMPATH definovaný níže je NP-úplný pro libovolné
k ≥ 1:
k-HAMPATH = { G, s, t | G je orientovaný graf obsahující alespoň k různých
hamiltonovských cest z s do t}