最后更新: 2025-01-22 09:25 查看: 271 次纠错评论(0) 课件开VIP

哈密顿图

哈密顿图与半哈密顿图
1859 年，哈密顿（Halmilton）爵士发明了一个关于十二面体的一个数学游戏，如图 8.11所示，一位旅行者沿着顶点标有城市名称的正十二面体的棱线行走，他要找一条通过每个顶点（城市）恰好一次的回路。这样就引出了一个问题：能不能在图中找到一条回路，使它含有这个图的所有顶点？哈密顿爵士把这个问题称为周游世界问题。

这一游戏抽象出图论中一个概念——哈密顿（Halmilton）图，并派生出货郎担（Traveling Salesman）问题。

定义8．26（哈密顿图）若图 $G$ 具有一条包含 $G$ 中所有顶点的回路，则称该回路为哈密顿回路，称 $G$ 为哈密顿图。若图 $G$ 具有一条包含 $G$ 中所有顶点的路，则称该路为哈密顿路，称 $G$ 为半哈密顿图。

显然哈密顿路通过图中每个顶点一次且仅一次，哈密顿
 ![图片](/uploads/2025-01/083974.jpg)
图8．11回路则是从图中的一个顶点出发，通过每个顶点一次且仅一次，最后回到出发点的回路。

对于哈密顿图的性质，首先要说明的是有关哈密顿图性质的研究成果与欧拉图性质的研究成果不同，哈密顿图的充要条件至今仍然是图论中尚未解决的主要问题之一。我们只能分别给出哈密顿图的充分条件和必要条件。首先我们给出哈密顿图的必要条件。

定理 8.19 （必要条件）若图 $G$ 是哈密顿图，则对于顶点集 $V$ 的每一个非空真子集 $S$ ， $\omega(G-S) \leqslant|S|$ 均成立，其中 $|S|$ 表示 $S$ 中的顶点数，$G-S$ 表示 $G$ 中删去顶点子集 $S$ 后得到的图。

证明：设 $C$ 是图 $G$ 的一个哈密顿回路，则对 $V$ 的每一个非空真子集 $S, \omega(C-S) \leqslant|S|$ ；则 $\omega(G-S) \leqslant \omega(C-S) \leqslant|S|$ 。

利用定理 8.19 可以判定某些图不是哈密顿图。如图8．12（a）中，令 $S=\left\{v_1, v_4\right\}$ ，则 $\omega(G-S)=3>|S|$ ，所以该图不是哈密顿图。
 ![图片](/uploads/2025-01/c34317.jpg)
 
 必须特别注意定理 8.19 是必要条件。例如，著名的彼得森（Petersen）图如图8．12（b）所示，在图中删去任意一个顶点或任意两个顶点，彼得森图是连通图；删去 3 个顶点，最多只能得到有两个连通分支的子图；删去 4 个顶点，最多只能得到有 3 个连通分支的子图；删去 5 个或 5 个以上的顶点，余下的顶点数都不大于 5 ，故必不能有 5 个以上的连通分支数。所以该图满足 $\omega(G-S) \leqslant|S|$ ，但是可以证明彼得森图不是哈密顿图（证明留作习题）。

下面介绍哈密顿图的充分条件。
定理 8.20 （充分条件）若 $G$ 是 $n(\geqslant 3)$ 个顶点的简单图，对于每一对不相邻的顶点 $u, v$ ， $d(u)+d(v) \geqslant n$ 成立，则 $G$ 是哈密顿图。

