[理工] 演算法 reduction

[twiddlebug (Tina)]

https://i.imgur.com/7RTw7yO.jpg

想請問a小題。
之前在板上看到有人說可以這樣做reduction。
想請問如果他抓的那兩個點不是原圖HP的起點跟終點，這樣加了P 點不是也不會形成HC嗎
?

還是請問有甚麼其他的方法嗎？先謝謝各位了!

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 120.114.191.135 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1578473102.A.871.html
推 NCTUcs: 應該是將P點跟G上所有其他點相連吧
→ NCTUcs: https://en.wikipedia.org/wiki/Hamiltonian_path_problem
→ NCTUcs: 第二段Reduction between the path problem and the cycle
→ twiddlebug: 完全懂了！！ 謝謝N大！