第8章 欧拉图与哈密顿图.ppt

《第8章 欧拉图与哈密顿图.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第8章欧拉图与哈密顿图8.1欧拉图具有经过所有边的简单生成回路的图8.2哈密顿图具有生成圈的图1©PekingUniversity七桥问题哥尼斯堡域普雷格尔河2©PekingUniversityLeonhardEulerLeonhardEuler(1707~1783):人类有史以来最多产的数学家.1736年,“七桥问题”,图论和拓扑学诞生ADcdabfCgBe3©PekingUniversity一笔画4©PekingUniversity欧拉通路(Eulertrail)欧拉通路:经过图中所有边一次,且仅一次行

2、遍所有顶点的通路欧拉通路是经过所有边的简单通路并且是生成通路(经过所有顶点)5©PekingUniversity欧拉回路(Eulertour/circuit)欧拉回路(Eulertour/circuit):经过图中所有边一次,且仅一次行遍所有顶点的回路欧拉回路是经过所有边的简单生成回路6©PekingUniversity欧拉图(Eulerian):有欧拉回路的图半欧拉图(semi-Eulerian):有欧拉通路但无欧拉回路的图规定：平凡图为欧拉图7©PekingUniversity无向欧拉图的充分必要条件定

3、理8.1:设G是无向连通图,则(1)G是欧拉图(2)G中所有顶点都是偶数度(3)G是若干个边不交的圈的并8©PekingUniversity定理8.1(1)(2)(1)G是欧拉图(2)G中所有顶点都是偶数度证明:若G是平凡图,结论成立;G是非平凡图,因为G是欧拉图，所以存在欧拉回路,设C为G中一条欧拉回路,C=vi0e1vi1e2vi2…em-1vim-1emvi0任意v,在C中出现一次就获2度,若总共k次经过顶点v,则d(v)=2k.9©PekingUniversity定理8.1(2)(3)(2

4、)G中所有顶点都是偶数度(3)G是若干个边不重的圈的并证明:(2)(3):若删除任意1个圈上的边,则所有顶点的度还是偶数,但是不一定连通了.对每个连通分支重复进行.10©PekingUniversity定理8.1(3)(1)(3)G是若干个边不交的圈的并(1)G是欧拉图证明:(3)(1):有公共点但边不交的简单回路,总可以拼接成欧拉回路:在交点处,走完第1个回路后再走第2个回路.#用归纳法严格证明11©PekingUniversity例Adbfge12©PekingUniversity无向半欧拉图的充

5、分必要条件定理8.2:设G是无向连通图,则(1)G是半欧拉图(2)G中恰有2个奇度顶点13©PekingUniversity定理8.2证明G是半欧拉图G中恰有2个奇度顶点证明::设G为半欧拉图,存在欧拉通路C=vi0e1vi1e2vi2…em-1vim-1emvim欧拉通路的起点和终点是奇数度,其余顶点都是偶数度.:在两个奇数度顶点之间加1条新边,所有顶点都是偶数度,得到欧拉回路.从欧拉回路上删除所加边后,得到欧拉通路.#14©PekingUniversity有向欧拉图的充分必要条件定理8.3:设G

6、是有向连通图,则(1)G是欧拉图(2)vV(G),d+(v)=d-(v)(3)G是若干个边不重的有向圈的并15©PekingUniversity定理8.3定理8.3:设G是有向连通图,则(1)G是欧拉图(2)vV(G),d+(v)=d-(v)(3)G是若干个边不交的有向圈的并证明:(1)(2)(3)(1).(1)(2):若欧拉回路总共k次经过顶点v,则d+(v)=d-(v)=k.其余与定理1类似.#16©PekingUniversity有向半欧拉图的充分必要条件定理8.4:设G是无向

7、连通图,则(1)G是半欧拉图(2)G中恰有2个奇度顶点,其中1个入度比出度大1,另1个出度比入度大1,其余顶点入度等于出度.#17©PekingUniversity例求欧拉通/回路？18©PekingUniversityFleury算法(避桥法)输入:无向图G.输出:欧拉通路/欧拉回路.算法:从任意一点开始,沿着没有走过的边向前走在每个顶点,优先选择剩下的非桥边,除非只有唯一一条边直到得到欧拉回路或宣布失败19©PekingUniversityFleury算法(举例)20©PekingUniversity

8、Fleury算法(迭代形式)算法:(1)P0:=v0;(2)设Pi=v0e1v1e2…eivi已经行遍,设Gi=G-{e1,e2,…,ei},ei+1:=Gi中满足如下2条件的边:(a)ei+1与vi关联(b)除非别无选择,否则ei+1不是Gi中的桥(3)若GiNi,则回到(2);否则算法停止21©PekingUniversityFleury算法(递归形式)算法:(1)ifd(v)>1thene:=v关联的任意