[理工] 算法 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