作者ccczz (什麼鬼)
看板Grad-ProbAsk
標題[問題] Euler 迴路 and Hamiltomian 迴路
時間Sat Apr 11 18:54:50 2009
Euler 迴路 簡單來說是
一個連通圖
從任一點 開始 經過每個點最多一次 最後回到起始點?
Hamiltonian 迴路是
經過每個點每個邊一次最多一次 最後回到起始點?
差別在於 Euler 每個點 可以走多次 只要路徑不同就可以?
而 Hamiltonian 不行?
話說考交大資管前 看了Hamiltonian algo 沒讀懂他
隔天就出了 最後結果差1分第一階段
不想悲劇再來一次了..煩請解答了
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.47.112.45
1F：推 ymsmart:E.C. 是要每個邊接走過一次 且起終點相同 04/11 23:49
2F：→ ymsmart:H.C.是每個點分別各經過一次 起終點相同 04/11 23:49
3F：→ ccczz:E.C.走不重複邊的情況下 經過重複的點也OK嗎? 04/12 00:48
4F：→ ccczz:2-----3 04/12 00:51
5F：→ ccczz: \ / 04/12 00:51
6F：→ ccczz: (1,4) 04/12 00:51
7F：→ ccczz: / \ 04/12 00:51
8F：→ ccczz:5-----6 數字是經過順序 04/12 00:52
9F：→ ccczz:漏打一個 最後回到1 04/12 00:52
10F：→ morning12345:可以，重點只在邊 04/12 15:00
11F：→ ccczz:謝謝 我懂意思了 04/12 15:10