最后更新: 2025-01-22 09:25 查看: 95 次反馈刷题

哈密顿图

哈密顿图与半哈密顿图
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$ 为竞赛图。
因此竞赛图也可以说是有向化的完全图。

刷题

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

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

下一篇：哈密顿有向图

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