证明：假设存在满足条件的 $n(\geqslant 3)$ 个顶点的非哈密顿图 $G$ 。通过加边，可得最大非哈密顿图 $G^{\prime}$ ，（即在 $G^{\prime}$ 中加入任意一边后，得哈密顿图）。将边 $\{u, v\}$ 加入 $G^{\prime}$ ，得一条包含 $G^{\prime}$ 中每一个顶点的路 $\left(v_1, v_2, \cdots, v_n\right), u=v_1, v=v_n$ 。但因为 $G^{\prime}$ 是非哈密顿图，$v_1$ 与 $v_n$ 不相邻，并且 $d\left(v_1\right)+d\left(v_n\right)$ $\geqslant n$ ，因而必存在某顶点 $v_i$ ，使 $v_1$ 与 $v_i$ 相邻，$v_{i-1}$ 与 $v_n$ 不相邻。否则，若 $v_1$ 与 $v_{i_1}, v_{i_2}, \cdots, v_{i_k}$ 相邻 $\left(2 \leqslant i_1 \leqslant i_2 \leqslant \cdots \leqslant i_k \leqslant n-1\right), d\left(v_1\right)=k$ ；而 $v_n$ 与 $v_{i_1-1}, v_{i_2-1}, \cdots, v_{i_k-1}$ 都不相邻，$d\left(v_n\right) \leqslant n-k-1$ ， $d\left(v_1\right)+d\left(v_n\right) \leqslant k+n-k-1=n-1<n$ ，这是不可能的。所以，必存在顶点 $v_i$ ，使 $v_1$ 与 $v_i$ 相邻，$v_{i-1}$ 与 $v_n$ 相邻。从而在 $G^{\prime}$ 中得到一条哈密顿回路 $\left(v_1, v_2, \cdots, v_{i-1}, v_n, v_{n-1}, \cdots, v_i, v_1\right)$ ，这与假设 $G^{\prime}$ 是非哈密顿图相矛盾。

推论 8.2 若 $G$ 是 $n(n \geqslant 3)$ 个顶点的简单图，对于每一个顶点 $v$ ，满足 $d(v) \geqslant n / 2$ ，则 $G$ 是哈密顿图。

证明：利用定理 8.20 即证得。
定理 8.21 若 $G$ 是 $n$ 个顶点的简单图，对于每一对不相邻的顶点 $u, v$ ，满足 $d(u)+d(v) \geqslant$ $n-1$ ，则 $G$ 是半哈密顿图。

证明留作习题。
注意定理 8.20 和定理 8.21 的条件不是必要的，可以举例说明（留作习题）。

下面给出并行计算的一种模型，称为 $n$－立方或超立方。一般地，$n$－立方定义如下。
$n$－立方（超立方）是一个具有 $2^n$ 个顶点的图，它的每个顶点标以字长为 $n$ 的一个二进制数，并且两个顶点的标号恰有一位数字不同，当且仅当这两个顶点间连一边。

可以证明：当 $n \geqslant 2$ 时，$n$－立方是一个哈密顿图（证明留作习题）。
在 $2^n$ 个字长为 $n$ 的二进制数所组成的序列中，每两个相邻的二进制数恰有一位数字不同，则称该序列为格雷码（Gray Code）。

随着计算机硬件价格的下降，建造带有多个处理机的并行计算机已成为可行的，$n$－立方就是并行计算的一种模型，详述可见有关并行计算的文献和书籍。

竞赛图
$n$ 位网球选手进行单循环比赛，即在每两个选手之间都要比赛一场，显然，网球比赛没有平局。用有向图表示 $n$ 位网球选手的单循环比赛：$n$ 位网球选手组成有向图的顶点集合，每个选手对应一个顶点；当甲选手胜了乙选手时，有一条以甲为尾以乙为头的弧。这样表示竞赛的有向图，在任何两个顶点之间，有且仅有一条弧。下面给出竞赛图的定义。

定义8．27（竞赛图）若有向图 $G$ 中每两个顶点之间恰有一条弧，则称 $G$ 为竞赛图。
因此竞赛图也可以说是有向化的完全图。

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

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

免费注册

《高等数学》难点解析

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

《线性代数》难点解析

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

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

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

上一篇：欧拉图和半欧拉图

下一篇：哈密顿有向图

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