哈密尔顿图

⚠ 转载请注明出处：作者：ZobinHuang，更新日期：Mar.23 2022

    本作品由 ZobinHuang 采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可，在进行使用或分享前请查看权限要求。若发现侵权行为，会采取法律手段维护作者正当合法权益，谢谢配合。

目录

有特定需要的内容直接跳转到相关章节查看即可。

正在加载目录...

「哈密尔顿图」与「哈密尔顿路」的定义

    图 $G$ 中存在经过每个顶点恰好一次的圈, 称 $G$ 为 哈密尔顿图 (Hamiltonian graph)，简称 $H$ 图。该圈是 $G$ 的一个生成圈，称为 $G$ 的 哈密尔顿圈 (Hamiltonian Cycle)，简称 $H$ 圈。

    把条件放松，如果存在经过 $G$ 的每个顶点的路, 称该路为 $G$ 的 哈密尔顿路 (Hamiltonian Path)，简称 $H$ 路，称 $G$ 为 可迹的 (Traceable)。

    与我们在 欧拉图和中国邮递员问题 中讨论的欧拉迹的概念对比着来看，我们会发现其实哈密尔顿圈是在求「点不重」的环游方式，而欧拉迹是在求「边不重」的环游方式。

性质与判定

性质

    首先我们给出一个与哈密尔顿图的必要条件 (哈密尔顿所具有的性质):

若图 $G$ 为 $H$ 图，则对 $V(G)$ 的任一非空顶点子集 $S$，有 $\omega(G-S) \le |S|$。

    证明:

    $G$ 是 $H$ 图，设 $C$ 是 $G$ 的 $H$ 圈，则对 $V(G)$ 的任意非空子集 $S$，容易知道: $\omega(C-S) \le |S|$ (i.e. 从圈上删点，有可能会产生新的连通分支，也可能不会)，因此有 $\omega(G-S) \le \omega(C-S) \le |S|$。

    上述不等式是 $H$ 图的性质，并不能用来判断一个图是否为 $H$ 图，但是不满足上述性质的图一定不是 $H$ 图。

    下面再给出几个判断一个图不是 $H$ 图的充分条件:

有割点 (不是分离点) 的图必不是 $H$ 图

不等部的二部图必不是 $H$ 图

    下面给出一个关于 $H$ 路的类似的结论:

若图 $G$ 包含 $H$ 路，则对 $V(G)$ 的任一非空顶点子集 $S$，有 $\omega(G-S) \le |S|+1$

    证明:

    $G$ 是 $H$ 图，设 $P$ 是 $G$ 的 $H$ 路，则对 $V(G)$ 的任意非空子集 $S$，容易知道: $\omega(P-S) \le |S|+1$ (i.e. 从路上删去 $|S|$ 个点，可最多产生 $|S|+1$ 个分支)，因此有 $\omega(G-S) \le \omega(P-S) \le |S|+1$。

判定

    图的 $H$ 性判定是 $NP$-完全问题. 到目前为止, 有关的定理有 300+, 但没有一个是理想的(充分必要的)。下面我们介绍几个著名的定理。

Dirac 定理

    下面对和充分性有关的 Dirac 定理 进行介绍。

对于 $n \ge 3$ 的简单图 $G$，如果 $G$ 中有 $\delta(G) \ge \frac{n}{2}$，那么 $G$ 是 $H$ 图。

    现在我们给出关于这个定理的证明。

    我们反转思路，采用反证法证明：

如果 $G$ 是 $n \ge 3$ 的非 $H$ 图，则有$\delta(G) < \frac{n}{2}$ 成立

    首先，我们假设 $G$ 是极大非 $H$ 简单图 (i.e. 给定点数，边数最多的非 $H$ 图)。这里选择极大非 $H$ 简单图是合理的，因为:

