[理工] 演算法 reduction twiddlebug PTT批踢踢實業坊

[理工] 演算法 reduction

作者: twiddlebug (Tina) 2020-01-08 16:45:00

https://i.imgur.com/7RTw7yO.jpg
想請問a小題。
之前在板上看到有人說可以這樣做reduction。
想請問如果他抓的那兩個點不是原圖HP的起點跟終點，這樣加了P 點不是也不會形成HC嗎
?
還是請問有甚麼其他的方法嗎？先謝謝各位了!

作者: NCTUcs 2020-01-08 17:57:00

應該是將P點跟G上所有其他點相連吧https://en.wikipedia.org/wiki/Hamiltonian_path_problem第二段Reduction between the path problem and the cycle

作者: twiddlebug (Tina) 2020-01-08 19:09:00

完全懂了！！謝謝N大！

繼續閱讀

[理工] 101台大電機丙CLA 分散系統dsa66253 [理工] 106清大計科 7 8bochengchen [理工] 中央線代矩陣分解WendyD [理工] 104中央資結第4題！Aa841018 [理工] 102清大計系第八題leegaga61029 [商管] 108 中正資結JK520nsk [理工] 離散一階邏輯dsa66253 [理工] 離散圖論同胚yahooyamgoog 105台科離散zxc2179vbnm [理工] 104交大計組 sign extension WendyD

Contact Us: admin [ a t ] ucptt.com