第17讲--欧拉图-北京大学计算机系离散数学讲义ppt课件.ppt

《第17讲--欧拉图-北京大学计算机系离散数学讲义ppt课件.ppt》由会员分享，可在线阅读，更多相关《第17讲--欧拉图-北京大学计算机系离散数学讲义ppt课件.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第17 讲 欧拉图1.七桥问题,一笔画,欧拉通(回)路,欧拉图2.判定欧拉图的充分必要条件3.求欧拉回路的算法4.中国邮递员问题2023/5/4 1 集合论与图论第17 讲在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确2023/5/4 2 集合论与图论第17 讲在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确2023/5/4 3 集合论与图论第17 讲在整堂课的教学中

2、，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确一笔画2023/5/4 4 集合论与图论第17 讲在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确欧拉图(Eulerian)欧拉通路(Euler trail):经过图中所有边的简单通路 欧拉回路(Euler tour/circuit):经过图中所有边的简单回路 欧拉图(Eulerian):有欧拉回路的图 半欧拉图(semi-Eulerian):有欧拉通路的图2023/5/4 5 集合论与图论第17 讲在整堂课的教学中，刘教师总是让学生带着问题来

3、学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确无向欧拉图的充分必要条件 定理1:设G 是无向连通图,则(1)G 是欧拉图(2)G 中所有顶点都是偶数度(3)G 是若干个边不交的圈的并 证明:(1)(2)(3)(1).(1)(2):若欧拉回路总共k次经过顶点v,则d(v)=2k.2023/5/4 6 集合论与图论第17 讲在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确定理1(2)(3)(2)G 中所有顶点都是偶数度(3)G 是若干个边不交的圈的并 证明:(2)(3):若删除任意1 个圈上的边,则所有顶点的度还是偶数,

4、但是不一定连通了.对每个连通分支重复进行.2023/5/4 7 集合论与图论第17 讲在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确定理1(3)(1)(1)G 是欧拉图(3)G 是若干个边不交的圈的并 证明:(3)(1):有公共点但边不交的简单回路,总可以拼接成欧拉回路:在交点处,走完第1 个回路后再走第2 个回路.#用归纳法严格证明2023/5/4 8 集合论与图论第17 讲在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确无向半欧拉图的充分必要条件 定理2:设G 是无向连

5、通图,则(1)G 是半欧拉图(2)G 中恰有2 个奇度顶点 证明:(1)(2):欧拉通路的起点和终点是奇数度,其余顶点都是偶数度.(2)(1):在两个奇数度顶点之间加1 条新边,所有顶点都是偶数度,得到欧拉回路.从欧拉回路上删除所加边后,得到欧拉通路.#2023/5/4 9 集合论与图论第17 讲在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确有向欧拉图的充分必要条件 定理3:设G 是有向连通图,则(1)G 是欧拉图(2)vV(G),d+(v)=d-(v)(3)G 是若干个边不交的有向圈的并 证明:(1)(2)(3)(1).(1)(2

6、):若欧拉回路总共k次经过顶点v,则d+(v)=d-(v)=k.其余与定理1 类似.#2023/5/4 10 集合论与图论第17 讲在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确有向半欧拉图的充分必要条件 定理4:设G 是无向连通图,则(1)G 是半欧拉图(2)G 中恰有2 个奇度顶点,其中1 个入度比出度大1,另1 个出度比入度大1,其余顶点入度等于出度.#2023/5/4 11 集合论与图论第17 讲在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确例2023/5/4 1

7、2 集合论与图论第17 讲在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确算法(algorithm)一组有限条指令,具有以下特征:输入:算法工作对象 输出:算法工作结果 确定性:算法根据输入和当前工作状态,决定下一步采用的指令 可行性:算法的指令都是可以实现的 终止性:算法工作有穷步后停止输入 输出指令组 工作区2023/5/4 13 集合论与图论第17 讲在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确Fleury 算法 输入:连通图G,起点v,终点w.若vw,则除v,w