1. 命题中的假设是非 $H$ 图，则可以是任意的非 $H$ 图，我们选择极大非 $H$ 简单图以后面证明的方便;
2. 选择极大非 $H$ 简单图并不失一般性，因为非极大的 $H$ 图可以通过加边得到极大的非 $H$ 图，而如果我们如果能够基于极大非 $H$ 图证明出关于最小度上界的结论，那么通过删边，自然关于最小度上界的结论仍然会成立，也即极大非 $H$ 图是我们对我们证明结论最不利的情况。

    下面我们正式开始证明。

    首先，$G$ 一定不能是完全图，否则 $G$ 是 $H$ 图。于是可以考虑在 $G$ 中任意取两个不相邻的顶点 $u$ 和 $v$。考虑 $G+uv$，由 $G$ 的极大性，可以知道 $G+uv$ 是 $H$ 图，并且 $G+uv$ 的每一个 $H$ 圈必然包含边 $uv$，如下图所示。

    所以在 $G$ 中存在起点为 $u$ 而终点为 $v$ 的 $H$ 路 $P$。不失一般性，设起点为 $u$ 终点为 $v$ 的 $H$ 路 $P$ 为: $P=v_1v_2...v_n$ ($u=v_1$, $v_n=v$)。

    下面我们令 \begin{cases} S=\{v_i|uv_{i+1} \in E(G)\}, i=1,2,...,n-1 \\ T=\{v_j|v_jv \in E(G)\}, j=1,2=...,n-1 \end{cases}

    我们可以把 $S$ 理解为，如果 $u$ 和 $P$ 路上的点 $v_i$ 相邻，那么点 $v_i$ 在 $P$ 路上的前一个点 $v_{i-1}$ 就会被加入到集合中；可以 $T$ 理解为，如果 $v$ 和 $P$ 路上的点 $v_j$ 相邻，那么点 $v_j$ 在本身就会被加入到集合中。

    基于这层定义，显然: $P$ 路上 $v_n$ 没有下一个点，并且 $v_n$ 本身并不与自己邻接，因此有 $v_n \notin S \cup T$，所以 $|S \cup T| < n$。

    如果 $|S \cap T| \ne \emptyset$，则 $\exists v_i \in S \cap T$，使得 $uv_{i+1}, vv_i \in E(G)$，如下图所示。

    这种情况下会出现 $H$ 圈，如下图所示:

    这与我们极大非 $H$ 图的假设相违背，因此我们可以得到结论 $S \cap T = \emptyset$，因此有:

$$d(u)+d(v) = |S|+|T| = |S \cup T| + |S \cap T| = |S \cup T| < n$$

    因此可以整得 $d(u)$ 和 $d(v)$ 中至少有一个的度数小于 $\frac{n}{2}$，逆否命题证毕，因此有原命题成立。

    上述定理还有增强版形式，如下所示。我们不予以证明。

设 $G$ 是 $2$-连通的 $n \ge 3$ 阶图，若 $G$ 的每个顶点的度都不小于 $k$，则 $G$ 中包含一条长度至少为 $2k$ 的圈或 $H$ 圈。

Ore 定理

    Ore 对 Dirac 定理进行了优化，如下所示，我们不予以证明。

对于 $n \ge 3$ 的简单图 $G$，若图 $G$ 中的任意两个不相邻顶点 $u$，$v$ 有: $d(u)+d(v) \ge n$，那么 $G$ 是 $H$ 图。

Bondy-Chvátal 定理

    Bondy 和 Chvátal 又对 Ore 定理进行了优化，我们下面先给出一些引理和定义，然后给出 Chvátal 定理。

    首先给出引理，证明过程略。

对于简单图 $G$，若图 $G$ 中，如果 $G$ 中有两个不相邻顶点 $u$，$v$ 有: $d(u)+d(v) \ge n$
那么 $G$ 是 $H$ 图当且仅当 $G+uv$ 是 $H$ 图。

    下面给出一些定义。

    在 $n$ 阶简单图中，若对 $d(u) + d(v) \ge n$ 的任意一对顶点 $u$ 与 $v$，均有 $u \leftrightarrow v$，则称 $G$ 是 闭图 (closed)。

    如上所示是一个非闭图，而如下所示是一个闭图。值得注意的是，下面的图中并不存在 $d(u)+d(v) \ge n$ 的点，因此自然没有点需要满足闭图的条件，所以也算作是一个闭图。

    反复连接 $G$ 中度和不小于 $n$ 的不相邻顶点对，直到没有这样的顶点对存在为止，得到的图称作 $G$ 的 闭包 (closure)，记作 c(G)。

    如果 $G$ 本身是闭图，则其闭包是它本身；如果 $G$ 不是闭图，则可以通过在度和大于等于 $n$ 的不相邻顶点对间加边来构造 $G$ 的闭包。

    值得注意的是，不是任意图的闭包都是完全图，如 $C_5$。

    下面有一个结论，我们不加证明地给出。

图 $G$ 的闭包 $C(G)$ 是唯一的。

    下面是 Bondy-Chvátal 定理，也称为 闭包定理:

