文档介绍：该【图论讲义41E图 】是由【1781111****】上传分享，文档一共【6】页，该文档可以免费在线阅读，需要了解更多关于【图论讲义41E图 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..、基本概念七桥问题:如下图。从任一陆地点出发,经过每座桥一次且仅一次回到出发点,是否可能?哥尼斯堡七桥G转化为图论问题:图G中从任一顶点出发,经过每条边恰好一次回到出发点,是否可能?Euler环游(tour,circuit,closedtrail):经过图G的每条边恰好一次的闭迹。Euler迹(trail):经过每条边恰好一次的迹。Euler图:有Euler环游的图。七桥问题:图G是否Euler图?二、。证明:设图G是Euler图,C是G中一个Euler环游。对?v∈V(),v必在C上出现。因C每经过v一次,就有两条与v关联的边被使用。设C经过v共k次,则d(v)=2k。充分性:无妨设ν(G)>1。因G连通,故至少有一条边。下面用反证法证明充分性结论。假设图G无奇度顶点,但它不是Euler图。令S={G|G至少有一条边,无奇度顶点,且不是Euler图}则S≠φ。取S中边数最少的一个,记为G′。因δ(G′)≥2,故G′含有圈,因而含有闭迹。设C是G′中一条最长的闭迹。由假设,C不是G′的Euler环游。因此G′E(C)必有一个连通分支至少含有一条边。记这个连通分支为G。由于C是闭迹,故G中没有奇度顶点,00且ε(G)<ε(G′)。由G′的选择可知,G必有Euler环游C。由于G′连通,故C必经过G0000中至少一个顶点,从而V(C)V(C)≠φ。因此C+C是G′的一条闭迹,且00ε(C+C)>ε(C),这与C的选取矛盾。证毕。01:..无妨设ν()1。因G连通且无奇度顶点,故δ(G)≥2,因而必含有圈。当ν(G)=2时,设仅有的两点为u,v,则u,v间必有偶数条边,它们显然构成Euler回路。假设ν(G)=k时,结论成立。当ν(G)=k+1时,任取v∈V(G)。令S={v的所有关联边}。记S中的边为e,e,e,12m其中m=d(v)为偶数。记G′=Gv。对G′作如下操作:(1)任取e,e∈S,设e=vv,e=vv;ijiijj(2)G′:=G′+vv,S:=S{e,e};ijij(3)若S=φ,则令G′:=G′?v,停止;否则转(1)继续。这个过程最终得到的G′有k个顶点,且每个顶点在G′中的度与在G中完全一样。由归纳假设,G′中有Euler环游,设为P。将P中上述添加边vv都用对应的两条边e,e代替,显ijij然获得G的一条Euler环游。证毕。定理一个连通图有Euler迹当且仅当它最多有两个奇度顶点。证明必要性:设连通图G有Euler迹C,其起点和终点分别为u,v。若uv∈E(G),则G有Euler闭迹(环游),,G无奇度顶点。若uv?G,则G+uv有Euler环游。,图G+uv无奇度顶点。故G最多只可能有两个奇度顶点。充分性:若G无奇度顶点,,G有Euler环游,自然有Euler迹。若G只有两个奇度顶点,设其为u,v,则给G添加一条新边e=uv所得的图G+e的每个顶点都是偶度顶点。从而G+e有Euler环游。故G有Euler迹。证毕。。证明留作****题。例三、求Euler图中的Euler环游-∈V(G),令w:=v,i:=0。=vevLev已取定。从E{e,e,L,e}中选取一条边e,使得i011ii12ii+1(1)e和v相关联;i+1i2:..2)e不选G=G{e,e,,e}的割边,除非没有别的选择。,停止。定理若G是Euler图,则Fleury算法终止时得到的是G的Euler环游。证明设G是Euler图,W=veveLev是Fleury算法终止时得到的迹。则显然v在n0112nnnG=G{e,e,L,e}中的度数是0(v,若不是0,则算法应继续)。故n12nnv=v(否则v在G中是奇度顶点,这不可能),即W是闭迹。0nnn若W不是G的Euler环游,设S={G中度>0的所有顶点}。则S≠φ(因W不是Gnnn的Euler环游,有边不在W上),且W上有S中的点(否则G中W上的点都是G的孤立nnnnn点,这与G是Euler图(从而连通)矛盾),但v∈S=V(G)S。设m是W上使得v∈Snnm而v∈S的最大整数。因W终止于S=V(G)S,故e=vv是G中[S,S]的仅m+1nm+1mm+1m有的一条边,因而是G的一条割边。mv=v0nSSevevmm+1m+1设e是G中和v关联的另一条边(因d(v)>0,这样的边e一定存在),则由算法第mmGnm二步知:e必定也是G的一条割边(否则,按算法应选e而不选e),因而e是G[S]的mm+1m割边。但由于W是闭迹,v=v∈S,且对?v∈S,d(v)是偶数。故G[S]=G[S]中n0nGmn每个顶点都是偶数度顶点,由此又推出G[S]无割边(连通性一章****题)。m以上两方面矛盾。证毕。例:2314653:..中国邮递员问题(ChinesePostmanProblem)问题(管梅谷,1960):一位邮递员从邮局出发投递邮件,经过他所管辖的每条街道至少一次,然后回到邮局。请为他选择一条路线,使其所行路程尽可能短。图论模型:求赋权连通图中含有所有边的权最小的闭途径。这样的闭途径称为最优回路。思想:(1)若G是Euler图,则G的Euler环游便是最优回路,可用Fleury算法求得;(2)若G不是Euler图,则含有所有边的闭途径必须重复经过一些边,最优回路要求重复经过的边的权之和达到最小。闭途径重复经过一些边,实质上可看成给图G添加了一些重复边(其权与原边的权相等),最终消除了奇度顶点形成一个Euler图。因此,在这种情况下求最优回路可分为两步进行:首先给图G添加一些重复边得到Euler图*,使得添加边的权之和w(e)最小,(其中F=E(G*)E(G));然后用Fleury算法求G*的一条Eulere∈F环游。这样便得到G的最优回路。G*∑w(e)问题是:如何给图G添加重复边得到Euler图,使得添加边的权之和最小?e∈F方法一(图上作业法),则C是G的最优回路当且仅当C对应的欧拉图G*满足:(1)G的每条边在G*中至多重复出现一次;(2)G的每个圈上在G*中重复出现的边的权之和不超过该圈总权的一半。证明必要性:先证(1)设C是最优回路,即C是它所对应的G*的一个Euler环游。假设G中的边e=uv被C经过了m次,即在G*中u,v之间有m条重边。若m≥3,则在G*中删去这m条边中的两条,不改变u,v的度数的奇偶性。所得图G′仍为Euler图,但w(G′)<w(G*),即G′中的欧拉环游是比C更优的一条投递路线,这是矛盾的。下证(2)。设C是G中一个圈,且在G*中,C上重复出现的边的权之和>C的权的一半。将C1111上重复的边改为不重复而未重复的边改为重复边。4:..~~*中C上各顶点的度数的奇偶性。设所得图为G,则G仍是欧拉图,但1~~w(G)w(G),G的欧拉环游比C更优。这是不可能的。充分性:设C是G的一个最优回路,G*是它对应的欧拉图;C是G的一条投递路线112(经过所有边的回路),它对应的欧拉图G*满足(1)和(2)。由必要性知,G*也满足(1)21和(2)。我们来证明w(C)=w(C)。21设F、F分别为G*和G*的重复边集合。令F=(FUF)(FF)。则G[F]为F12121212在G*UG*中的导出子图(G[F]中的边全是F和F的边,且无一边既在F中又在F中)。121212**E(G)E(G)12FF12E(G)由于在G*和G*中,过一个顶点v的添加边条数的奇偶性与度数d(v)的奇偶性相同,12G故G[F]中各顶点的度数均为偶数。这表明G[F]各连通分支均为欧拉图。从而G[F]是若干个圈的边不重的并。而且G[F]中各圈均既有F的边又有F的边(因F的边不会形成圈,F1212的也是)。由条件(2),G[F]中任一个圈C′上F的边的权之和与F的边的权之和均不超过1211w(C′)。于是F、F在C′上边的权之和必都等于w(C′)。这说明G[F]中属于F的边21221的权之和=G[F]中属于F的边的权之和。因此w(G*)=w(G*),从而w(C)=w(C)。22121证毕。奇偶点图上作业法:奇偶点图上作业法虽然通俗易懂,但使用时需要检查图的每个圈,对于有很多圈的图,计算量很大,实际当中用得较少。方法二(Edmonds-Johnson方法)定理设G是赋权连通图,G中有2k个奇度顶点。设A={e|e∈E,在求最优回路时e被添加重复边}。则G[A]是以G的奇度顶点为起点和终点的k条无公共边的最短路之并。证明(略)。基于此定理,Edmonds和Johnson于1973年给出了求解邮递员问题的有效算法。Edmonds-Johnson算法:5:..,令G*,转step2;否则转step3。*中的Euler回路,结束。。′为顶点集,构作赋权完全图K,(n=|V′|),使得对n?v,v∈V′,K中边vv的权为v至v在G中最短路的权。。,得Euler图G*,转step2。注:该算法的复杂度为O(ν2)。例:求下图的最优投递路线,A为邮局。B5C358A1410D496FE解:只有两个奇点,V′={B,E}。B到E的最短路为BAFE,权为13。完全赋权图K及2相应的Euler图G*为B5C35138BEA1410D49F6KE2G*易求得其Euler环游,并得到最优回路。6