十二面体中的哈密顿回路 哈密顿图 （台湾作漢米頓圖 ）又稱漢密頓圖 ，是指存在哈密頓環 的無向圖 ，由哈密顿 爵士提出。
下列定義，既適用於無向圖，亦適用於有向圖。
哈密頓路徑 圖的一條路 ，經過每個頂點恰好一次。
哈密頓環 在一條哈密頓路的基礎上，再有一條邊將其首尾連接，所構成的圈 。注意，若有一個哈密頓圈，則移除其任一條邊，皆可得到一條哈密頓路，但反之則不然，即給定一條哈密頓路，不一定能延伸成哈密頓圈，因為該路徑的首尾兩頂點之間，不一定有邊相連。
哈密頓圖
有哈密頓圈的圖。
半哈密頓圖
有哈密頓路，但無哈密頓圈的圖。
哈密頓連通圖
一幅圖，以其任意兩個頂點為起終點，皆存在一條哈密頓路。
哈密頓分解
將邊集分劃 成若干個哈密頓圈。
亞哈密頓圖
亞哈密頓圖
哈密尔顿图的必要条件：
若G=(V,E) 是一个哈密尔顿图，则对于V的每一个非空子集S，均有W(G－S) ≤|S|。其中|S|是S中的顶点 数，W(G－S)表示图G擦去属于S中的顶点后，剩下子图的连通分支的个数。
對歐拉圖 而言，有某個充要條件，可用作簡單判定一幅圖是否歐拉圖（歐拉定理 ）。然而，對於哈密頓圖，並無相應的結果。
不過，仍有一系列越來越鬆的判別條件，能夠斷定一幅圖必定為哈密頓圖。[ 1] 蓋布瑞·狄拉克 度 推出存在哈密頓圈的定理之中，目前最優的，是1976年邦迪與赫瓦塔爾的定理。
以上是有關無向圖的部分。對於有向圖，相應的定理舉例有Ghouila–Houiri。
蓋布瑞·狄拉克 [ 2] [ 3]
n
{\displaystyle n}
簡單圖 （
n
≥
3
{\displaystyle n\geq 3}
n
2
{\displaystyle {\frac {n}{2}}}
设
G
=
(
V
,
E
)
{\displaystyle G=(V,E)}
|
V
|
=
n
{\displaystyle |V|=n}
n
≥
3
{\displaystyle n\geq 3}
顶点
u
,
v
∈
V
{\displaystyle u,v\in V}
u
{\displaystyle u}
v
{\displaystyle v}
度 ，即
d
(
u
)
{\displaystyle d(u)}
d
(
v
)
{\displaystyle d(v)}
d
(
u
)
+
d
(
v
)
≥
n
{\displaystyle d(u)+d(v)\geq n}
G
{\displaystyle G}
此条件由挪威图论 数学家 奧斯丁·歐爾 在1960年给出。
波紹·拉約什 [ 4] [ 5]
一幅
n
{\displaystyle n}
n
≥
3
{\displaystyle n\geq 3}
對所有滿足
1
≤
k
<
n
−
1
2
{\displaystyle 1\leq k<{\frac {n-1}{2}}}
k
{\displaystyle k}
k
{\displaystyle k}
k
{\displaystyle k}
度不大於
n
−
1
2
{\displaystyle {\frac {n-1}{2}}}
n
−
1
2
{\displaystyle {\frac {n-1}{2}}}
則必為哈密頓圖。
注意
n
{\displaystyle n}
n
{\displaystyle n}
應用波紹定理的例子 作為例子，考慮附圖中，具有
6
{\displaystyle 6}
H
{\displaystyle H}
狄拉克定理不足以證明該圖為哈密頓圖。若要應用狄拉克定理，則所有頂點的度皆要至少為
3
{\displaystyle 3}
2
{\displaystyle 2}
奧爾定理同樣不敷使用，因為圖中標出的兩個不相鄰頂點
a
,
b
{\displaystyle a,b}
d
(
a
)
+
d
(
b
)
=
3
+
2
=
5
{\displaystyle d(a)+d(b)=3+2=5}
6
{\displaystyle 6}
另一方面，波紹定理能夠斷定該圖必為哈密頓圖，因為只有
0
{\displaystyle 0}
1
{\displaystyle 1}
1
{\displaystyle 1}
2
{\displaystyle 2}
0
<
1
{\displaystyle 0<1}
0
+
1
<
2
{\displaystyle 0+1<2}
赫歇爾圖 超過2個頂點的完全圖 是哈密顿图。
n
{\displaystyle n}
K
n
{\displaystyle K_{n}}
(
n
−
1
)
!
2
{\displaystyle {\frac {(n-1)!}{2}}}
(
n
−
1
)
!
{\displaystyle (n-1)!}
n
{\displaystyle n}
循環圖
C
n
{\displaystyle C_{n}}
循環圖 皆為哈密顿图。循環賽圖 強連通 。[ 6] 任何以柏拉圖立體 （凸正多面體）的邊與頂點構成的圖（「1-骨架 [ 7] [ 8]
同樣，棱柱 與反棱柱 的1-骨架也是哈密頓圖。
13種阿基米德立體 的1-骨架皆為哈密頓圖，但13種卡塔蘭立體 當中，僅有7個的1-骨架是哈密頓圖。[ 9] [ 10]
赫歇爾圖 [ 11] 哈密頓圖的線圖 仍是哈密頓圖。[ 12] :408
歐拉圖 的線圖也是哈密頓圖。
寻找哈密顿路径是一个典型的NP-完全 问题。后来人们也证明了，找一条哈密顿路的近似比为常数的近似算法也是NP-完全的。
寻找哈密顿路的确定算法虽然很难有多项式时间的，但是这并不意味着只能进行时间复杂度 为
O
(
n
×
n
!
)
{\displaystyle O(n\times n!)}
状态压缩 动态规划 [來源請求]
O
(
2
n
⋅
n
3
)
{\displaystyle O(2^{n}\cdot n^{3})}
^ Melissa DeLeon. Department of Mathematics and Computer Science, Seton Hall University , 编. A Study of Sufficient Conditions for Hamiltonian Cycles (PDF) . [2021-09-19 ] . （原始内容存档 (PDF) 于2012-12-22） （英语） . ^ Dirac, Gabriel Andrew. Some theorems on abstract graphs. Proc. London Math. Soc. 3. 1952, 2 : 6––81. MR 0047308 doi:10.1112/plms/s3-2.1.69 （英语） . ^ Ronald Graham . Handbook of Combinatorics . MIT Press. 1995. ISBN 978-0-262-57170-8（英语） . ^ Pósa, Lajos. A theorem concerning hamilton lines. Magyar Tud. Akad. Mat. Kutató ́Int. Közl. 1962, 7 : 225–226 （英语） . ^ Nash-Williams, Crispin. On Hamiltonian circuits in finite graphs (PDF) . Proc. Amer. Math. Soc. 1966, 17 : 466–467 [2021-09-19 ] . （原始内容存档 (PDF) 于2022-02-17） （英语） . ^ Graham 1995 ，第29 & 31頁 harvnb模板錯誤: 無指向目標: CITEREFGraham1995 (幫助 ) .^ Gardner, M. "Mathematical Games: About the Remarkable Similarity between the Icosian Game and the Towers of Hanoi." Sci. Amer. 196, 150–156, May 1957 . [2021-09-03 ] . （原始内容存档 于2016-10-22）. ^ Weisstein, Eric W. (编). Wolfram MathWorld (首頁) . at MathWorld Wolfram Research, Inc. （英语） . ^ Weisstein, Eric W. (编). Wolfram MathWorld (首頁) . at MathWorld Wolfram Research, Inc. （英语） . ^ Weisstein, Eric W. (编). Wolfram MathWorld (首頁) . at MathWorld Wolfram Research, Inc. （英语） . ^ Weisstein, Eric W. (编). Wolfram MathWorld (首頁) . at MathWorld Wolfram Research, Inc. （英语） . ^ Xiong, Liming; Liu, Zhanhong. Hamiltonian iterated line graphs [哈密頓的疊代線圖]. Discrete Mathematics. 2002, 256 : 407–422. doi:10.1016/S0012-365X(01)00442-3 （英语） .
