又稱漢密頓圖，是指存在哈密頓環的無向圖，由哈密顿爵士提出。

定義
下列定義，既適用於無向圖，亦適用於有向圖。

;哈密頓路徑:圖的一條路，經過每個頂點恰好一次。
;哈密頓環:在一條哈密頓路的基礎上，再有一條邊將其首尾連接，所構成的圈。注意，若有一個哈密頓圈，則移除其任一條邊，皆可得到一條哈密頓路，但反之則不然，即給定一條哈密頓路，不一定能延伸成哈密頓圈，因為該路徑的首尾兩頂點之間，不一定有邊相連。
;哈密頓圖:有哈密頓圈的圖。
;半哈密頓圖:有哈密頓路，但無哈密頓圈的圖。
;哈密頓連通圖:一幅圖，以其任意兩個頂點為起終點，皆存在一條哈密頓路。
;哈密頓分解:將邊集分劃成若干個哈密頓圈。
;亞哈密頓圖:並非哈密頓圖，但只要移除任何一個頂點，就會變成哈密頓圖。

Non-hamiltonian.svg|非哈密頓圖
Semi-hamiltonian.svg|半哈密頓圖
Hamiltonian.svg|哈密頓圖

性質
哈密尔顿图的必要条件：
若G=(V,E) 是一个哈密尔顿图，则对于V的每一个非空子集S，均有W(G－S) ≤|S|。其中|S|是S中的顶点数，W(G－S)表示图G擦去属于S中的顶点后，剩下子图的连通分支的个数。

充分條件
對歐拉圖而言，有某個充要條件，可用作簡單判定一幅圖是否歐拉圖（歐拉定理）。然而，對於哈密頓圖，並無相應的結果。

不過，仍有一系列越來越鬆的判別條件，能夠斷定一幅圖必定為哈密頓圖。此類定理，最早見於1952年的研究，其想法直觀，即只要有「足夠多」邊，就能迫得圖有哈密頓圈。用頂點的度推出存在哈密頓圈的定理之中，目前最優的，是1976年邦迪與赫瓦塔爾的定理。

以上是有關無向圖的部分。對於有向圖，相應的定理舉例有Ghouila–Houiri。

狄拉克定理
於1952年證明以下定理：

n個頂點的簡單圖（n \ge 3）中，若每個頂點的度皆至少為\frac n2，則必為哈密頓圖。

歐爾定理
设 G=(V,E) 是一个无向简单图，|V|=n，n \geq 3。若对于任意两个不相鄰的顶点 u,v \in V，都有 u 和 v 的度，即 d(u) 与 d(v) 满足 d(u)+d(v)\geq n，那么，G 是哈密尔顿图。

此条件由挪威图论数学家奧斯丁·歐爾在1960年给出。

波紹定理
證明了幾條有關哈密頓圈的定理。以下具體引用一條1962年的定理，有關連邊少的頂點：

一幅n個頂點的完全圖（n \ge 3），若滿足：

對所有滿足1 \le k 的整數k，度不大於k的頂點個數，嚴格小於k；

度不大於\frac{n-1}2的頂點個數，小於或等於\frac{n-1}2；

則必為哈密頓圖。

注意n為偶時，條件2已包含於條件1，所以只在n為奇數時，條件2才需要分開列出。

作為例子，考慮附圖中，具有6個頂點的圖。其為哈密頓圖：已經將頂點排列好，使哈密頓圈H（以紅色標示）正好是外圈。

• 狄拉克定理不足以證明該圖為哈密頓圖。若要應用狄拉克定理，則所有頂點的度皆要至少為3，然而圖中有頂點的度僅為2。
• 奧爾定理同樣不敷使用，因為圖中標出的兩個不相鄰頂點a, b的度，和僅為d(a) + d(b) = 3 + 2 = 5，但奧爾定理的條件中，至少要有6。
• 另一方面，波紹定理能夠斷定該圖必為哈密頓圖，因為只有0個度為1的頂點，以及1個度為2的頂點，故已滿足條件1（因為0 且0 + 1 ）。

例子
]]
*超過2個頂點的完全圖是哈密顿图。n階無向完全圖K_n上，不同的（無向）哈密頓圈有\frac{(n - 1)!}2個。而若考慮方向，則有(n - 1)!個有向哈密頓圈。
*n個頂點的圖當中，最少邊數的哈密頓圖是循環圖C_n。任何循環圖皆為哈密顿图。

• 有奇數條（有向）哈密頓路徑。任意（多於兩個頂點的）循環賽圖為哈密頓圖當且僅當其為強連通。

*任何以柏拉圖立體（凸正多面體）的邊與頂點構成的圖（「」）皆為哈密顿图。
*同樣，棱柱與反棱柱的1-骨架也是哈密頓圖。
*13種阿基米德立體的1-骨架皆為哈密頓圖，但13種卡塔蘭立體當中，僅有7個的1-骨架是哈密頓圖。.

• 赫歇爾圖（附圖）是眾多不具哈密頓圈的凸多面體1-骨架當中，最小的一個。
• 哈密頓圖的線圖仍是哈密頓圖。
• 歐拉圖的線圖也是哈密頓圖。

哈密顿路径问题
寻找哈密顿路径是一个典型的NP-完全问题。后来人们也证明了，找一条哈密顿路的近似比为常数的近似算法也是NP-完全的。

寻找哈密顿路的确定算法虽然很难有多项式时间的，但是这并不意味着只能进行时间复杂度为O(n \times n!)暴力搜索。利用状态压缩动态规划，可以将时间复杂度降低到O(2^n \cdot n^3)，具体算法是建立方程f[i][S][j]，表示经过了i个节点，节点都是集合S的，到达节点j时的最短路径。每次都按照点j所连的节点进行转移。

參見
*哈密頓路徑
*哈密顿路径问题

參考文獻