如何判斷哈密頓圖_哈密頓圖的必要條件

一、哈密頓圖定義概念

哈密頓通路（回路）與哈密頓圖（Hamilton圖）通過圖G的每個結(jié)點(diǎn)一次，且僅一次的通路（回路），就是哈密頓通路（回路）。存在哈密頓回路的圖就是哈密頓圖。

1.哈密頓通路

設(shè)G=《V，E》為一圖（無向圖或有向圖）.G中經(jīng)過每個頂點(diǎn)一次且僅一次的通路稱作哈密頓通路

2.哈密頓回路

G中經(jīng)過每個頂點(diǎn)一次且僅一次的回路稱作哈密頓回路

3.哈密頓圖

若G中存在哈密頓回路，則稱它是哈密頓圖

4.定義詳解：

（1）存在哈密頓通路（回路）的圖一定是連通圖；

（2）哈密頓通路是初級通路，哈密頓回路是初級回路；

（3）若G中存在哈密頓回路，則它一定存在哈密頓通路，反之不真

（4）只有哈密頓通路，無哈密頓回路的圖不交哈密頓圖；

二、判斷條件

與歐拉圖的情形不同，到目前為止還未找到判斷一個圖是否是哈密頓圖的非平凡的充要條件。事實(shí)上這是圖論中尚未解決的主要問題之一。哈密頓圖有很多充分條件，例如，

（1）若圖的最小度不小于頂點(diǎn)數(shù)的一半，則圖是哈密頓圖；

（2）若圖中每一對不相鄰的頂點(diǎn)的度數(shù)之和不小于頂點(diǎn)數(shù)，則圖是哈密頓圖。

另外，還有很多用度序列、度和、圖的堅韌度等參數(shù)給出的充分條件。

三、哈密頓圖的充分條件和必要條件

定理1：設(shè)無向圖G是哈密頓圖，V1是V的任意的非空子集，則

p（G-V1）≤|V1|

其中，p（G-V1）為從G中刪除V1（刪除V1中各頂點(diǎn)及關(guān)聯(lián)的邊）后所得到的圖的連通分支，|V1|為V1集合中包含的頂點(diǎn)個數(shù)?！竟茴D圖存在的必要條件】

推論：有割點(diǎn)的圖一定不是哈密頓圖

設(shè)v是圖中的割點(diǎn)，則p（G-v）》=2，由上述定理知G不是哈密頓圖

（2）設(shè)G是n（n》=3）階無向簡單圖，若對于G中的每一對不相鄰的頂點(diǎn)u，v，均有

d（u）+d（v）》=n-1

則G中存在哈密頓通路。又若

d（u）+d（v）》=n

則G中存在哈密頓回路，即G為哈密頓圖。【哈密頓圖存在的充分條件】

其中d（u），d（v）分別代表頂點(diǎn)u，v的度數(shù)。

定理2：設(shè)G是n（n≥3）階無向簡單圖，如果G中任何一對不相鄰的頂點(diǎn)度數(shù)之和都大于等于n，則G是哈密頓圖。

推論：設(shè)G是n（n≥3）階無向簡單圖，如果G中任何一對不相鄰的頂點(diǎn)的度數(shù)之和都大于等于n，則G是哈密頓圖。

定理3：在n（n≥2）階有向圖D=中，如果所有有向邊均用無向邊代替，所得無向圖中含生成子圖Kn，則有向圖中存在哈密頓圖。

推論：n（n≥3）階有向完全圖為哈密頓圖。

哈密頓路徑也稱作哈密頓鏈，指在一個圖中沿邊訪問每個頂點(diǎn)恰好一次的路徑。尋找這樣的一個路徑是一個典型的NP-完全（NP-complete）問題。后來人們也證明了，找一條哈密頓路的近似比為常數(shù)的近似算法也是NP完全的。

四、如何判斷哈密頓圖

1.常用方法判斷是哈密頓圖：

（1）若能通過觀察找出圖G中的一條哈密頓回路，則G當(dāng)然是哈密頓圖。

（2）若一個無向圖G滿足上述（2）中的條件，一個有向圖D滿足上述（3）的推論的條件，則G、D都是哈密頓圖。

2.破壞哈密頓圖存在的必要條件，判定不是哈密頓圖：

設(shè)n階圖G是哈密頓圖，則G應(yīng)該滿足以下諸條件：

（1）G必須是連通圖；

（2）G中的邊數(shù)m必須大于等于頂點(diǎn)數(shù)n；

（3）若G中存在2度頂點(diǎn)v，即d（v）=2，則與v關(guān)聯(lián)的兩條邊ei，ej必須在G中的任何哈密頓回路上；

（4）若G中存在每條哈密頓回路中出現(xiàn)的邊，不能構(gòu)成邊數(shù)小于n的初級回路（圈）；

破壞以上諸條件中的一條，都不是哈密頓圖。