哈密顿图

定义

哈密顿通路是初级通路，哈密顿回路是初级回路。环与平行边不影响哈密顿性。哈密顿图的实质是能将图中的所有顶点排列在同一个圈上。

哈密顿图与欧拉图的区别：经过所有顶点一次且仅一次，没有不经过的顶点，但对边没有要求，可以有重复经过或者未经过的边（当然由定义推断得到，不可能重复经过一条边）。

定理：设无向图 $G = ⟨ V, E ⟩$ 是哈密顿图，对于任意 $V^{'} \subset V$ 且 $V^{'} \neq = \emptyset$ ，均有： $p (G - V^{'}) \leq ∣ V^{'} ∣$

推论：设无向图 $G = ⟨ V, E ⟩$ 是半哈密顿图，对于任意 $V^{'} \subset V$ 且 $V^{'} \neq = \emptyset$ ，均有： $p (G - V^{'}) \leq ∣ V^{'} ∣ + 1$

二部图情形：设二部图 $G = ⟨ V_{1}, V_{2}, E ⟩$ ， $∣ V_{1} ∣ \leq ∣ V_{2} ∣$ ：

定理（狄拉克型条件）：设 $G$ 是 $n$ （ $n \geq 3$ ）阶无向简单图。若对于任意不相邻的顶点 $u, v$ ，均有 $d (u) + d (v) \geq n$ ，则 $G$ 中存在哈密顿通路。

推论：设 $G$ 为 $n$ （ $n \geq 3$ ）阶无向简单图，若对于 $G$ 中任意两个不相邻的顶点 $u, v$ ，均有 $d (u) + d (v) \geq n$ ，则 $G$ 中存在哈密顿回路，从而 $G$ 为哈密顿图。

定理：设 $u, v$ 为 $n$ 阶无向简单图 $G$ 中两个不相邻的顶点，且 $d (u) + d (v) \geq n$ ，则 $G$ 为哈密顿图当且仅当 $G \cup (u, v)$ 为哈密顿图。

竞赛图： $n$ （ $n \geq 2$ ）阶竞赛图中存在哈密顿通路。

完全图 $K_{n}$ （ $n \geq 3$ ）均为哈密顿图。

带权图：给定图 $G = ⟨ V, E ⟩$ ，设 $w : E \to R$ （ $R$ 为实数集），对任意边 $e$ 赋予实数 $w (e)$ ，称 $G$ 为带权图。

货郎担问题（旅行商问题）：设 $G = ⟨ V, E, w ⟩$ 为一个 $n$ 阶完全带权图 $K_{n}$ ，各边的权非负，求 $G$ 中的一条最短的哈密顿回路。这就是货郎担问题的数学模型。

完全带权图 $K_{n}$ 中不同的哈密顿回路数为 $(n - 1)! /2$ 。用枚举法解货郎担问题的算法复杂度为 $O ((n - 1)!)$ ，当 $n$ 较大时计算量惊人地大。

最短路问题：给定带权图 $G = ⟨ V, E, w ⟩$ （每条边权非负），求从 $u$ 到 $v$ 的最短路径。Dijkstra 标号法是常用算法。