哈密顿图

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

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

非哈密顿图

半哈密顿图

哈密顿图

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

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

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

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

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

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

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

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

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

一幅${\displaystyle n}$个顶点的完全图（${\displaystyle n\ge <!--\; \ge \; -->3}$），若满足：

则必为哈密顿图。

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

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

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

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