漢密爾頓圈

漢密爾頓圈：圖G中包含一條經過每個頂點恰好一次的閉途徑，如果G的階數n不小於3，則這樣的一個途徑稱一個漢密爾頓圈。

基本介紹

• 中文名：漢密爾頓圈
• 定義：圖G中包含一條經過每個頂點恰好一次的閉途徑，如果G的階數n不小於3，則這樣的一個途徑稱一個漢密爾頓圈

如果圖G中包含一個漢密爾頓圈，則稱G是漢密爾頓的

完全圖一定有漢密爾頓圈，有橋的圖一定無漢密爾頓圈。

Ore性質：圖H中任意兩個不相鄰的頂點x,y,都有deg(x)+deg(y)＞=n,則H具有Ore性質。deg表示該點的度。

具有Ore性質的圖是連通的。

若簡單圖G滿足Ore性質，且階數n＞=3,則這個圖有漢密爾頓圈。