四川大学-计算机学院--冯伟森-离散数学(第27讲)

冯伟森Email：[e-mail]2020年2月29日星期六2020/2/29计算机学院2主要内容Euler图及其应用①欧拉道路（回路）的定义②如何判别欧拉图③一个图含有欧拉道路的条件④连通有向图G中含有有向欧拉道路和回路的充要条件⑤Fleury算法⑥Euler图的应用(中国邮递员问题算法)2020/2/29计算机学院3哥尼斯堡七桥问题哥尼斯堡城市有一条横贯全城的普雷格尔(Pregel)河，城的各部分用七座桥联接，每逢假日，城中居民进行环城逛游，这样就产生了一个问题：能不能设计一次“遍游”，使得从某地出发对每座跨河桥只走一次，而在遍历了七桥之后却又能回到原地？Ab2BDCb4b1b3b5b7b62020/2/29计算机学院4Euler图定义13-1.1设G是一个无孤立结点的图，包含G的每条边的简单道路（回路）称为该图的一条欧拉道路（回路）。具有欧拉回路的图称为欧拉图。规定平凡图为欧拉图。显然，每个欧拉图必然是连通图。因此，一条欧拉道路（回路）是经过图中每边一次且仅一次的道路（回路）。为什么？2020/2/29计算机学院5例13-1.1v5v1v2v3v4a)v5v1v2v3v4b)v4v1v2v3c)图a是欧拉图；图b不是欧拉图，但存在欧拉道路；图c不存在欧拉道路。2020/2/29计算机学院6定理13-1.1无向连通图G＝V，E是欧拉图当且仅当G的所有结点的度数都为偶数。证明：“”设G是Euler图，则G必然存在一条包含所有边（也包含所有结点）的回路C，对uV，u必然在C中出现一次（可出现多次），每出现u一次，都关联着G中的两条边，而当u又重复出现时，它又关联着G中的另外的两条边，（为什么？）因而u每出现一次，都将使得结点u的度数增加2度，若u在通路中重复出现j次，则deg(u)＝2j。即u的度数必为偶数。由于在回路C中边不可能重复出现2020/2/29计算机学院7“”设连通图G的结点的度数都是偶数，则G必含有简单回路（可对结点个数进行归纳证明）。设C是一条包含G中边最多的简单回路：⑴若C已经包含G中所有的边，则C就是Euler回路，结论成立。⑵若C不能包含G中所有的边，则删边子图G-E（C）仍然无奇数度结点。由于G是连通的，C中应至少存在一点v，使G-E（C）中有一条包含v的回路C′。（见示意图）Why?2020/2/29计算机学院8这样，就可以构造出一条由C和C′组成的G的回路，其包含的边数比C多，与假设矛盾。因此，C必是Euler回路，结论成立。vCC'2020/2/29计算机学院9证明：“”设G具有一条Euler道路L，则在L中除起点和终点外，其余每个结点都与偶数条边相关联，所以，G中仅有零个（Euler回路）或者两个奇数度结点。“”⑴若G没有奇度数结点，则结论显然成立；⑵若G有两个奇度数结点u和v，则G+uv是Euler图，从而存在Euler回路C。从C中去掉边uv，则得到一条简单道路L（起点u和终点v），且包含了G的全部边，即L是一条Euler道路。推论13-1.1.1非平凡连通图G＝V，E含有欧拉道路当且仅当G仅有零个或者两个奇数度结点。注意：若有两个奇度数结点，则它们是G中每条欧拉通路的端点。2020/2/29计算机学院10例13-1.2由定理13-1.1及推论13-1.1.1容易看出：a)是欧拉图；b)不是欧拉图，但存在欧拉道路；c)既不是欧拉图，也不存在欧拉道路。V2V1V5V3V4(a)V2V1V5V3V4(b)V1V4V2V3(c)现在，我们是不是已经解决了哥尼斯堡七桥问题？Ab2BDCb4b1b3b5b7b62020/2/29计算机学院11有向图的欧拉道路、欧拉图定理13-1.2ⅰ）有向连通图G含有有向欧拉道路，当且仅当除了两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的入度比出度大1，另一个结点的出度比入度大1。ⅱ）有向连通图G含有有向欧拉回路，当且仅当G中的所有结点的入度等于出度。类似于无向图的讨论，对有向图我们有以下结论：同样，有向Euler图的结点度数都为偶数；含有有向Euler道路的图仅有零个或者两个奇度数结点。2020/2/29计算机学院12例13-1.3V1V2V3V4V1V2V3V4V8V2V4V6V1V3V5V7图a)存在一条的欧拉道路：v3v1v2v3v4v1；(a)(b)(c)图(b)中存在欧拉回路v1v2v3v4v1v3v1，因而(b)是欧拉图；图(c)中有欧拉回路v1v2v3v4v5v6v7v8v2v4v6v8v1因而(c)是欧拉图。2020/2/29计算机学院13例13-1.4解，仅有两个度数为奇数的结点b，c，因而存在从b到c的欧拉通路，蚂蚁乙走到c只要走一条欧拉通路，边数为9条。而蚂蚁甲要想走完所有的边到达c，至少要先走一条边到达b，再走一条欧拉通路，因而它至少要走10条边才能到达c，所以乙必胜。甲、乙两只蚂蚁分别位于右图中的结点a，b处，并设图中的边长度是相等的。甲、乙进行比赛：从它们所在的结点出发，走过图中的所有边最后到达结点c处。如果它们的速度相同，问谁先到达目的地？cb(乙)a(甲)2020/2/29计算机学院14Fleury算法（构造Euler回路）1.任取v0∈V，令P0＝v0；2.设P0＝v0e1v1e2…eivi，按下面的方法从GK=E-{e1,e2,…,ei}中选取ei+1：1)ei+1与vi相关联；2)除非无别的边可选取，否则ei+1不应该为Gk＝G-{e1,e2,…,ei}中的割边；3.当Gk为零图时，算法结束；否则，返回2。设G＝V，E是一个欧拉图即如果ei+1是割边，同时还有其它边与vi相关联，则不能选ei+12020/2/29计算机学院15例13-1.5v4v5v6e4e5e6e10e9e8e3在右图所示的欧拉图中，某人用算法求Ｇ中的欧拉回路时，走了简单的回路：v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2之后，无法行遍了，试分析在哪步他犯了错误？v1v3v7e1e2e7v８e1３e1２e1４e1１v2v4v5v6e4e5e6e10e9e8e3v1v3v7e1e2e7v８e1３e1２e1４e1１v2此人行遍v8时犯了能不走桥就不走桥的错误，因而未能行遍出欧拉回路。当他走到v8时，Ｇ－｛e2，e3，e14，e10，e1，e8｝,见右图，此时，e9为该图中的桥，而e7、e11均不是桥。因此，他不该走e9，而应该走e7或e11。但在行遍v3和v1时，也遇到桥，为什么没有问题呢？v9v92020/2/29计算机学院16中国邮递员问题山东师范大学，管梅谷先生1962提出并解决。（参考文献：①1962（数学通报）81.10,P32,②电子技术应用,81.5）一个邮递员从邮局出发，在其分管的投递区域内走遍所有的街道把邮件送到每个收件人手中，最后又回到邮局，要走怎样的线路使全程最短。343441123235424323这个问题用图来表示：街道为图的边，街道交叉口为图的结点，问题就是要从这样一个图中找出一条至少包含每条边一次的总长最短的回路。2020/2/29计算机学院17对此，管梅谷曾证明，若图的边数为m，则所求回路的长度最小是m，最多不超过2m，并且每条边在其中最多出现两次。中国邮递员问题，一般为在带权连通图中找一条包括全部边的且权最小的回路。这个问题有着有效的解决办法，其中最直观的方法之一是:把图中的某些边复制成两条边，然后在所求图中找一条欧拉回路。中国邮递员问题是运筹学中一个典型的优化问题。显然，当这个图是欧拉图时，任何一条欧拉回路都符合要求；当这个图不是欧拉图时，所求回路必然要重复通过某些边。关键是：复制哪些边？2020/2/29计算机学院18算法（1）若G不含奇数度结点，则任一欧拉回路就是问题的解决。（2）若G含有2K(K0)个奇数度结点，则先求出其中任何两点间的最短路径，然后再在这些路径之中找出K条路径P1，P2，…，PK，使得满足以下条件：①任何Pi和Pj（i≠j）没有相同的起点和终点。②在所满足①的K条最短路径的集合中，P1，P2，…PK的长度总和最短。（3）根据（2）中求出的K条最短道路P1，P2，…，PK，在原图G中复制所有出现的在这条道路上的边，设所得之图为G′。（4）构造G′的欧拉回路，即得中国邮递员问题的解。找出需复制的边连通图中，奇数度结点的个数必为偶数个。2020/2/29计算机学院19例13-1.61．因为G含有奇数度结点，所以2．G中有2K=4(K=2)个奇结点V1，V2，V3，V5。这4点间的距离d(V1,V2)=3，d(V1,V3)=5，d(V1,V5)=4，d(V2,V3)=2，d(V2,V5)=3，d(V3,V5)=4各路径:V1V2(3),V3V5(4)—7V1V3(5),V2V5(3)—8V1V5(4),V2V3(2)—6∴两条长度最短P1=V1V7V5,P2=V2V33．构造G’的任一E图就是中国邮递员问题的解。37311V25621323V6V5V7V4V3V137311V25621323V6V5V7V4V3V1321G′G2020/2/29计算机学院20习题十三1、2、4、5、7、8实验三利用Kruskal算法，用C语言编写出给定无向连通加权图G，构造一棵最小生成树的程序。测试数据:采用教材P150的例11.3进行验证。2020/2/29计算机学院21