最后更新: 2024-04-06 18:33 查看: 277 次纠错评论(0) 课件开VIP

欧拉图与哈密尔顿图

## 欧拉图与哈密尔顿图
定义 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. 哈密顿图

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

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

免费注册

《高等数学》难点解析

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

《线性代数》难点解析

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

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

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

上一篇：附录 C 链同伦及其应用

下一篇：后记

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