《集合论与图论》第17讲1 第17讲欧拉图 ?1. 七桥问题,一笔画,欧拉通(回)路,欧拉图 ?2. 判定欧拉图的充分必要条件 ?3. 求欧拉回路的算法 ?4. 中国邮递员问题 《集合论与图论》第17讲2 七桥问题 ?七桥问题(Seven bridges of K?nigsberg problem): River Pregel, Kaliningrad, Russia 《集合论与图论》第17讲3 Leonhard Euler ?Leonhard Euler(1707~1783): ?人类有史以来最多产的数学家. ?1736年,“七桥问题”,图论和拓扑学诞生 AD c d a b f C g B e 《集合论与图论》第17讲4 一笔画 《集合论与图论》第17讲5 欧拉图(Eulerian) ?欧拉通路(Euler trail): 经过图中所有边的 简单通路 ?欧拉回路(Euler tour/circuit): 经过图中所 有边的简单回路 ?欧拉图(Eulerian): 有欧拉回路的图 ?半欧拉图(semi-Eulerian): 有欧拉通路的 图 《集合论与图论》第17讲6 无向欧拉图的充分必要条件 ?定理1: 设G是无向连通图,则 (1) G是欧拉图 ? (2) G中所有顶点都是偶数度 ? (3) G是若干个边不交的圈的并 ?证明: (1)?(2)?(3)?(1). (1)?(2): 若欧拉回路总共k次经过顶点v,则 d(v)=2k. 《集合论与图论》第17讲7 定理1((2)?(3)) (2) G中所有顶点都是偶数度 (3) G是若干个边不交的圈的并 ?证明: (2)?(3): 若删除任意1个圈上的边, 则所有顶点的度还是偶数, 但是不一定连 通了. 对每个连通分支重复进行. 《集合论与图论》第17讲8 定理1((3)?(1)) (1) G是欧拉图 (3) G是若干个边不交的圈的并 ?证明: (3)?(1): 有公共点但边不交的简单 回路, 总可以拼接成欧拉回路: 在交点处, 走完第1个回路后再走第2个回路. # ?用归纳法严格证明 《集合论与图论》第17讲9 无向半欧拉图的充分必要条件 ?定理2: 设G是无向连通图,则 (1) G是半欧拉图 ? (2) G中恰有2个奇度顶点 ?证明: (1)?(2): 欧拉通路的起点和终点是 奇数度,其余顶点都是偶数度. (2)?(1): 在两个奇数度顶点之间加1条新边, 所有顶点都是偶数度,得到欧拉回路.从欧 拉回路上删除所加边后,得到欧拉通路. # 《集合论与图论》第17讲10 有向欧拉图的充分必要条件 ?定理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类似. # 《集合论与图论》第17讲11 有向半欧拉图的充分必要条件 ?定理4: 设G是无向连通图,则 (1) G是半欧拉图 ? (2) G中恰有2个奇度顶点, 其中1个入度 比出度大1,另1个出度比入度大1, 其余顶 点入度等于出度. # 《集合论与图论》第17讲12 例 《集合论与图论》第17讲13 算法(algorithm) ?一组有限条指令, 具有以下特征: ?输入: 算法工作对象 ?输出: 算法工作结果 ?确定性: 算法根据输入和当前工作状态, 决定 下一步采用的指令 ?可行性: 算法的指令都是可以实现的 ?终止性: 算法工作有穷步后停止 输入输出 指令组工作区 《集合论与图论》第17讲14 Fleury算法 ?输入: 连通图G,起点v,终点w. 若v≠w, 则 除v,w外的顶点都有偶数度;若v=w, 则所 有顶点都有偶数度. ?输出: 从v到w的欧拉通路/欧拉回路. ?算法: (下一页) 《集合论与图论》第17讲15 Fleury算法(递归形式) ?算法: (1) if d(v)>1 then e:=v关联的任意非割边 (2) else e:=v关联的唯一边 (3) u:=e的另一个端点. (4) 递归地求G-e的从u到w的欧拉通路 (5) 把e接续在递归地求出的通路上 《集合论与图论》第17讲16 Fleury算法(迭代形式) ?算法: (1) P 0 :=v; (2) 设P i =v 0 e 1 v 1 e 2 …e i v i 已经行遍,设G i =G- {e 1 ,e 2 ,… ,e i }, e i+1 := G i 中满足如下2条件的边: (a) e i+1 与v i 关联 (b) 除非别无选择,否则e i+1 不是G i 中的桥 (3) 若G i ≠N i , 则回到(2); 否则算法停止 《集合论与图论》第17讲17 Fleury算法(举例) 《集合论与图论》第17讲18 Fleury算法(正确性证明) ?定理5: 设G是无向欧拉图,则Fleury算法 终止时得到的简单通路是欧拉回路 ?证明: (1) P m 是回路: 显然. (2) P m 经过G中所有边: (反证)否则, G-P m 的连通分支还是欧拉回路, 并且与 P m 相交. 若v 0 是交点,则算法不应结束; 若 v 0 不是交点,则算法在最后离开交点回到 v 0 时走了桥; 这都是矛盾! # 《集合论与图论》第17讲19 逐步插入回路算法 (0) i:=0, v*:=v,v:=v 1 ,P 0 =v 1 , G 0 =G. (1) e:=在G i 中与v关联的任意边(v,v’), P i+1 :=“P i ”ev’. (2) if v’≠v* then i:=i+1, v=v’, goto (1). (3) if E(P i+1 )=E(G) then结束 else G i+1 :=G-E(P i+1 ), e:=G i+1 中与P i+1 上v k 关联的任意边, P i+1 := v k …v k . v*:=v k ,v:=v k , i:=i+1, goto (1). 《集合论与图论》第17讲20 逐步插入回路算法(举例) 《集合论与图论》第17讲21 应用(轮盘设计) 1 0 1 1 0 1 1 0 ?000,001,010,011,100,101,110,111 a b c c a 《集合论与图论》第17讲22 应用(轮盘设计) ?D=<V,E>, V={00,01,10,11}, E={ abc=<ab,bc> | a,b,c∈{0,1} } 00 11 01 10 000 001 100 010 101 011 110 111 0 0 1 1 0 1 1 0 1 1 0 《集合论与图论》第17讲23 中国邮递员问题 ?中国邮递员问题(Chinese postman problem): 求邮递员走遍管区所有街道的 最短回路 ?管梅谷(Guan Mei-gu),1962,中国 ?运筹学(Operation Research) ?组合优化(Combinatorial Optimization) 《集合论与图论》第17讲24 带权图(weighted graph) ?带权图(weighted graph): G=<V,E,W>, W:E→R, W(e)称为e的权 A B FE C D 5 10 9 3 814 4 5 6 A B FE C D 5 10 9 3 814 4 5 6 13 《集合论与图论》第17讲25 中国邮递员问题(解法) ?解法: (1) 求带权图G所有奇数顶点之间的短程线 (2) 用所有奇数顶点和短程线得完全图K (3) 求K的最小完美匹配M (4) 用M给G沿短程线加重复边得G* (4) 求G*的欧拉回路 《集合论与图论》第17讲26 中国邮递员问题(举例) 1 6 5 3 A BCDE IH GF 2 112 242 5 5 BD HG 4 2 8 7 1 6 5 3 A BCDE IH GF 2 112 242 最优路线: ABCDEFGHBCDGHIA, W(G*)=35 G G* K 《集合论与图论》第17讲27 总结 ?七桥问题,一笔画,欧拉通(回)路,欧拉图 ?判定欧拉图的充分必要条件 ?求欧拉回路的算法 ?中国邮递员问题 《集合论与图论》第17讲28 作业(#13) ? p234, 习题八, 2,3,4(更正: G-v 0 )