《第17讲欧拉图 北京大学计算机系离散数学讲义(版)》由会员分享，可在线阅读，更多相关《第17讲欧拉图 北京大学计算机系离散数学讲义(版)（28页珍藏版）》请在装配图网上搜索。
1、第17讲 欧拉图1.七桥问题,一笔画,欧拉通(回)路,欧拉图2.判定欧拉图的充分必要条件3.求欧拉回路的算法4.中国邮递员问题2024/4/151集合论与图论第17讲七桥问题七桥问题(Seven bridges of Knigsberg problem):River Pregel,Kaliningrad,Russia2024/4/152集合论与图论第17讲Leonhard EulerLeonhard Euler(17071783):人类有史以来最多产的数学家.1736年,“七桥问题”,图论和拓扑学诞生ADcdabfCgBe2024/4/153集合论与图论第17讲一笔画2024/4/154集合论
2、与图论第17讲欧拉图(Eulerian)欧拉通路(Euler trail):经过图中所有边的简单通路欧拉回路(Euler tour/circuit):经过图中所有边的简单回路欧拉图(Eulerian):有欧拉回路的图半欧拉图(semi-Eulerian):有欧拉通路的图2024/4/155集合论与图论第17讲无向欧拉图的充分必要条件定理1:设G是无向连通图,则 (1)G是欧拉图 (2)G中所有顶点都是偶数度 (3)G是若干个边不交的圈的并证明:(1)(2)(3)(1).(1)(2):若欧拉回路总共k次经过顶点v,则d(v)=2k.2024/4/156集合论与图论第17讲定理1(2)(3)(2)
3、G中所有顶点都是偶数度(3)G是若干个边不交的圈的并证明:(2)(3):若删除任意1个圈上的边,则所有顶点的度还是偶数,但是不一定连通了.对每个连通分支重复进行.2024/4/157集合论与图论第17讲定理1(3)(1)(1)G是欧拉图(3)G是若干个边不交的圈的并证明:(3)(1):有公共点但边不交的简单回路,总可以拼接成欧拉回路:在交点处,走完第1个回路后再走第2个回路.#用归纳法严格证明2024/4/158集合论与图论第17讲无向半欧拉图的充分必要条件定理2:设G是无向连通图,则 (1)G是半欧拉图 (2)G中恰有2个奇度顶点 证明:(1)(2):欧拉通路的起点和终点是奇数度,其余顶点都
4、是偶数度.(2)(1):在两个奇数度顶点之间加1条新边,所有顶点都是偶数度,得到欧拉回路.从欧拉回路上删除所加边后,得到欧拉通路.#2024/4/159集合论与图论第17讲有向欧拉图的充分必要条件定理3:设G是有向连通图,则 (1)G是欧拉图 (2)vV(G),d+(v)=d-(v)(3)G是若干个边不交的有向圈的并证明:(1)(2)(3)(1).(1)(2):若欧拉回路总共k次经过顶点v,则d+(v)=d-(v)=k.其余与定理1类似.#2024/4/1510集合论与图论第17讲有向半欧拉图的充分必要条件定理4:设G是无向连通图,则 (1)G是半欧拉图 (2)G中恰有2个奇度顶点,其中1个入
5、度比出度大1,另1个出度比入度大1,其余顶点入度等于出度.#2024/4/1511集合论与图论第17讲例2024/4/1512集合论与图论第17讲算法(algorithm)一组有限条指令,具有以下特征:输入:算法工作对象输出:算法工作结果确定性:算法根据输入和当前工作状态,决定下一步采用的指令可行性:算法的指令都是可以实现的终止性:算法工作有穷步后停止输入输出指令组 工作区2024/4/1513集合论与图论第17讲Fleury算法输入:连通图G,起点v,终点w.若vw,则除v,w外的顶点都有偶数度;若v=w,则所有顶点都有偶数度.输出:从v到w的欧拉通路/欧拉回路.算法:(下一页)2024/4
6、/1514集合论与图论第17讲Fleury算法(递归形式)算法:(1)if d(v)1 then e:=v关联的任意非割边(2)else e:=v关联的唯一边(3)u:=e的另一个端点.(4)递归地求G-e的从u到w的欧拉通路(5)把e接续在递归地求出的通路上2024/4/1515集合论与图论第17讲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);否则算法停止2024/4/
7、1516集合论与图论第17讲Fleury算法(举例)2024/4/1517集合论与图论第17讲Fleury算法(正确性证明)定理5:设G是无向欧拉图,则Fleury算法终止时得到的简单通路是欧拉回路证明:(1)Pm是回路:显然.(2)Pm经过G中所有边:(反证)否则,G-Pm的连通分支还是欧拉回路,并且与Pm相交.若v0是交点,则算法不应结束;若v0不是交点,则算法在最后离开交点回到v0时走了桥;这都是矛盾!#2024/4/1518集合论与图论第17讲逐步插入回路算法(0)i:=0,v*:=v,v:=v1,P0=v1,G0=G.(1)e:=在Gi中与v关联的任意边(v,v),Pi+1:=“Pi
8、”ev.(2)if vv*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).2024/4/1519集合论与图论第17讲逐步插入回路算法(举例)2024/4/1520集合论与图论第17讲应用(轮盘设计)10110110000,001,010,011,100,101,110,111abcca2024/4/1521集合论与图论第17讲应用(轮盘设计)D=,V=00,01,10,11,E=
9、abc=|a,b,c0,1 00110110000001100010101011110111001101101102024/4/1522集合论与图论第17讲中国邮递员问题中国邮递员问题(Chinese postman problem):求邮递员走遍管区所有街道的最短回路管梅谷(Guan Mei-gu),1962,中国 运筹学(Operation Research)组合优化(Combinatorial Optimization)2024/4/1523集合论与图论第17讲带权图(weighted graph)带权图(weighted graph):G=,W:ER,W(e)称为e的权ABFECD51
10、0938 14456ABFECD510938 14456132024/4/1524集合论与图论第17讲中国邮递员问题(解法)解法:(1)求带权图G所有奇数顶点之间的短程线(2)用所有奇数顶点和短程线得完全图K(3)求K的最小完美匹配M(4)用M给G沿短程线加重复边得G*(4)求G*的欧拉回路2024/4/1525集合论与图论第17讲中国邮递员问题(举例)1653ABCDEIHGF211224255BDHG42871653ABCDEIHGF2112242最优路线:ABCDEFGHBCDGHIA,W(G*)=35GG*K2024/4/1526集合论与图论第17讲总结七桥问题,一笔画,欧拉通(回)路,欧拉图判定欧拉图的充分必要条件求欧拉回路的算法中国邮递员问题2024/4/1527集合论与图论第17讲作业(#13)p234,习题八,2,3,4(更正:G-v0)2024/4/1528集合论与图论第17讲
第17讲欧拉图 北京大学计算机系离散数学讲义(版)
