离散数学_第15章_欧拉图与哈密顿图

（ 1）
（ 2）
（ 3）
（ 5） （ 6） 图2 易知，图 2 中， （1 ） 、 （4）为欧拉图， （ 2） ， （5）为半欧拉图， （3） ， （6） 既不是欧拉图，也不是半欧拉图. 在（3） ， （6）中各至少加几条边才能 成为欧拉图？ N 为何值时，无向完全图是欧拉图？为何值时，为半欧拉 图？什么样的完全二部图是欧拉图？
英 英
G 法 德
俄 意 D
F
汉
C
日
E
第三节 最短路问题与货郎担问题
一、带权图 定义 15.3 给定图 G = <V,E>， （G 为无向图或有向图） ， 设 W：ER（R 为实数集） ，对 G 中任意边 e = (vi,vj) （G 为有向图时，e = <vi,vj>） ，设 W(e) = wij，称实数 wij 为边 e 上的权，并将 wij 标注在边 e源自文库上，称 G 为带权图， 此时常将带权图 G 记作 <V,E,W>. 设 GG，称
第十五章 欧拉图与哈密顿图
本章的内容 欧拉图 哈密顿图 带权图与货郎担问题 本章的先行知识是第十四章
第一节 欧拉图
历史背景：哥尼斯堡七桥问题与欧拉图
（1）
（2）
图1 其实，欧拉图是一笔画出的边不重复的回路.
一、 欧拉图的定义与判别法 1. 欧拉图的定义 定义 15.1 （1）欧拉通路——经过图中每条边一次且仅一次行遍所有顶点的 通路. （2）欧拉回路——经过图中每条边一次且仅一次行遍所有顶点的 回路. （3）欧拉图——具有欧拉回路的图. （4）半欧拉图——具有欧拉通路而无欧拉回路的图. 几点说明： 规定平凡图为欧拉图. 欧拉通路是生成的简单通路，欧拉回路是生成的简单回路. 环不影响图的欧拉性.
例 设 G 是欧拉图，但 G 不是平凡图，也不是一个环，则(G)2. 证 只需证明 G 中不可能有桥（如何证明？）
（1）
（2）
图4 图 4 中， （1） ， （2）两图都是欧拉图，均从 A 点出发，如何一次 成功地走出一条欧拉回路来？
4．Fleury 算法 Fleury 算法： (1) 任取 v0V(G)，令 P0=v0. (2) 设 Pi = v0e1v1e2…eivi 已经行遍，按下面方法来从 E(G){e1,e2,…,ei}中选取 ei+1： (a) ei+1 与 vi 相关联； (b) 除非无别的边可供行遍，否则 ei+1 不应该为 Gi = G{e1,e2,…,ei}中的桥. (3) 当 (2)不能再进行时，算法停止. 可以证明，当算法停止时所得简单通路 Pm = v0e1v1e2…emvm（vm=v0）为 G 中一条欧拉回路. 用 Fleury 算法走出图 4 中(1)，(2)从 A 出发（其实从任何一点 出发都可以）的欧拉回路各一条.
3．无向哈密顿图的一个充分条件 定理 15.7 设 G 是 n 阶无向简单图，若对于任意不相邻的顶点 vi,vj，均有 d(vi)+d(vj) n1 () 则 G 中存在哈密顿通路. 证明线索： （1）由()证 G 连通 （2） = v1v2…vl 为 G 中极大路径. 若 l = n, 证毕. （3）否则，证 G 中存在过上所有顶点的圈 C，由（1）知 C 外顶点存在与 C 上某顶点相邻顶点，从而得比更长的路径， 重复（2）--（3） ，最后得 G 中哈密顿通路.
证（着重关键步骤） （1）由()及简单图的性质，用反证法证明 G 连通. （2） = v1v2…vl 为极大路径，l n, 若 l = n（结束）. 下面讨论 l<n 的情况，即要证 G 中存在过 上 所有顶点的圈. ① 若(v1,vl)在 G 中，则 (u,v)为 G 中圈
② 否则，设 v1 与上 v i1 v 2 , v i2 ,..., vik 相邻，则 k2（否则由极大路径端 点的性质及()， 会得到 d(v1)+d(vl)1+l2<n1） ， 又 vl 至少与 v i2 , v i3 ,...v ik 左边相邻顶点之一相邻 （写出理由） ， 设 v ir 1 与 vl 相邻， 见图 7 中 （1） ， 于是得 G 中回路 C（ （1）中图去掉边( v ir 1 , vir )）
（1）
（2 ）
图 10 令 V 1 ={a, b, c, d}, 则 p(GV 1 ) = 6 >4，由定理 15.6 可知图中无哈密顿回路. 在国际象棋盘上跳马有解，试试看.
Hamilton图的一个应用(习题8.2#6)
• 7位客人入席,A 只会讲英语,B 会讲英, 汉语,C 会讲英,意大利,俄语,D 会讲日, 汉语,E 会讲德,意大利语,F 会讲法,日, 俄语,G 会讲法,德语.能否安排圆桌席 位使每位客人与其左右邻不用翻译便 可交谈?
本定理的条件是哈密顿图的必要条件，但不是充分条件。可以验证 彼得松图（图 14.3 中（1）所示）满足定理中的条件，但它不是哈密顿图。 当然，若一个图不满足定理中的条件，它一定不是哈密顿图。
推论 设无向图 G=<V,E>是半哈密顿图，对于任意的 V1V 且 V1均有 p(GV1) |V1|+1 证 令uv 为 G 中哈密顿通路，令 G = G(u,v)，则 G为哈密顿图. 于是 p(GV1) = p(GV1(u,v)) |V1|+1
几点说明： 定理 15.7 是半哈密顿图的充分条件，但不是必要条件. 长度为 n1（n4）的路径构成的图不满足（）条件， 但它显然是半哈密顿图. 定理 15.7 的推论同样不是哈密顿图的必要条件，G 为 长为 n 的圈，不满足（）条件，但它当然是哈密顿 图. 由定理 15.7 的推论可知，Kn（n3）均为哈密顿图.
• 建立无向图模型:结点为客人;会共同语 言的2结点相邻接.则问题归结为求此图 的一条Hamilton回路.不难验证,此图有 一条Hamilton回路是: (A,B,D,F,G,E,C,A).
A
按此回路安排席位 可满足要求. 思考问题:此图有Euler 回路或路径吗?若有,能 否用来解决此问题?
B
几点说明 定理 15.6 中的条件是哈密顿图的必要条件，但不是 充分条件（彼得松图） 由定理 15.6 立刻可知， Kr,s 当 sr+1 时不是哈密顿图. 易知 Kr,r（r2）时都是哈密顿图，Kr,r+1 都是半哈密 顿图. 常利用定理 15.6 判断某些图不是哈密顿图. 例 设 G 为 n 阶无向连通简单图，若 G 中有割点或桥， 则 G 不是哈密顿图. 证 设 v 为割点，则 p(Gv) 2>|{v}|=1. K2 有桥，它显然不是哈密顿图. 除 K2 外，其他有桥 的图（连通的）均有割点. 其实，本例对非简单连通图也对.
第二节 哈密顿图
历史背景：哈密顿周游世界问题与哈密顿图.
（1） 图5
（2）
一、哈密顿图与半哈密顿图 1. 定义 定义 15.2 （1）哈密顿通路——经过图中所有顶点一次仅一次的通路. （2）哈密顿回路——经过图中所有顶点一次仅一次的回路. （3）哈密顿图——具有哈密顿回路的图. （4）半哈密顿图——具有哈密顿通路且无哈密顿回路的图. 几点说明： 平凡图是哈密顿图. 哈密顿通路是初级通路，哈密顿回路是初级回路. 环与平行边不影响哈密顿性. 哈密顿图的实质是能将图中的所有顶点排在同一个圈上
4．n（n2）阶竞赛图中存在哈密顿通路 定理 15.9 若 D 为 n（n2）阶竞赛图，则 D 中具有哈密顿通路 证明思路：注意，竞赛图的基图是无向完全图. 对 n（n2）做 归纳. 只需观察图 8 中两个图.
（1） 图8
（2）
二、判断某图是否为哈密顿图至今还是一个难题. 下面总结判断某图是哈密顿图或不是哈密顿图的一些可行的方法. 1． 观察出哈密顿回路. 例 图 9 中（周游世界问题）是哈密顿图，易知 a b c d e f g h i j k l m n p q r s t a 为图中的一条哈密顿回路.
（1）
（2） 图6
（3）
（4）
在图 6 中， （1） ， （2）是哈密顿图， （3）是半哈密顿图， （4）既不是哈密顿图，也不是半哈密顿图，为什么？
2．无向哈密顿图的一个必要条件 定理 15.6 设无向图 G=<V,E>是哈密顿图，对于任意 V1V 且 V1，均有 p(GV1) |V1| 证 设 C 为 G 中任意一条哈密顿回路， 易知， 当 V1 中顶点在 C 上均不 相邻时，p(C-V1)达到最大值|V1|，而当 V1 中顶点在 C 上有彼此相邻的情况时， 均有 p(C-V1)<|V1|，所以有 p(C-V1)≤|V1|. 而 C 是 G 的生成子图，所以，有 p(G-V1)≤p(C-V1)≤|V1|。
（a）制造满足归纳假设的若干个小欧拉图 . 由连通及无 奇度数顶点可知，(G)2，用扩大路径法可得 G 中 长度3 的圈 C1. 删除 C1 上所有的边（不破坏 G 中 顶点度数的奇偶性）得 G，则 G无奇度顶点，设它 有 s（s1）个连通分支 G1, G2, …, Gs, 它们的边数 均k，因而它们都是小欧拉图. 设 C1, C2, …, Cs是 G1, G2, …, Gs的欧拉回路. （b）将 C1 上被删除的边还原，从 C1 上某一顶点出发走 出 G 的一条欧拉回路 C.
（ 4）
2. 无向欧拉图的判别法 定理 15.1 无向图 G 是欧拉图当且仅当 G 连通且无奇度数顶点. 证 若 G 为平凡图无问题. 下设 G 为 n 阶 m 条边的无向图. 必要性 设 C 为 G 中一条欧拉回路. （1）G 连通显然. （2）viV(G)，vi 在 C 上每出现一次获 2 度，所以 vi 为偶 度顶点. 由 vi 的任意性，结论为真. 充分性 对边数 m 做归纳法（第二数学归纳法）. （1）m=1 时，G 为一个环，则 G 为欧拉图. （2）设 mk（k1）时结论为真，m=k+1 时如下证明：
eE ( G ')
W (e) 为 G的权，并记作 W(G)，即
W (G ' )
eE ( G ')
（1）
（2）
图7
（3）由连通性，可得比更长的路径（见图 7 中（2）所示） ，对它 再扩大路径，重复（2） ，最后得哈密顿通路. 推论 设 G 为 n（n3）阶无向简单图，若对于 G 中任意两个不相 邻的顶点 vi,vj，均有 d(vi)+d(vj) n （） 则 G 中存在哈密顿回路，从而 G 为哈密顿图. 证明线索：由定理 15.7 得 = v1v2…vn 为 G 中哈密顿通路 . 若 (v1,vn)E(G)，得证. 否则利用（）证明存在过 v1, v2, …, vn 的圈（哈密顿回路）. 定理 15.8 设 u,v 为 n 阶无向简单图 G 中两个不相邻的顶点，且 d(u)+d(v)n，则 G 为哈密顿图当且仅当 G(u,v)为哈密顿图.
从以上证明不难看出：欧拉图是若干个边不重的圈之并，见示意图 3.
图3
PLAY
3．有向欧拉图的判别法 定理 15.3 有向图 D 是欧拉图当且仅当 D 是强连通的且每个顶点的 入度都等于出度. 本定理的证明类似于定理 15.1. 定理 15.4 有向图 D 是半欧拉图当且仅当 D 是单向连通的，且 D 中 恰有两个奇度顶点，其中一个的入度比出度大 1，另一个的出度 比入度大 1，而其余顶点的入度都等于出度. 本定理的证明类似于定理 15.1. 定理 15.5 G 是非平凡的欧拉图当且仅当 G 是连通的且为若干个边不 重的圈之并. 可用归纳法证定理 15.5.
图9 注意，此图不满足定理 15.7 推论的条件.
2．满足定理 15.7 推论的条件（）. 完全图 Kn（n3）中任何两个顶点 u,v，均有 d(u)+d(v) = 2(n1) n（n3） ， 所以 Kn 为哈密顿图. 3．破坏定理 15.6 的条件的图不是哈密顿图. 例 在四分之一国际象棋盘（44 方格组成）上跳马无解. 在国际象棋盘上跳马有解.