如何判斷一個圖是否是漢密爾頓圖？哈密頓圖哈密頓圖和歐拉電路與哈密頓電路問題非常相似。1859年，威廉·漢密爾頓爵士在給朋友的一封信中，首先談到了一個關(guān)于十二面體的數(shù)學(xué)游戲：我們能在圖中找到一個回路，使

如何判斷一個圖是否是漢密爾頓圖？

哈密頓圖哈密頓圖和歐拉電路與哈密頓電路問題非常相似。

1859年，威廉·漢密爾頓爵士在給朋友的一封信中，首先談到了一個關(guān)于十二面體的數(shù)學(xué)游戲：我們能在圖中找到一個回路，使它包含圖的所有節(jié)點嗎？（見圖）他把每個節(jié)點看作一座城市，把連接兩個節(jié)點的邊緣看作一條交通線。所以他的問題是他能否找到一條旅行路線，沿著交通線只經(jīng)過每個城市一次，然后回到原來的出發(fā)地。他把這個問題稱為環(huán)游世界的問題。定義1給定一個圖G，如果有一條路恰好通過圖的每個節(jié)點一次，則該路稱為Hamilton路。如果有一個電路恰好通過圖中的每個節(jié)點一次，則稱為哈密頓電路。具有哈密頓回路的圖稱為哈密頓圖。定理1如果G=