哈密爾頓圖

哈密爾頓圖，是美國圖論數學家奧勒出了一個圖是哈密爾頓圖的充分條件。

詞語解釋

哈密爾頓圖

含有圖中所有頂點的軌稱作哈密爾頓軌，閉合的哈密爾頓軌稱作哈密爾頓環，含有哈密爾頓環的圖稱作哈密爾頓圖。

相關說明

哈密爾頓圖

著名的美國圖論數學家奧勒在1960年給出了一個圖是哈密爾頓圖的充分條件：對於頂點個數大於2的圖，如果圖中任意兩點度的和大於頂點總數，那這個圖一定是哈密爾頓圖。
哈密爾頓軌也稱作哈密爾頓鏈，指在一個圖中沿邊訪問每個頂點恰好一次的路徑。尋找這樣的一個路徑是一個典型的NP-完備(NP-complete)問題。