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ý.
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.