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

哈密顿有向图

定义 8.28 （哈密顿有向图）若有向图 $G$ 具有一条包含 $G$ 中所有顶点的有向回路，则称

该有向回路为哈密顿回路，称 $G$ 为哈密顿有向图。若有向图 $G$ 具有一条包含 $G$ 中所有顶点的有向路，则称该路为哈密顿有向路，称 $G$ 为半哈密顿有向图。

显然哈密顿有向图是包含 $G$ 中每个顶点一次且仅一次的有向回路，所以哈密顿有向图必定是强连通图。在这里我们仅考虑一种比较简单的情况，给出哈密顿有向图的充分条件。

定理8．22 任何一个竞赛图是半哈密顿有向图。
证明：若竞赛图的顶点数小于 4 ，显然有一条哈密顿有向路。
归纳步骤：假设 $n$ 个顶点的任一竞赛图是半哈密顿有向图。设 $G$ 是 $n+1$ 个顶点的竞赛图，从 $G$ 中删去顶点 $v$ 及其关联边，得到有向图 $G^{\prime \prime}$ ，由归纳假设，$G^{\prime}$ 有哈密顿有向路 $\left(v_1, v_2, \cdots, v_n\right), G$有 3 种情况。
（1）在 $G$ 中有一条弧 $\left(v, v_1\right)$ ，则有哈密顿有向路 $\left(v, v_1, v_2, \cdots, v_n\right)$ ；
（2）在 $G$ 中没有弧 $\left(v, v_1\right)$ ，则必有弧 $\left(v_1, v\right)$ 。若存在 $v_i, v_i$ 是 $v_1$ 之后第一个碰到并且有弧 $\left(v, v_i\right)$的顶点，则显然得到一条哈密顿有向路（ $v_1, v_2, \cdots, v_{i-1}, v, v_i, \cdots, v_n$ ）；；
（3）在 $G$ 中没有弧 $\left(v, v_i\right)$ ，而对所有 $v_i$ ，均有弧 $\left(v_i, v\right), i=1,2, \cdots, n$ ，则得一条哈密顿有向路（ $v_1, v_2, \cdots, v_n, v$ ）。

所以，由定理 8．22，$n$ 位网球选手进行单循环比赛，这 $n$ 位选手一定能依次排出一个优胜次序，然而这种次序可能有几种。进一步，我们可以得到一个更强的结果。

定理 8.23 任何一个强连通的竞赛图 $G$ 必是哈密顿有向图。
证明：下面证明一个 $n$ 个顶点的强连通竞赛图 $G$ 包含长度为 $3,4, \cdots, n$ 的有向回路。首先证明 $G$ 包含长度为 3 的有向回路。设 $v$ 是 $G$ 的任何顶点，$G$ 中所有弧 $(v, w)$ 的顶点 $w$ 全体记为 $W$ ，所有弧 $(z, v)$ 的顶点 $z$ 全体记为 $Z$ 。因为 $G$ 是强连通的，$W$ 和 $Z$ 全是非空集，所以在 $G$ 中必有顶点 $w^{\prime} \in W$ 以及 $z^{\prime} \in Z$ 的弧 $\left(w^{\prime}, z^{\prime}\right)$ ，于是得到长度为 3 的有向回路 $\left(v, w^{\prime}, z^{\prime}, v\right)$ 。

