宅學習 - Social Learning Space 社交學習空間@FJU CSIE

"

通過每一頂點且只通過一次的路徑稱為漢米爾頓路徑;若是要求必須再回到起始頂點的迴路，則稱為漢米爾頓迴路。

由於漢米爾頓路徑及漢米爾頓迴路，到目前還沒有找到一個簡單又可快速判斷的充要條件，因此，我們只能利用這類路徑或迴路的基本特性來做判斷。首先，我們可以從下列之必要條件來判斷一個圖是否有漢米爾頓迴路：

漢米爾頓迴路通過圖中除起點外之任一頂點最多一次。
若一圖有漢米爾頓迴路，則該必具連通性。因為在非連通性的圖中，不可能有通過每一頂點之迴路。
若一圖有漢米爾頓迴路，則圖中任一頂點之進出次數至少是2。因為若有一頂點，其進出次數少於2(即進出次數為0或1)，即至多有一個邊連接該頂點，則要通過該頂點的任一迴路務必沿著同一邊回去才能通過其他頂點，如此一來必有一頂點重複通過，此乃不可能也。
若一圖存在漢米爾頓迴路，則任一條漢米爾頓迴路必經由那些次數為2的頂點之兩個邊。
若一頂點，其次數大於2，在建造一條漢米爾頓迴路時，一旦路過該頂點，則其他與該頂點相連接而尚未使用過的邊都不能再考慮使用。
在一個具有n個頂點的圖G=(V,E)中，任一漢米爾頓路徑必恰好經過n-1個邊;而任一漢米爾頓迴路必恰好經過n個邊。
若一圖有漢米爾頓迴路存在，則只要去掉該迴路上的任一個邊，及可得到此圖的漢米爾頓路徑。

參考資料：http://www.cis.nctu.edu.tw/~is83039/discret/discrete6.html

[@more@]"