這個是複雜度的問題
應該算跟離散數學有關吧 @@
我的問題是:
從 Directed Hamiltonian Path (dHAMPATH)
reduce到 Undirected Hamiltonian Path (uHAMPATH)
網路上找到證明方法都是把有向圖的點分成三個 v_in,v_mid,v_out
因為要讓無向圖的函數可以處理有向圖
所以把有向圖轉換成無向圖時記錄了方向這我可以理解
不過有 in 跟 out 應該就夠了呀
那 mid 存在的用意是做什麼用呢??
這裡有證明解答的連結
http://www.cs.tau.ac.il/~rosenric/TA/ex08b/HAMPATH.pdf
我想很久想不出來..請幫忙解惑一下 謝謝!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 208.29.54.91