[理工] Reduction 107 清大計科 8

看板Grad-ProbAsk作者DLHZ (going faster)時間5年前 (2020/01/25 15:06)推噓3(3推 0噓 4→)

留言7則, 3人參與討論串1/1

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

9/10 00:18,

9/10 00:18

→

alt

9/10 00:24,

9/10 00:24

噓

9/10 00:25,

9/10 00:25

-- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 106.1.43.179 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1579935969.A.108.html