最后更新: 2024-04-06 18:33 查看: 190 次反馈刷题

欧拉图与哈密尔顿图

## 欧拉图与哈密尔顿图
定义 17 通过图 (无向图或有向图) 中每条边正好一次的通路称为欧拉通路, 存在欧拉通路的图称为半欧拉图; 通过图中每条边正好一次的回路称为欧拉回路, 存在欧拉回路的图称为欧拉图。

显然, 欧拉通路是简单通路, 欧拉回路是简单回路。欧拉图必定是半欧拉图, 反之,则不然。
判断一个图是否为欧拉图或半欧拉图, 有很简单的充要条件。
定理 11 不含孤立点的无向图 $G$ 是半欧拉图, 当且仅当 $G$ 连通, 且奇度结点为零个或两个。
定理 12 不含孤立点的无向图 $G$ 是欧拉图, 当且仅当 $G$ 连通, 且所有结点的度为偶数。
定理 13 不含孤立点的无向图 $G$ 是欧拉图, 当且仅当 $G$ 连通, 且 $G$ 是边不相交的基本回路的并。

定理 14 不含孤立点的有向图 $D$ 是半欧拉图, 当且仅当 $D$ 弱连通, 且其中一个结点的入度比出度大 1 , 另一个结点的出度比入度大 1 , 其余结点的入度均等于出度。

定理 15 不含孤立点的有向图 $D$ 是欧拉图, 当且仅当 $D$ 弱连通, 且所有结点的入度等于出度。
设 $G$ 为无向欧拉图, 求 $G$ 中一条欧拉回路的算法如下。
Fleury 算法
第 1 步 任取 $G$ 中一结点 $v_0$, 令 $P_0=v_0$ 。
第 2 步 假设 $P=v_0 e_1 e_2 \cdots e_i V_i$ 已选好, 按下面方法从 $E-\left\{e_1, e_2, \cdots, e_i\right\}$ 中选 $e_{i+1}$
(1) $e_{i+1}$ 与 $e_i$ 相关联;
(2) 除非无别的边可供选择, 否则 $e_{i+1}$ 不应该是 $G_i=G-\left\{e_1, e_2, \cdots, e_i\right\}$ 的断边。第 3 步 当第 2 步不能执行时, 算法停止。
有向欧拉图的欧拉回路可类似求出。
作为欧拉图的应用及其推广的例子是邮路问题。设一个邮递员从邮局出发沿着他所管辖的街道送信, 然后返回到邮局, 他应选择怎样的路线, 才能使得所走的实际路程最短呢?我们知道, 如果他管辖的街道恰好成为欧拉图, 就不存在最短路程的问题, 因为不论他怎样安排行走路线, 所走路程总是一定的。但实际问题中一般不会恰巧就是欧拉图, 必然某些街道要重复经过, 因此邮路问题是一个既与欧拉图又与最小权通路有关的问题。邮路问题可用图论的概念描述如下: 在一个带权图 $G$ 中, 怎样找到一条回路 $C$, 使得 $C$ 包含 $G$ 中的每条边至少一次, 而且回路 $C$ 具有最小权。 $C$ 分三种情况:
(1) 如果 $G$ 是欧拉图, 必定有欧拉回路, $C$ 即找到。
（2）如果 $G$ 是具有从 $v_i$ 到 $v_j$ 的欧拉通路的半欧拉图, $C$ 的构造如下: 找从 $v_i$ 到 $v_j$ 的欧拉通路及 $v_i$ 到 $v_j$ 的最小权通路 (即最短路径)。这两条通路合并在一起就是最小权回路。
(3) 如果 $G$ 不是半欧拉图, 一般说来, $G$ 中包括各条边之回路, 其重复的边数与奇结点数目有关, 若奇结点多于 2 , 则回路中会出现更多的重复的边, 问题是怎样使重复边的权总和最小。在理论上已证明: 一条包括 $G$ 的所有边的回路 $C$ 具有最小权当且仅当:
(1) 每条边最多重复一次;
(2) 在 $G$ 的每个回路上, 有重复边的权之和小于回路权的一半。
定义 18 通过图中每个结点正好一次的通路称为哈密尔顿通路, 存在哈密尔顿通路的图称为半哈密尔顿图; 通过图中每个结点正好一次的回路称为哈密尔顿回路, 存在哈密尔顿回路的图称为哈密尔顿图。
哈密尔顿图也是半哈密尔顿图, 反之, 则不然。哈密尔顿图或半哈密尔顿图必连通。
判断一个图是否为欧拉图或半欧拉图有一种简单的方法, 但至今未找到判别一个图是否为哈密尔顿图或半哈密尔顿图的简明的充要条件, 只能给出若干必要条件或充分条件。

定理 16 若无向图 $G=<V, E>$ 是哈密尔顿图, $W$ 是 $V$ 的任意非空子集, 则 $p(G-W) \leq|W|$
定理 16 的实用价值在于利用其逆否命题来判定一个图不是哈密尔顿图。
定理 17 设 $G$ 为 $n$ 阶无向简单图, 若对 $G$ 的任意两个不相邻的结点 $u$ 和 $v$, 有 $\operatorname{deg}(u)+\operatorname{deg}(v) \geq n-1$, 则 $G$ 为半哈密尔顿图。

定理 18 设 $G$ 为 $n$ 阶无向简单图, 且 $n \geq 3$, 若对 $G$ 的任意两个不相邻的结点 $u$ 和 $v$,有 $\operatorname{deg}(u)+\operatorname{deg}(v) \geq n$, 则 $G$ 为哈密尔顿图。

定理 19 设 $G$ 为 $n$ 阶无向简单图, 若对 $G$ 的任一结点 $v$ 有 $\operatorname{deg}(v) \geqslant \frac{n}{2}$, 则 $G$ 为哈密尔顿图。

定理 20 设 $D$ 为 $n$ 阶有向简单图, 若略去 $D$ 的方向后所得无向图中含生成子图 $K_n$,则 $D$ 为半哈密尔顿图。
推论 竞赛图是半哈密尔顿图。
作为哈密尔顿回路的一个推广是推销员问题, 亦称流动售货员问题或货郎担问题。设有一个推销员从公司出发走销附近所有城镇, 然后返回公司, 其旅行路线怎样安排, 才能使总距离最小? 用图论观点来说, 就是要找一条权最小的哈密尔顿回路, 即所谓最小权哈密尔顿回路。研究这类问题很有实用价值, 但至今还未找到好的解决方法。下面给出一种
“近邻法” 或 “最邻近法”, 按此方法求得的哈密尔顿回路未必是最小权哈密尔顿回路, 但很接近最小权哈密尔顿回路。
近邻法
设图为带权无向完全图。
第 1 步任取一个结点为始点, 找一个最靠近始点的结点, 形成一条边的初始路径。
第 2 步 设 $x$ 表示刚加入这条路径的结点, 从所有不在该路径上的结点中选一个最靠近 $x$ 的结点, 将连接 $x$ 和这一结点的边加入该路径。重复这一步, 直到图中所有结点包含在路径上。
第 3 步 将连接始点和最后加入的结点的边加入路径, 便得一条哈密尔顿回路。

子目录

1. 欧拉图

2. 哈密顿图

刷题

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

上一篇：最短路径问题

下一篇：平面图

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