哈密頓通路（回路）與哈密頓圖（Hamilton圖）通過圖G的每個結(jié)點一次，且僅一次的通路（回路），就是哈密頓通路（回路）。下面總結(jié)四個定義，幫助大家理解。

一、哈密頓圖定義

通過圖中所有頂點一次且僅一次的通路稱為哈密頓通路。

通過圖中所有頂點一次且僅一次的回路稱為哈密頓回路。

具有哈密頓回路的圖稱為哈密頓圖。

具有哈密頓通路而不具有哈密頓回路的圖稱為半哈密頓圖。

（1）哈密頓通路

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

（2）哈密頓回路

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

（3）哈密頓圖

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

（4）定義詳解：

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

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

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

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

二、性質(zhì)

設(shè)G=<V ,E>是哈密頓圖，則對于V的任意非空真子集V1，均有p(G -V1)≤|V1|。其中p(x)為 x 的連通分支數(shù)。

推論：設(shè)G=<V ,E>是半哈密頓圖，則對于V的任意非空真子集V1，均有p(G -V1)≤|V1|+1 。其中p(x)為 x 的連通分支數(shù)。

完全圖K2k+1(k≥1)中含 k 條邊不重的哈密頓回路，且這 k 條邊不重的哈密頓回路含K2k+1中的所有邊。

完全圖K2k(k≥2)中含k-1條邊不重的哈密頓回路，從K2k中刪除這k-1條邊不重的哈密頓回路后所得圖含 k 條互不相鄰的邊。

三、充分條件

設(shè)G是n(n≥2)的無向簡單圖，若對于G中任意不相鄰的頂點，均有，則G中存在哈密頓通路。

推論 1：設(shè)G是n(n≥3)的無向簡單圖，若對于G中任意不相鄰的頂點，均有，則G中存在哈密頓回路，從而G為哈密頓圖。

推論 2：設(shè)G是n(n≥3)的無向簡單圖，若對于G中任意頂點，均有，則G中存在哈密頓回路，從而G為哈密頓圖。

設(shè)D為n(n≥2)階競賽圖，則D具有哈密頓通路。

若D含n(n≥2)階競賽圖作為子圖，則D具有哈密頓通路。

強連通的競賽圖為哈密頓圖。

若D含n(n≥2)階強連通的競賽圖作為子圖，則D具有哈密頓回路。