第17讲 欧拉图 北京大学计算机系离散数学讲义(ppt版).pptVIP

《集合论与图论》第17讲 第17讲 欧拉图 1. 七桥问题,一笔画,欧拉通(回)路,欧拉图 2. 判定欧拉图的充分必要条件 3. 求欧拉回路的算法 4. 中国邮递员问题 七桥问题 七桥问题(Seven bridges of K?nigsberg problem): River Pregel, Kaliningrad, Russia Leonhard Euler Leonhard Euler(1707~1783): 人类有史以来最多产的数学家. 1736年,“七桥问题”,图论和拓扑学诞生 一笔画 欧拉图(Eulerian) 欧拉通路(Euler trail): 经过图中所有边的简单通路 欧拉回路(Euler tour/circuit): 经过图中所有边的简单回路 欧拉图(Eulerian): 有欧拉回路的图 半欧拉图(semi-Eulerian): 有欧拉通路的图 无向欧拉图的充分必要条件 定理1: 设G是无向连通图,则 (1) G是欧拉图 ? (2) G中所有顶点都是偶数度 ? (3) G是若干个边不交的圈的并 证明: (1)?(2)?(3)?(1). (1)?(2): 若欧拉回路总共k次经过顶点v,则d(v)=2k. 定理1((2)?(3)) (2) G中所有顶点都是偶数度 (3) G是若干个边不交的圈的并 证明: (2)?(3): 若删除任意1个圈上的边,则所有顶点的度还是偶数, 但是不一定连通了. 对每个连通分支重复进行. 定理1((3)?(1)) (1) G是欧拉图 (3) G是若干个边不交的圈的并 证明: (3)?(1): 有公共点但边不交的简单回路, 总可以拼接成欧拉回路: 在交点处,走完第1个回路后再走第2个回路. # 用归纳法严格证明 无向半欧拉图的充分必要条件 定理2: 设G是无向连通图,则 (1) G是半欧拉图 ? (2) G中恰有2个奇度顶点 证明: (1)?(2): 欧拉通路的起点和终点是奇数度,其余顶点都是偶数度. (2)?(1): 在两个奇数度顶点之间加1条新边,所有顶点都是偶数度,得到欧拉回路.从欧拉回路上删除所加边后,得到欧拉通路. # 有向欧拉图的充分必要条件 定理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类似. # 有向半欧拉图的充分必要条件 定理4: 设G是无向连通图,则 (1) G是半欧拉图 ? (2) G中恰有2个奇度顶点, 其中1个入度比出度大1,另1个出度比入度大1, 其余顶点入度等于出度. # 例 算法(algorithm) 一组有限条指令, 具有以下特征: 输入: 算法工作对象 输出: 算法工作结果 确定性: 算法根据输入和当前工作状态, 决定下一步采用的指令 可行性: 算法的指令都是可以实现的 终止性: 算法工作有穷步后停止 Fleury算法 输入: 连通图G,起点v,终点w. 若v?w, 则除v,w外的顶点都有偶数度;若v=w, 则所有顶点都有偶数度. 输出: 从v到w的欧拉通路/欧拉回路. 算法: (下一页) Fleury算法(递归形式) 算法: (1) if d(v)1 then e:=v关联的任意非割边 (2) else e:=v关联的唯一边 (3) u:=e的另一个端点. (4) 递归地求G-e的从u到w的欧拉通路 (5) 把e接续在递归地求出的通路上 Fleury算法(迭代形式) 算法: (1) P0:=v; (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); 否则算法停止 Fleury算法(举例) Fleury算法(正确性证明) 定理5: 设G是无向欧拉图,则Fleury算法终止时得到的简单通路是欧拉回路 证明: (1) Pm是回路: 显然. (2) Pm经过G中所有边: (反证)否则, G-Pm的连通分支还是欧拉回路, 并且与Pm相交. 若v0是交点,则算法不应结束; 若v0不是交点,则算法在最后离开交点回到v0时走了桥; 这都是矛盾! # 逐步插入回路算法 (0) i:=0, v*:=v,v:=v1,P0=v1, G0=G. (1) e:=在Gi中与v关联的