最后更新: 2023-11-07 19:28 查看: 550 次纠错评论(0) 课件开VIP

哈密顿图

## 定义

哈密顿路径: 在无向图 $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)

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：欧拉图

下一篇：没有了

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