哈密顿图

哈密顿图（台湾作汉米顿图）又称汉密顿图，是指存在哈密顿环的无向图，由哈密顿爵士提出。

十二面体中的哈密顿回路

定义

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

哈密顿路径

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

哈密顿环

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

哈密顿图

有哈密顿圈的图。

半哈密顿图

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

哈密顿连通图

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

哈密顿分解

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

亚哈密顿图

亚哈密顿图并非哈密顿图，但只要移除任何一个顶点，就会变成哈密顿图。

• 
  非哈密顿图
• 
  半哈密顿图
• 
  哈密顿图

性质

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

充分条件

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

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

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

狄拉克定理

盖布瑞·狄拉克于1952年证明以下定理：

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

欧尔定理

主条目：奥尔定理

设 $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\geq 3$），若满足：

1. 对所有满足$1\leq k<{\frac {n-1}{2}}$的整数$k$，度不大于$k$的顶点个数，严格小于$k$；
2. 度不大于${\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<1$且$0+1<2$）。

例子

赫歇尔图

• 超过2个顶点的完全图是哈密顿图。$n$阶无向完全图$K_{n}$上，不同的（无向）哈密顿圈有${\frac {(n-1)!}{2}}$个。而若考虑方向，则有$(n-1)!$个有向哈密顿圈。
• $n$个顶点的图当中，最少边数的哈密顿图是循环图$C_{n}$。任何循环图皆为哈密顿图。
• 循环赛图有奇数条（有向）哈密顿路径。任意（多于两个顶点的）循环赛图为哈密顿图当且仅当其为强连通。
• 任何以柏拉图立体（凸正多面体）的边与顶点构成的图（“1-骨架”）皆为哈密顿图。
• 同样，棱柱与反棱柱的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所连的节点进行转移。

参见

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