最后更新: 2023-11-07 19:28 查看: 449 次反馈刷题

哈密顿图

## 定义

哈密顿路径: 在无向图 $G$ 中包含其所有顶点的初级路径

哈密顿回路：在无向图 $G$ 中包含其所有顶点的初级回路

哈密顿图: 具有哈密顿回路的无向图

例1: 下图中(a)，哈密顿提出的「周游世界」的游戏。把一个正十二面体的二十个顶点看成地球上的二十个城市。要求游戏者沿棱线走，寻找一条经过所有结点一次且仅一次的回路，(b)是其哈密顿图，哈密顿回路由实线标出。

![图片](/uploads/2023-10/0e7bc2.jpg)
例2：下图中，图(a)(b)中有哈密顿回路，为哈密顿图，图(c)中有哈密顿路径，(d)中两者均无
![图片](/uploads/2023-10/55525f.jpg)
PS：欧拉图与哈密顿图对比，欧拉图遍历的是边，而哈密顿图遍历的是结点。

## 哈密顿图的判定

对于哈密尔顿图的判定，只能给出若干必要条件或充分条件，没有充要条件。
1.必要条件

定理 (1): 若 $G$ 是哈密尔顿图，则对于结点集 $V(G)$ 的任一非空真子集 $S \subset V(G)$ 有 $\omega(G-S) \leq|S|$ 。其中 $G-S$ 表示在 $G$ 中删去 $S$ 中的结点后所构成的图， $\omega(G-S)$ 表示 $G-S$ 的连通分支数。

证明: 设 $C$ 是 $G$ 的一条哈密顿回路， $C$ 视为 $G$ 的子图，在回路 $C$ 中，每删去 $S$ 中的一个结点，最多增加一个连通分支，且删去 $S$ 中的第一个结点时分支数不变，所以有 $\omega(C-S) \leq|S|$。又因为 $C$ 是 $G$ 的生成子图，所以 $C-S$ 是 $G-S$ 的生成子图，且 $\omega(G-S) \leq \omega(C-S)$ ，因此 $\omega(G-S) \leq|S|$ 。

推论: 若 $G$ 含有哈密尔顿路径，即半哈密尔顿图，则对于结点集 $V(G)$ 的任一非空真子集 $S \subset V(G)$ 有 $\omega(G-S) \leq|S|+1$ 。

思路：因为不是回路，在哈密尔顿通路上删除第一个点，最多可以产生两个分支。

PS：哈密顿图的必要条件，可用来判定某些图不是哈密尔顿图，是破坏条件。

例3: 下图中，(a)不是哈密尔顿图。(a)中如果删除中间三个白点，即 $|S|=3$ ，而此时 $\omega(G-S)=4$ ，见图(b)。(c)虽然满足定理(1)，但不是哈密顿图。
![图片](/uploads/2023-10/de9413.jpg)

2. 充分条件

首先引入扩大路径法:

设 $G=\langle V, E\rangle$ 为 $n$ 阶无向图， $\Gamma_l$ 为 $G$ 中一条初级路径。若此路径的起点或终点，与路径外的结点相邻，就将他们扩充到路径中，重复这一过程，直到路径的两端不与路径外的结点相邻为止。最后得到的路径 $\Gamma_{l+k}$ 为一条极大路径 (由长度 $l$ 扩充到 $l+k$ ，且不唯一)，并称使用此种方法证明问题的方法为扩大路径法。

例3: 设 $G$ 为 $n(n \geq 3)$ 阶无向简单图，最小度 $\delta \geq 2$ 。证明 $G$ 中存在长度 $\geq \delta+1$ 的回路。

证明: 设 $\Gamma_l=v_0 v_1 \ldots v_l$ 是 $G$ 中的一条极大路径。由极大路径的定义知， $v_0$ 不与 $\Gamma_l$ 外的结点相邻，而 $d\left(v_0\right) \geq \delta$ ，所以至少存在 $\delta$ 个 $\Gamma_l$ 上的结点与 $v_0$ 相邻。设 $v_\delta$ 是与 $v_0$ 相邻，且在 $\Gamma_l$ 上与 $v_0$ 最远的结点，则路径 $v_0 v_1 \ldots v_\delta$ 的长度 $\geq \delta$ 。于是， $v_0 v_1 \ldots v_\delta v_0$ 为长度 $\geq \delta+1$ 的回路。

定理 (2): 设图 $G$ 是 $n$ 阶的无向简单图 $(n \geq 3)$ ，如果 $G$ 中每一对不相邻的结点 $u, v$ 均有 $d(u)+d(v) \geq n-1$ ，则 $G$ 中存在哈密顿路径。

证明:
(1) 证明 $G$ 是连通图

反证法: 若 $G$ 不是连通图，则至少存在两个分支。设连通分支 $G_1, G_2$ 的阶数为 $n_1, n_2$ 。不妨设 $u \in V\left(G_1\right), v \in V\left(G_2\right)$ ，则有 $d(u)+d(v) \leq\left(n_1-1\right)+\left(n_2-1\right)=n-2$ ，此与题设矛盾，所以 $G$ 是连通图。
(2) 证明 $G$ 中存在哈密顿路径

设 $\Gamma_l=v_1 v_2 \ldots v_l$ 为 $G$ 中的一条极大路径。
(1) 若 $l=n$ ，则找到一条哈密顿路径 $\Gamma_l$ ；
(2) 若 $l<n$ ，则必定存在一点 $v_{o u t}$ 与 $\Gamma_l$ 上除 $v_1, v_l$ 外的端点相连。此时，若存在圈 $C$ 刚好经过 $\Gamma_l$ 上的所有点，则圈 $C$ 又可与 $v_{o u t}$ 组合成更长的极大路径 $\Gamma_{l+1}$ 。

重复上述(1)(2)过程，最终找到一条哈密顿路径。

下面证明，存在回路 $C$ 经过 $\Gamma_l$ 上所有的点。
(1) 若 $v_1, v_l$ 相邻，则容易找到回路 $C$;
(2) 若 $v_1, v_l$ 不相邻，设 $v_1$ 与 $\Gamma_l$ 上的 $v_{i_1}=v_2, v_{i_2}, \ldots, v_{i_k}$ 相邻，则 $k \geq 2$ 。否则， $d\left(v_1\right)+d\left(v_l\right)=1+l-2<n-2$ 。 又 $v_l$ 至少与 $v_{i_2-1}, v_{i_3-1} \ldots, v_{i_k-1}$ 之一相邻，否则， $d\left(v_1\right)+d\left(v_l\right)=k+[l-2-(k-1)]<n-2$ 。设 $v_l$ 与 $v_{i_r-1}$ 相邻，则得到回路 $C=\left(v_1 v_2 \ldots v_{i_r-1} v_l v_{l-1} \ldots v_{i_r} v_1\right) 。$
![图片](/uploads/2023-10/c9f134.jpg)
定理 (3): 设图 $G$ 是 $n$ 阶的无向简单图 $(n \geq 3)$ ，对于 $G$ 中每一对不相邻的结点 $u, v$ 均有 $d(u)+d(v) \geq n$ ，则 $G$ 是哈密顿图。

但不满足定理(2)(3)的，不一定不是哈密顿图。如下图，不满足定理(2)(3)，但是哈密顿图。
![图片](/uploads/2023-10/77528f.jpg)

刷题

做题，是检验是否掌握数学的唯一真理

上一篇：欧拉图

下一篇：没有了

本文对您是否有用？有用 (0) 无用 (0)