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

如何判斷一個(gè)圖是否是漢密爾頓圖？

哈密頓圖哈密頓圖和歐拉電路與哈密頓電路問(wèn)題非常相似。

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