Presentation is loading. Please wait.

Presentation is loading. Please wait.

第十五章 欧拉图与哈密顿图 主要内容 欧拉图 哈密顿图 带权图与货郎担问题.

Similar presentations


Presentation on theme: "第十五章 欧拉图与哈密顿图 主要内容 欧拉图 哈密顿图 带权图与货郎担问题."— Presentation transcript:

1 第十五章 欧拉图与哈密顿图 主要内容 欧拉图 哈密顿图 带权图与货郎担问题

2 15.1 欧拉图 历史背景:哥尼斯堡七桥问题与欧拉图

3 欧拉图定义 定义15.1 (1) 欧拉通路——经过图中每条边一次且仅一次行遍所有顶点的通路.
(2) 欧拉回路——经过图中每条边一次且仅一次行遍所有顶点的回路. (3) 欧拉图——具有欧拉回路的图. (4) 半欧拉图——具有欧拉通路而无欧拉回路的图. 几点说明: 规定平凡图为欧拉图. 欧拉通路是生成的简单通路,欧拉回路是生成的简单回路. 环不影响图的欧拉性.

4 欧拉图实例 上图中,(1) ,(4) 为欧拉图,(2),(5)为半欧拉图,(3),(6)既不是欧拉图,也不是半欧拉图. 在(3),(6)中各至少加几条边才能成为欧拉图?

5 无向欧拉图的判别法 定理15.1 无向图G是欧拉图当且仅当G连通且无奇度数顶点.
证 若G 为平凡图无问题. 下设G为 n 阶 m 条边的无向图. 必要性 设C 为G 中一条欧拉回路. (1) G 连通显然. (2) viV(G),vi在C上每出现一次获2度,所以vi为偶度顶点. 由vi 的任意性,结论为真. 充分性 对边数m做归纳法(第二数学归纳法). (1) m=1时,G为一个环,则G为欧拉图. (2) 设mk(k1)时结论为真,m=k+1时如下证明:

6 从以上证明不难看出:欧拉图是若干个边不重的圈之并,见示意图3.
PLAY

7 欧拉图的判别法 定理15.2 无向图G是半欧拉图当且仅当G 连通且恰有两个奇 度顶点. 证 必要性简单. 充分性(利用定理15.1)
证 必要性简单. 充分性(利用定理15.1) 设u,v为G 中的两个奇度顶点,令 G  =G(u,v) 则G  连通且无奇度顶点,由定理15.1知G 为欧拉图,因而 存在欧拉回路C,令 =C(u,v) 则 为 G 中欧拉通路.

8 有向欧拉图的判别法 定理15.3 有向图D是欧拉图当且仅当D是强连通的且每个顶 点的入度都等于出度. 本定理的证明类似于定理15.1.
的出度比入度大1,而其余顶点的入度都等于出度. 定理15.5 G是非平凡的欧拉图当且仅当G是连通的且为若干 个边不重的圈之并. 可用归纳法证定理15.5.

9 例题 例1 设G是欧拉图,但G不是平凡图,也不是一个环,则 (G)2. 证 只需证明G中不可能有桥(如何证明?) (1) (2)
(1) (2) 上图中,(1),(2)两图都是欧拉图,均从A点出发,如何一次成功地走出一条欧拉回路来?