图 $G$ 是 $H$ 图当且仅当它的闭包是 $H$ 图

    下面给出证明:

    必要性：如果 $G$ 本身已经是 $H$ 图，在 $G$ 之上添加边并不会改变 $G$ 的哈密尔顿性质，因此其闭包自然地也就是 $H$ 图。

    充分性证明: 假设 $G$ 的闭包是 $H$ 图，下面我们证明 $G$ 是 $H$ 图。

    如果 $G$ 的闭包就是它本身，则结论显然。

    若不然，设 $e_i (1 \le i \le k)$ 是为构造 $G$ 的闭包而添加的所有边，由 8 可知，$G$ 是 $H$ 图当且仅当 $G+e_1$ 是 $H$ 图，而 $G+e_1$ 是 $H$ 图当且仅当 $G+e_1+e_2$ 是 $H$ 图。如此反复，可以得到结论。

    由于完全图一定是 $H$ 图，因此我们可以得到结论：

若 $G$ 是 $n \ge 3$ 的简单图，若 $G$ 的闭包是完全图，则 $G$ 也一定是 $H$ 图。

    闭包定理可以推导出 Dirac 和 Ore 定理:

设 $G$ 是 $n \ge 3$ 的简单图，

1. 若 $\delta (G) \ge \frac{n}{2}$，则 $G$ 是 $H$ 图 (Dirac 定理);
2. 若对于 $G$ 中任意不相邻的顶点 $u$ 和 $v$，都有 $d(u)+d(v) \ge n$，则 $G$ 是 $H$ 图 (Ore 定理)

度序列判定法

    在闭包定理的基础上，Chvátal 进一步得到图的 $H$ 性的度序列判定法:

设简单图 $G$ 的度序列是 $(d_1,d_2, …,d_n)$，其中，$d_1 \le d_2 \le … \le d_n$，并且 $n \ge 3$：若对任意的$1 \le i \le \frac{n}{2}$，有 $d_i>i$ (i.e. 等价于 $d_{n−i} \ge n−i$)，则 $G$ 是 $H$ 图。

    等价表述是：

设简单图 $G$ 的度序列是 $(d_1,d_2, …,d_n)$，其中，$d_1 \le d_2 \le … \le d_n$，并且 $n \ge 3$：若不存在 $1 \le i \le \frac{n}{2}$，使得 $d_i \le i$ (i.e. 等价于 $d_{n−i} < n−i$)，则 $G$ 是 $H$ 图。

    证明:

    思路是证明满足上述条件的 $G$ 的闭包 $C(G)$ 是完全图，这样 $C(G)$ 就是 $H$ 图，故原图即 $H$ 图。我们使用反证法证明 $C(G)$ 是一个完全图。

    我们假设满足上述条件的 $C(G)$ 不是一个完全图，然后证明: 存在 $1 \le i \le \frac{n}{2}$，使得 $d_i \le i$ 和 $d_{n-i} \le n-i$ 同时成立，即与条件矛盾。

    若 $C(G)$ 不是完全图:

    首先证明第一个假设 $d_i \le i$。则在 $C(G)$ 中存在不相邻的两点 $u$ 和 $v$，使得 $d(v)+d(u) < n$，且不妨设 $u$ 和 $v$ 是不相邻点中度和 $d(v)+d(u)$ 最大的两点。另一方面，不妨设 $d(u) \le d(v)$，那么 $1 \le d(u) < \frac{n}{2}$。设 $d(u)=i$，则 $d(v) < n-i$，也即 $d(v) \le n-1-i$，说明与 $v$ 相邻的节点不超过 $n-1-i$ 个邻点，故与 $v$ 不相邻的节点至少有 $i$ 个，而与 $v$ 相邻的点中 $u$ 的度最大 (i.e. $d(u)=i$)，即有 $i$ 个点度不超过 $i$，故有 $d_i \le i$。这与假设矛盾。

    然后证明第二个假设 $d_{n-i} \le n-i$。由于 $d(u)=i$。这说明与 $u$ 邻接的点有 $i$ 个，则与 $u$ 不相邻的点有 $n-1-i$ 个，而这些点中 $v$ 的度最大，有 $d(v) < n-i$。因此我们已经找到了 $n-1-i$ 个点，它们的度小于 $n-i$。再加上 $u$ 自己，我们就找到了 $n-i$ 个点的度小于 $n-i$，也即 $d_{n-i} < n-i$。这与假设矛盾。

    可见，若 $C(G)$ 不是完全图，$C(G)$ 将违背假设条件，因此 $C(G)$ 是完全图，故 $C(G)$ 是 $H$ 图，故 $G$ 是 $H$ 图。