8、外的顶点都有偶数度;若v=w,则所有顶点都有偶数度.输出:从v到w 的欧拉通路/欧拉回路.算法:(下一页)2023/5/4 14 集合论与图论第17 讲在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确Fleury 算法(递归形式)算法:(1)if d(v)1 then e:=v 关联的任意非割边(2)else e:=v 关联的唯一边(3)u:=e 的另一个端点.(4)递归地求G-e 的从u 到w 的欧拉通路(5)把e 接续在递归地求出的通路上2023/5/4 15 集合论与图论第17 讲在整堂课的教学中，刘教师总是让学生带着问题来学习

9、，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确Fleury 算法(迭代形式)算法:(1)P0:=v;(2)设Pi=v0e1v1e2eivi已经行遍,设Gi=G-e1,e2,ei,ei+1:=Gi中满足如下2 条件的边:(a)ei+1与vi关联(b)除非别无选择,否则ei+1不是Gi中的桥(3)若GiNi,则回到(2);否则算法停止2023/5/4 16 集合论与图论第17 讲在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确Fleury 算法(举例)2023/5/4 17 集合论与图论第17 讲在整堂课的教学中，刘教师总是

10、让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确Fleury 算法(正确性证明)定理5:设G 是无向欧拉图,则Fleury 算法终止时得到的简单通路是欧拉回路 证明:(1)Pm是回路:显然.(2)Pm经过G 中所有边:(反证)否则,G-Pm的连通分支还是欧拉回路,并且与Pm相交.若v0是交点,则算法不应结束;若v0不是交点,则算法在最后离开交点回到v0时走了桥;这都是矛盾!#2023/5/4 18 集合论与图论第17 讲在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确逐步插入回路算法(0)i:=0,v*

11、:=v,v:=v1,P0=v1,G0=G.(1)e:=在Gi中与v关联的任意边(v,v),Pi+1:=“Pi”ev.(2)if v v*then i:=i+1,v=v,goto(1).(3)if E(Pi+1)=E(G)then 结束 else Gi+1:=G-E(Pi+1),e:=Gi+1中与Pi+1上vk关联的任意边,Pi+1:=vkvk.v*:=vk,v:=vk,i:=i+1,goto(1).2023/5/4 19 集合论与图论第17 讲在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确逐步插入回路算法(举例)2023/5/4 2

12、0 集合论与图论第17 讲在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确应用(轮盘设计)10110110000,001,010,011,100,101,110,111abcca2023/5/4 21 集合论与图论第17 讲在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确应用(轮盘设计)D=,V=00,01,10,11,E=abc=|a,b,c 0,1 00110110000001100010101011110111001101101102023/5/4 22 集合论与图论第

13、17 讲在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确中国邮递员问题 中国邮递员问题(Chinese postman problem):求邮递员走遍管区所有街道的最短回路 管梅谷(Guan Mei-gu),1962,中国 运筹学(Operation Research)组合优化(Combinatorial Optimization)2023/5/4 23 集合论与图论第17 讲在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确带权图(weighted graph)带权图(wei

14、ghted graph):G=,W:E R,W(e)称为e 的权ABF ECD510938 14456ABF ECD510938 14456132023/5/4 24 集合论与图论第17 讲在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确中国邮递员问题(解法)解法:(1)求带权图G 所有奇数顶点之间的短程线(2)用所有奇数顶点和短程线得完全图K(3)求K 的最小完美匹配M(4)用M 给G 沿短程线加重复边得G*(4)求G*的欧拉回路2023/5/4 25 集合论与图论第17 讲在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的

15、设置具有一定的梯度，由浅入深，所提出的问题也很明确中国邮递员问题(举例)1 6 5 3A B C D EI H G F2 1 1 22 4 25 5B DH G42871 6 5 3A B C D EI H G F2 1 1 22 4 2最优路线:ABCDEFGHBCDGHIA,W(G*)=35GG*K2023/5/4 26 集合论与图论第17 讲在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确总结 七桥问题,一笔画,欧拉通(回)路,欧拉图 判定欧拉图的充分必要条件 求欧拉回路的算法 中国邮递员问题2023/5/4 27 集合论与图论第17 讲在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确作业(#13)p234,习题八,2,3,4(更正:G-v0)2023/5/4 28 集合论与图论第17 讲