哈密顿图 Hamiltonian Graphs

定义

欧拉图：给定的连通图 $G$ 是否存在一条包含其每一条边的闭迹。

哈密顿图（Hamiltonian graph）：图中存在一条闭迹恰好一次经过 $G$ 的每一个顶点。

• 这样的迹一定是一个圈，除了当 $G$ 是图 $N_1$（只有 1 个顶点的零图）时。
• 这样的圈是一个哈密顿圈（Hamiltonian cycle），而 $G$​ 是一个哈密顿图。

半哈密顿图：如果一个非哈密顿图 $G$ 存在一条经过每一个顶点的路径，那么 $G$ 是半哈密顿图。

• 不一定封闭！

哈密顿图的判定

如何判定一个图是不是哈密顿图？

其中最著名的可能是由 G.A.Dirac 提出的，被称为狄拉克定理（Dirac’s theorem）。我们从 O.Ore（奥勒）的一个更一般的结果推导出狄拉克定理。奥勒定理（Ore’s Theorem）是图论中的一个经典定理，它给出了图是哈密顿图的一个充分条件。

定理7.1（奥勒，1960）：设 $G$ 是一个具有 $n$（$n\ge 3$）个顶点的简单图，如果对于每一对不相邻的顶点 $v$ 和 $w$，都有$deg(v)+deg(w)\ge n$，那么 $G$​ 是哈密顿图。

证明：

• 反证法假设：假设存在一个不包含哈密顿圈的非哈密顿图 $G$，它满足对于每一对非相邻顶点 $v$ 和 $w$，都有 $\mathrm{deg}(v)+\mathrm{deg}(w)\ge n$。

• 最长路径的存在性：在 $G$ 中，我们可以找到一个最长的路径 $P$。这条路径可能不包含 $G$​ 的所有顶点，但包含尽可能多的顶点。

  • 设该路径 $P$ 的顶点序列为 $v_1,v_2,\dots ,v_k$，其中路径的顶点数 $k<n$，一定是小于 $n$，否则就是半哈密顿图。

• 路径的性质：由于 $P$ 是最长路径，故两个端点 $v_1$ 和 $v_k$ 一定不相邻，否则我们可以通过加入边 $v_k{v}_1$ 将 $P$ 封闭成一个圈，并且尝试在该圈上找到更长的路径，这与假设 $P$ 是最长路径矛盾。

• 非相邻顶点的度数和：由于 $v_1$ 和 $v_k$ 不相邻，根据假设条件，我们有 $\mathrm{deg}(v_1)+\mathrm{deg}(v_k)\ge n$，说明 $v_1$ 和 $v_k$ 总共至少与 $n$​ 个顶点相连 。

  • 由于 $v_1$ 和 $v_k$ 都位于路径 $P$ 的端点，且 $P$ 是最长路径，说明 $v_1$ 和 $v_k$ 不可能和路径外的其他 $n-k$ 个顶点相连。
  • 而 $v_1$ 和 $v_k$ 又总共至少与 $n$ 个顶点相连，说明 $v_1$ 和 $v_k$ 只能和路径 $P$ 中的顶点相连，即度数不会超过 $n-k+1$。
  • 同时，$v_1$ 和 $v_k$ 至少各自与 $P$ 中的一个其他顶点相连，不会存在其中一个端点度为 1 的情况。
    • 假如 $v_1$ 度为 1，那么 $v_k$ 的度为 $n-1$，这与 $v_k$ 的度不会超过 $n-k+1$ 矛盾。

• 路径 $P$ 中必存在圈：综上所述，存在至少一个顶点 $v_i$（$1<i<n-1$）在 $P$ 上与 $v_1$ 相邻，并且 $v_{i-1}$ 与 $v_k$ 相邻。这意味着我们可以将 $v_1$ 和 $v_k$ 连接起来，形成一个圈：$v_1\to v_2\to \cdots \to v_{i-1}\to v_k\to v_{k-1}\to \cdots \to v_{i+1}\to v_i\to v_1$​（如图 7.5 所示）。

  

• 拓展路径构成矛盾：最长路径 $P$ 中形成了圈，设 $u$ 是一个不在 $P$ 中的顶点，考虑 $u$ 与路径 $P$ 上顶点的连接情况。

  • 情况 1：如果 $u$ 与 $v_1$ 或 $v_k$ 中的一个顶点相邻。
    • 这样就可以将 $u$ 加入到路径 $P$ 中，使得 $P$ 变得更长，从而与 $P$ 是最长路径的假设矛盾。
  • 情况 2：如果 $u$ 与 $v_1$ 和 $v_k$ 都不相邻。
    • 根据假设条件，对于不相邻的 $v_1$​ 和 $u$，有 $deg(v_1)+\mathrm{deg}(u)\ge n$。同理，对于不相邻的 $v_k$​ 和 $u$ 也有 $deg(v_k)+\mathrm{deg}(u)\ge n$。因此 $u$ 必然与路径 $P$ 中的许多顶点相邻。
    • 那么通过路径中的圈，该路径总能和顶点 $u$ 相连，于是可以添加顶点 $u$ 到该路径 $P$ 中，形成更长的路径，这与 $P$​ 是最长路径的假设相矛盾。

• 结论：因此，我们的假设是错误的，如果在图中对于每一对不相邻的顶点 $v$ 和 $w$，都有$deg(v)+deg(w)\ge n$，图 $G$ 中必然包含一个具有 $n$ 个顶点且存在圈的路径，即哈密顿圈，图 $G$ 肯定是哈密顿图。

推论7.2（狄拉克，1952）：设 $G$ 是一个具有 $n$（$n\ge 3$）个顶点的简单图，如果对于每个顶点 $v$，都有 $deg(v)\ge n/2$，那么 $G$ 是哈密顿图。

证明：这个结果直接由定理7.1得出，因为对于每一对顶点 $v$ 和 $w$，无论它们是否相邻，都有 $deg(v)+deg(w)\ge n$。