10 Fleury算法 算法: (1) 任取v0V(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算法走出上一页图(1),(2)从A出发(其实从任何一点 出发都可以)的欧拉回路各一条.

11 15.2 哈密顿图 历史背景:哈密顿周游世界问题与哈密顿图 (1) (2)

12 哈密顿图与半哈密顿图 定义15.2 (1) 哈密顿通路——经过图中所有顶点一次仅一次的通路.
(2) 哈密顿回路——经过图中所有顶点一次仅一次的回路. (3) 哈密顿图——具有哈密顿回路的图. (4) 半哈密顿图——具有哈密顿通路且无哈密顿回路的图. 几点说明: 平凡图是哈密顿图. 哈密顿通路是初级通路,哈密顿回路是初级回路. 环与平行边不影响哈密顿性. 哈密顿图的实质是能将图中的所有顶点排在同一个圈上

13 实例 在上图中, (1),(2) 是哈密顿图; (3)是半哈密顿图; (4)既不是哈密顿图,也不是半哈密顿图,为什么?

14 无向哈密顿图的一个必要条件 定理15.6 设无向图G=<V,E>是哈密顿图,对于任意V1V且
V1,均有 p(GV1)  |V1| 证 设C为G中一条哈密顿回路 (1) p(CV1)  |V1| (2) p(GV1)  p(CV1)  |V1| (因为CG) 推论 设无向图G=<V,E>是半哈密顿图,对于任意的V1V且V1均有 p(GV1)  |V1|+1 证 令 uv为G中哈密顿通路,令G = G(u,v),则G为哈密顿图. 于是 p(GV1) = p(GV1(u,v))  |V1|+1

15 几点说明 定理15.6中的条件是哈密顿图的必要条件,但不是充分条件(彼得松图)
由定理15.6立刻可知,Kr,s当sr+1时不是哈密顿图. 易知Kr,r(r2)时都是哈密顿图,Kr,r+1都是半哈密顿图. 常利用定理15.6判断某些图不是哈密顿图. 例2 设G为n阶无向连通简单图,若G中有割点或桥,则G不 是哈密顿图. 证 设v为割点,则 p(Gv)  2>|{v}|=1. K2有桥,它显然不是哈密顿图. 除K2外,其他有桥的图(连通的)均有割点. 其实,本例对非简单连通图也对.

16 无向哈密顿图的一个充分条件 定理15.7 设G是n阶无向简单图,若对于任意不相邻的顶点vi,vj,均有
d(vi)+d(vj)  n () 则G 中存在哈密顿通路. 证明线索: (1) 由()证G连通 (2)  = v1v2…vl 为G中极大路径. 若l = n, 证毕. (3) 否则,证G 中存在过上所有顶点的圈C,由(1) 知C外顶 点存在与C上某顶点相邻顶点,从而得比更长的路径,重 复(2) –(3) ,最后得G中哈密顿通路.

17 证明 证(着重关键步骤) (1) 由()及简单图的性质,用反证法证明G连通.
(2)  = v1v2…vl 为极大路径,l  n, 若l = n(结束). 下面讨论l<n的情况,即要证G中存在过上所有顶点的圈. ① 若(v1,vl)在G中,则(u,v)为G中圈 ② 否则,设v1与上 相邻,则k2 (否则由极大路径端点性质及(),会得到d(v1)+d(vl)1+l2<n1), 又vl 至少与 左边相邻顶点之一相邻(写出理由),设 与vl相邻,见图中(1) ,于是得G中回路C ((1)中图去掉边( ) )

18 证明 图(1) 图(2) (3) 由连通性,可得比 更长的路径(如图(2) 所示), 对它再扩大路径,重复(2) ,最后得哈密顿通路.

19 推论 推论 设G为n (n3) 阶无向简单图,若对于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)为哈密顿图.

20 几点说明 定理15.7是半哈密顿图的充分条件,但不是必要条件. 长度 为n1(n4)的路径构成的图不满足()条件,但它显
然是半哈密顿图. 定理15.7的推论同样不是哈密顿图的必要条件,G为长为n的 圈,不满足()条件,但它当然是哈密顿图. 由定理15.7的推论可知,Kn(n3)均为哈密顿图.

21 无向哈密顿图的充分条件 n(n2)阶竞赛图中存在哈密顿通路 定理15.9 若D为n(n2)阶竞赛图,则D中具有哈密顿通路
做归纳. 只需观察下面两个图.

22 判断某图是否为哈密顿图方法 判断某图是否为哈密顿图至今还是一个难题. 总结判断某图是哈密顿图或不是哈密顿图的某些可行的方法.
1. 观察出哈密顿回路. 例3 下图(周游世界问题) 是哈密顿图 易知 a b c d e f g h i j k l m n p q r s t a 为图中的一条哈密顿回路. 注意,此图不满足定理15.7 推论条件.

23 判断某图是否为哈密顿图方法 2.满足定理15.7推论的条件(). 例4 完全图Kn (n3) 中任何两个顶点u,v,均有
d(u)+d(v) = 2(n1)  n(n3), 所以Kn为哈密顿图. 3.破坏定理15.6的条件的图不是哈密顿图. 例5 在四分之一国际象棋盘(44方格组成)上跳马无解. 在国际象棋盘上跳马有解.

24 令V1={a, b, c, d}, 则 p(GV1) = 6 >4,由定理15.6可知图中无哈密顿回路.
在国际象棋盘上跳马有解,试试看.

