哈密顿图

下列定义，既适用于无向图，亦适用于有向图。

哈密顿路径

图的一条路，经过每个顶点恰好一次。

哈密顿环

在一条哈密顿路的基础上，再有一条边将其首尾连接，所构成的圈。注意，若有一个哈密顿圈，则移除其任一条边，皆可得到一条哈密顿路，但反之则不然，即给定一条哈密顿路，不一定能延伸成哈密顿圈，因为该路径的首尾两顶点之间，不一定有边相连。

哈密顿图

有哈密顿圈的图。

半哈密顿图

有哈密顿路，但无哈密顿圈的图。

哈密顿连通图

一幅图，以其任意两个顶点为起终点，皆存在一条哈密顿路。

哈密顿分解

将边集分划成若干个哈密顿圈。

亚哈密顿图

亚哈密顿图（英语：Hypohamiltonian graph）并非哈密顿图，但只要移除任何一个顶点，就会变成哈密顿图。

•  

  非哈密顿图

•  

  半哈密顿图

•  

  哈密顿图

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

对欧拉图而言，有某个充要条件，可用作简单判定一幅图是否欧拉图（欧拉定理）。然而，对于哈密顿图，并无相应的结果。

不过，仍有一系列越来越松的判别条件，能够断定一幅图必定为哈密顿图。^[1]此类定理，最早见于盖布瑞·狄拉克（英语：Gabriel Andrew Dirac）1952年的研究，其想法直观，即只要有“足够多”边，就能迫得图有哈密顿圈。用顶点的度推出存在哈密顿圈的定理之中，目前最优的，是1976年邦迪与赫瓦塔尔的定理。

以上是有关无向图的部分。对于有向图，相应的定理举例有Ghouila–Houiri。

狄拉克定理

盖布瑞·狄拉克（英语：Gabriel Andrew Dirac）于1952年^[2]证明以下定理：^[3]

${\displaystyle n}$ 个顶点的简单图（${\displaystyle n\geq 3}$ ）中，若每个顶点的度皆至少为${\displaystyle {\frac {n}{2}}}$ ，则必为哈密顿图。

欧尔定理

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

此条件由挪威图论数学家奥斯丁·欧尔在1960年给出。

波绍定理

波绍·拉约什（英语：Lajos Pósa (mathematician)）证明了几条有关哈密顿圈的定理。以下具体引用一条1962年的定理^[4][5]，有关连边少的顶点：

一幅${\displaystyle n}$ 个顶点的完全图（${\displaystyle n\geq 3}$ ），若满足：

1. 对所有满足${\displaystyle 1\leq k<{\frac {n-1}{2}}}$ 的整数${\displaystyle k}$ ，度不大于${\displaystyle k}$ 的顶点个数，严格小于${\displaystyle k}$ ；
2. 度不大于${\displaystyle {\frac {n-1}{2}}}$ 的顶点个数，小于或等于${\displaystyle {\frac {n-1}{2}}}$ ；

则必为哈密顿图。

注意${\displaystyle n}$ 为偶时，条件2已包含于条件1，所以只在${\displaystyle n}$ 为奇数时，条件2才需要分开列出。

作为例子，考虑附图中，具有${\displaystyle 6}$ 个顶点的图。其为哈密顿图：已经将顶点排列好，使哈密顿圈${\displaystyle H}$ （以红色标示）正好是外圈。

• 狄拉克定理不足以证明该图为哈密顿图。若要应用狄拉克定理，则所有顶点的度皆要至少为${\displaystyle 3}$ ，然而图中有顶点的度仅为${\displaystyle 2}$ 。
• 奥尔定理同样不敷使用，因为图中标出的两个不相邻顶点${\displaystyle a,b}$ 的度，和仅为${\displaystyle d(a)+d(b)=3+2=5}$ ，但奥尔定理的条件中，至少要有${\displaystyle 6}$ 。
• 另一方面，波绍定理能够断定该图必为哈密顿图，因为只有${\displaystyle 0}$ 个度为${\displaystyle 1}$ 的顶点，以及${\displaystyle 1}$ 个度为${\displaystyle 2}$ 的顶点，故已满足条件1（因为${\displaystyle 0<1}$ 且${\displaystyle 0+1<2}$ ）。

• 超过2个顶点的完全图是哈密顿图。${\displaystyle n}$ 阶无向完全图${\displaystyle K_{n}}$ 上，不同的（无向）哈密顿圈有${\displaystyle {\frac {(n-1)!}{2}}}$ 个。而若考虑方向，则有${\displaystyle (n-1)!}$ 个有向哈密顿圈。
• ${\displaystyle n}$ 个顶点的图当中，最少边数的哈密顿图是循环图${\displaystyle C_{n}}$ 。任何循环图皆为哈密顿图。
• 循环赛图（英语：Tournament (graph theory)）有奇数条（有向）哈密顿路径。任意（多于两个顶点的）循环赛图为哈密顿图当且仅当其为强连通。^[6]
• 任何以柏拉图立体（凸正多面体）的边与顶点构成的图（“1-骨架（英语：n-skeleton）”）皆为哈密顿图。^[7][8]
• 同样，棱柱与反棱柱的1-骨架也是哈密顿图。
• 13种阿基米德立体的1-骨架皆为哈密顿图，但13种卡塔兰立体当中，仅有7个的1-骨架是哈密顿图。^[9][10].
• 赫歇尔图（英语：Herschel graph）（附图）是众多不具哈密顿圈的凸多面体1-骨架当中，最小的一个。^[11]
• 哈密顿图的线图仍是哈密顿图。^[12]:408
• 欧拉图的线图也是哈密顿图。

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

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

• 哈密顿路径
• 哈密顿路径问题