作者DLHZ (going faster)
看板Grad-ProbAsk
標題[理工] Reduction 107 清大 計科 8
時間Sat Jan 25 15:05:22 2020
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. 這樣的敘述是否可以
畢竟自己沒給教授改過這種東西
不太確定
想聽聽大家的意見
--
1F：推 godtomanne:alt+f4沒有用?9/10 00:18
2F：→ alt:去你媽的 9/10 00:24
3F：噓 F4:你才沒用 9/10 00:25
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 106.1.43.179 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1579935969.A.108.html
4F：推 NCTUcs: HP轉HC的reduction好像不是這樣子吧 01/25 15:15
5F：→ NCTUcs: 應該是加上一個點v 將G上所有點和v相連 01/25 15:16
6F：→ NCTUcs: 這樣只要在G'上包含HC 則代表有一個cycle經過x->v->y 01/25 15:17
7F：→ NCTUcs: 則表示G上有一條HP 且path的起終點分別是x和y 01/25 15:17
8F：→ DLHZ: 喔喔我了解了 那像2. 這樣的寫法應該就沒問題了吧 01/25 15:21
9F：推 NCTUcs: 可能要強調若G'中存在HP 則path的起終點必定分別為s和t 01/25 15:24
已補充。另外，對於x->v->y我做了點修改，感覺比較符合個別的意思。
10F：推 MASAGA: 我個人覺得唯若且若也順便寫一下比較保險 01/25 16:36
單向應該就可以了吧?考量時間上的問題應該只會寫出必要的部分。
※ 編輯: DLHZ (106.1.43.179 臺灣), 01/25/2020 16:47:57