[理工] Reduction 107 清大 計科 8

[DLHZ (going faster)]

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

---------------------------------------------------

我想問這樣的過程是否正確？

還是有那些東西需要說明？

我比較不確定是1. 這樣的敘述是否可以

畢竟自己沒給教授改過這種東西

不太確定

想聽聽大家的意見

--
推 godtomanne:alt+f4沒有用?
→ alt:去你媽的           　　　　　
噓 F4:你才沒用　　　　　　
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 106.1.43.179 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1579935969.A.108.html
推 NCTUcs: HP轉HC的reduction好像不是這樣子吧
→ NCTUcs: 應該是加上一個點v 將G上所有點和v相連
→ NCTUcs: 這樣只要在G'上包含HC 則代表有一個cycle經過x->v->y
→ NCTUcs: 則表示G上有一條HP 且path的起終點分別是x和y
→ DLHZ: 喔喔我了解了 那像2. 這樣的寫法應該就沒問題了吧
推 NCTUcs: 可能要強調若G'中存在HP 則path的起終點必定分別為s和t
已補充。另外，對於x->v->y我做了點修改，感覺比較符合個別的意思。

推 MASAGA: 我個人覺得唯若且若也順便寫一下比較保險
單向應該就可以了吧?考量時間上的問題應該只會寫出必要的部分。
※ 編輯: DLHZ (106.1.43.179 臺灣), 01/25/2020 16:47:57