Q: 如何對input為一無向圖G =(E, V)的Hamiltonian path problem
跟Hamiltonian cycle problem互相reduction？
1. 對HP轉成HC
如果將一個無向圖輸入解HP problem的演算法是yes
那任意拿掉一個邊後輸出依然是yes則存在HC
更正: 令G' = (E', V') 其中
V'=V∪{v}
E'=E∪{(v, u)|u∈V}
若G'存在HC則有一cycle路徑為v->x->...->y->v
xy之間依然符合HP的性質且經過所有G中的點
代表G中存在一HP x為起點y為終點
2. 對HC轉成HP
對要解HP的圖G任意挑選圖中某一點v
令G' = (E', V') 其中
V'=V∪{v', s, t}
E'=E∪{(v', u)|(v, u)∈E}∪{(s, v), (v, v'), (v', t)}
如果G'存在HP
由於s跟t的degree皆為1
則s跟t必定為起點或終點
考慮從s出發的情況
那t只能由v'前往
所以在走到v'前必須先經過其他所有點
而在經過v'跟t以外的所有點之後能到達v'
代表這個路徑也能走回v
所以G'存在HP代表原圖G存在HC