最后更新: 2025-01-22 09:25 查看: 176 次反馈同步训练

哈密顿图

哈密顿图与半哈密顿图
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}$ 相邻 $\l

免费注册看余下 50%

非VIP会员每天15篇文章，开通VIP 无限制查看

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

下一篇：哈密顿有向图

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