25 15.3 最短路问题与货郎担问题 定义15.3 给定图G = <V,E>,(G为无向图或有向图),设
W:ER (R为实数集),对G中任意边e = (vi,vj) (G为有向图 时,e = <vi,vj>),设W(e) = wij,称实数wij 为边e上的权,并将 wij标注在边e上,称G为带权图,此时常将带权图G记作 <V,E,W>. 设GG,称 为G的权,并记作W(G),即

26 货郎担问题 设G=<V,E,W>为一个n阶完全带权图Kn,各边的权非负,且
是货郎担问题的数学模型. 完全带权图Kn(n3)中不同的哈密顿回路数 (1) Kn中有n! 条不同的哈密顿回路(定义意义下) (2) 完全带权图中有n! 条不同的哈密顿回路 (3) 用穷举法解货郎担问题算法的复杂度为n!,当n较大时,计算量惊人地大

27 例6 求图中(1) 所示带权图K4中最短哈密顿回路.
(1) (2) 解 C1= a b c d a, W(C1)=10 C2= a b d c a, W(C2)=11 C3= a c b d a, W(C3)=9 可见C3 (见图中(2)) 是最短的,其权为9.

28 第十五章 习题课 主要内容 欧拉通路、欧拉回路、欧拉图、半欧拉图及其判别法 哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图 带权图、货郎担问题
基本要求 深刻理解欧拉图、半欧拉图的定义及判别定理 深刻理解哈密顿图、半哈密顿图的定义. 会用哈密顿图的必要条件判断某些图不是哈密顿图. 会用充分条件判断某些图是哈密顿图. 要特别注意的是,不能将必要条件当作充分条件,也不要将充分条件当必要条件.

29 练习1 1. 设G为n(n2)阶无向欧拉图,证明G中无桥(见例1思考题) 方法一:直接证明法.
命题 (*):设C为任意简单回路,e为C上任意一条边,则Ce连通. 证 设C为G中一条欧拉回路,任意的eE(C),可知Ce是Ge的子图,由()知 Ce 连通,所以e不为桥. 方法二:反证法. 利用欧拉图无奇度顶点及握手定理的推论. 否则,设e=(u,v)为G中桥,则Ge产生两个连通分支G1, G2,不妨设u在G1中,v在G2中. 由于从G中删除e时,只改变u,v 的度数(各减1),因而G1与G2中均只含一个奇度顶点,这与握手定理推论矛盾.

30 练习 2 2. 证明下图不是哈密顿图. (破坏必要条件) 方法一. 利用定理15.6,
方法一. 利用定理15.6, 取 V1 = {a, c, e, h, j, l},则 p(GV1) = 7 > |V1| = 6 方法二. G为二部图,互补顶点子集 V1 = {a, c, e, h, j, l}, V2 = {b, d, f, g, i, k, m}, |V1| = 6  7 = |V2|. 方法三. 利用可能出现在哈密顿回路上的边至少有n(n为阶数) 条——这也是哈密顿图的一个必要条件,记为(). 此图中,n = 13,m = 21. 由于h, l, j 均为4度顶点,a, c, e为3 度顶点,且它们关联边互不相同. 而在哈密顿回路上, 每个顶点准确地关联两条边,于是可能用的边至多有21(32+31) = 12. 这达不到()的要求.

31 练习 3 3.某次国际会议8人参加,已知每人至少与其余7人中的4人有共同语言,问服务员能否将他们安排在同一张圆桌就座,使得每个人都与两边的人交谈? 解 图是描述事物之间关系的最好的手段之一. 做无向图G=<V,E>, 其中 V={v| v为与会者}, E={(u,v) | u,vV且u与v有共同语言,且u  v}. 易知G为简单图且vV, d(v)4,于是,u,vV, 有d(u)+d(v)  8,由定理15.7 的推论可知G为哈密顿图. 服务员在G中找一条哈密顿回路C,按C中相邻关系安排座位即可. 由本题想到的:哈密顿回图的实质是能将图中所有的顶点排在同一个圈中.

32 练习 4 4. 距离(公里) 如图所示. 他如何走行程最短? 最短的路为ABCDA,距离为36公里,其余两条各为多少?


Download ppt "第十五章 欧拉图与哈密顿图 主要内容 欧拉图 哈密顿图 带权图与货郎担问题."

Similar presentations


Ads by Google