对 $k$ 归纳证明，假设有长度为 $k$ 的有向回路 $(k<n)$ ，则必有长度为 $k+1$ 的有向回路。假设 $\left(v_1\right.$ ， $v_2, \cdots, v_{i-1}, v, v_i \cdots, v_k, v_1$ ）是一条长度为 $k$ 的有向回路，现在考察长度为 $k+1$ ，分两种情况：
（1）如果有一个不在这条有向回路上的顶点 $v$ ，由于 $G$ 是强连通竞赛图，那么，$v$ 有这样的性质，在 $G$ 中既有弧 $\left(v, v_t\right)$ ，又有弧 $\left(v_j, v\right)$ ，所以必存在 $v_i$ ，使 $\left(v_{i-1}, v\right)$ 和 $\left(v, v_i\right)$ 都是 $G$ 中的弧，于是得到长度为 $k+1$ 的有向回路 $\left(v_1, v_2, \cdots, v_{i-1}, v, v_i, \cdots, v_k, v_1\right)$ 。
（2）如果不存在（1）所述性质的 $v$ ，那么 $v$ 有这样的性质，或者只有弧 $\left(v, v_i\right)$ ，或者只有弧 $\left(v_j, v\right)$ ，也就是说，不属于有向回路上的顶点集可以分为两个不相交集 $W$ 和 $Z$ ，其中 $W$ 是对于有向回路上每个顶点 $v_i$ ，使得 $\left(v_i, w\right)$ 是一条弧的顶点 $w$ 全体，$Z$ 是对于有向回路上每个顶点 $v_i$ ，使得 $\left(z, v_i\right)$ 是一条弧的顶点 $z$ 的全体。由于 $G$ 是强连通竞赛图，$W$ 和 $Z$ 均为非空集，且 $W$ 中每个顶点与 $Z$ 中每个顶点之间有弧，所以在 $G$ 中必有 $w^{\prime} \in W$ 和 $z^{\prime} \in Z$ 的弧（ $w^{\prime}, z^{\prime}$ ），于是得到一条长度为 $k+1$ 的有向回路 $\left(v_1, w^{\prime}, z^{\prime}, v_3, \cdots, v_k, v_1\right)$ 。

定理 8.24 （King—Chicken 定理）在任何竞赛图中，存在最大出度顶点到其他任何顶点的，长度不超过 2 的有向路。

证明：假设命题不成立，即对于具有最大出度的顶点 $u$ ，存在一个顶点 $v$ ，从 $u$ 到 $v$ 的有向路长度大于等于 3 。则存在从 $v$ 到 $u$ 以及 $u$ 的所有邻接点的弧，所以 $v$ 的出度大于 $u$ 的出度，导致矛盾。

货郎担问题／最邻近方法
设有 $n$ 个城镇，已知每两个城镇之间的距离。一个货郎从某一城镇出发巡回售货，问这个货郎应该如何选择路线，使每个城镇经过一次且仅一次，并且总的行程最短。这个问题称为货郎担（Traveling Salesman）问题。

如果用 $n$ 个顶点表示 $n$ 个城镇，用连接两点的边上的权值表示对应的两个城镇之间的距离；这样货郎担问题就转化为一个图论的问题：在一个带权的完全图中，找一个总的权最小的哈密顿回路。

货郎担问题的解决可以用穷举的方法，在 $n$ 个顶点的带权的完全图中，所有不同的哈密顿回路（包括有公共边的情况）是 $((n-1)!) / 2$ 。因为从任意一点开始，第一点可选 $n-1$ 条边，第二点可选 $n-2$ 条边，$\cdots \cdots$ ，所有可能的选取总数为 $(n-1)$ ！，而每一条哈密顿回路被计算 2次，所以哈密顿回路的总数是 $((n-1)!) / 2$ 。在这么多的哈密顿回路中求一个总的权最小的哈密顿回路，它的计算量是相当大的。

求最优解的有效算法至今尚未找到，下面给出一个较好的近似算法——最邻近方法。
设 $G=(V, E, \omega)$ 是 $n$ 个顶点的带权完全图，$\omega$ 是从 $E$ 到正实数集的函数，对 $V$ 中任何 3个顶点 $i, j, k$ 满足：$\omega(i, j)+\omega(j, k) \geqslant \omega(i, k)$ 。求最小权的哈密顿回路的最邻近方法步骤如下。
（1）任选一点 $v_0$ 作起点，找一个与 $v_0$ 最近的相邻点 $x$ ，得到一边构成的路。
（2）设 $x$ 是新加到这条路中的一点，从不在路中的所有点中，选一个与 $x$ 最近的相邻点，将它与 $x$ 连成一边。构成一条新的路，重复此过程，直到 $G$ 中所有顶点都在所构成的路中。
（3）连接 $v_0$ 和最后加到路中的顶点，构成一条回路，它就是带权的哈密顿回路。

例 8.4 图 8.13 以点 $a$ 为起点，根据最邻近法逐点构造一条哈密顿回路，这条回路为 $a, c, b, e, d, a$ ，总长度为 38 。而最小权的哈密顿回路为 $a, c, d, b, e, a$ ，总长度为 30 。
 ![图片](/uploads/2025-01/08ef2a.jpg)

刷题

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

上一篇：哈密顿图

下一篇：最短路

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