推 arcred :了解了, 感謝! 03/15 06:13
→ hcsoso :] 03/15 12:33
※ 引述《arcred (堅持阿伏哥聯盟)》之銘言：
: 這個是複雜度的問題
: 應該算跟離散數學有關吧 @@
: 我的問題是:
: 從 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
: 我想很久想不出來..請幫忙解惑一下 謝謝!
考慮這樣的圖：
‧→‧
↑ ↓
s‧→‧←‧
↓
‧t
這應該是沒有從 s to t 的 dHam 的，
但是你如果拿掉 mid，會發現有 uHam...
試著觀察 mid 在證明中的重要性！
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.28.224