图论第3章-树与最短路

第3章树,树连通无回路的无向图称为无向树,简称树,常用T表示树。(即树是不包含回路的连通图)平凡图称为平凡树。若无向图G至少有两个连通分支,则称G为森林。在无向树中，悬挂顶点称为树叶，度数大于或等于2的顶点称为分支点。,例：判断下列哪些图是树？,v1,v2,v3,v4,v5,v1,v2,v3,v4,v5,v1,v2,v4,v3,v5,(a),(b),(c),解:图(a)是树,因为它连通又不包含回路。图(b),(c)不是树,因为图(b)虽连通但有回路,图(c)虽无回路但不连通。在图(a)中,v1、v4、v5为均为叶，v2、v3均为分支节点。,定理：设G=V,E是无向图，|V|=n，|E|=m，则下列各命题是等价的：G是树。G中每一对结点之间存在惟一的路。G中无回路且m=n1。G是连通的且m=n1。G是连通的且G中任何边均为桥。G中无回路，但在任何两个不同的结点之间增加一个新边，得到一个惟一的含新边的回路。证明：G是树，所以G是连通的，uV，vV，u和v之间存在一条路。若路不惟一，设L1和L2都是u和v之间的路，则L1和L2组成了G中的一个回路，与G是树矛盾。,先证G中无回路。若G中存在某个结点v上的自回路，uV，由条件知u到v存在一条路L1：uv，因为v上有自回路，所以u到v存在另一条路L2：uvv，这与G中每一对结点之间存在惟一的路矛盾。若G中存在长度大于等于2的一条回路，则回路上两个结点之间存在不同的路。这与条件是矛盾的。所以G中无回路。以下用归纳法证明m=n1。当n=1时，G为平凡图，m=0=11=n1。结论成立。设nk时，结论成立。下证n=k+1时，结论也成立。,设nk时，结论成立。下证n=k+1时，结论也成立。设e=(u,v)是G中的一条边，由于G中无回路，所以G-e(在G删除边e所得的子图)有两个连通分支G1和G2，设它们的结点数和边数分别为：m1，n1和m2，n2。于是有n1k和n2k，由归纳假设知：m1=n11和m2=n2-1，则：m=m1m21=n1-1n2-11=n-1。,只须证明G是连通的。若不然，设G有t(t2)个连通分支G1，G2，Gt，Gi中均无回路，都是树。由可知，mi=ni1，i=1,t。于是m=m1m2mt=n1-1n2-1nt-1=n1n2nt-t=nt，由于t2，这与m=n1矛盾。所以G是连通图。只须证明G的每一条边均为桥。设e是G的任意边，删除e得子图G1，G1中的边数m1=m-1，G1中的结点数n1=n，m1=m1=n-1-1=n-2=n1-2n1-1，所以G1不是连通图，所以e是桥。,由于G中每一条边均为桥，因而G中无回路。又因为G连通，所以G是树。由知，uV，vV，uv，u与v之间存在一条惟一的路。在u与v之间增加一条新边，就得到G的一条回路，显然这条回路是惟一的。只须证明G是连通的，uV，vV，uv，在u与v之间增加一条新边(u,v)就产生G的一个惟一的回路，故结点u和结点v连通。由于u与v是任意的，所以G是连通图。,定理：设T是n阶非平凡的无向树，则T中至少有两片树叶。证:因为T是非平凡树,所以T中每个顶点的度数都大于等于1,设T有k片树叶,则有(n-k)个顶点度数大于等于2,由握手定理可知2m=d(vi)k+2(n-k)由m=n-1,将此结果代入上式后解得k2。,例：画出5阶所有非同构的无向树。,解：设Ti为5阶无向树,则Ti的边数为4，Ti的度序列之和为8，(Ti)4,(Ti)1,可能的度序列为：(1)1,1,1,1,4;(2)1,1,1,2,3;(3)1,1,2,2,2;,解：由握手定理2m=d(vi)及n=m+1,设G有t个1顶点,则有下列关系式2x2+3+4x3+t=2m=2x(n-1)=2x(2+1+3+t-1)解得：t=9。,例：无向树G有2个2度结点，1个3度结点，3个4度结点，则其1度结点数为多少？,解：设G有t个4度分支点，则有下列关系式8x1+2x3+tx4=2x(8+2+t-1)解得：t=2则G中共有12个顶点，11条边，度数序列之和为22，(Ti)=4,(Ti)=1,度序列为：1,1,1,1,1,1,1,1,3,3,4,4其非同构的图形为：,例：无向树G有8片树叶，2个3度分支点，其余分支点均为4度，问G有多少个4度分支点？画出其非同构的情况。,其非同构的图形为：,解：有如下6种情况:,(1,1,1,1,1,5),(1,1,2,2,2,2),(1,1,1,3,2,2),(1,1,3,3,1,1),(1,1,4,2,1,1),例：画出6阶所有非同构的无向树。,生成树设G为无向图，若G的生成子图是一棵树，则该树称为G的生成树。设G的生成树为T，则T中的边称为树枝。G的不在生成树T中的边称为弦。T的所有弦的集合的导出子图称为T的余树。注意：余树不一定是树。一个无向连通图，如果它本身不是树，它的生成树是不唯一的。但所有的连通图都具有生成树。,例：在下图中，(2)为(1)的一棵生成树T，(3)为T的余树，但（3）不是树。,a,b,c,d,e,a,b,c,d,e,a,b,c,d,(1),(2),(3),定理：无向图G具有生成树的充分必要条件是G为连通图。证明：若无向图G具有生成树，显然G为连通图。以下证明若无向图G为连通图，则G具有生成树。若连通图G无回路，则G本身就是一棵生成树；若G至少有一个回路，删除此回路的一边，得到子图G1，它仍然连通，并与G有相同结点集。若G1无回路，则G1就是一棵生成树；若G1仍有一个回路，再删除G1回路上的一边。重复上述过程，直至得到一个无回路的连通图，该图就是一棵生成树。由该定理的证明过程可以看出，一个连通图可以有多个生成树。因为在取定一个回路后，就可以从中去掉任一条边，去掉的边不同，可能得到的生成树也不同。,推论1:无向连通图G有n个结点和m条边，则mn1。证明：由上述定理的证明知，G有生成树，设为T。|E(G)|=m，其中，E(G)是图G的边构成的集合。|E(T)|=n1,其中，E(T)是树T的边构成的集合。而|E(G)|E(T)|，所以mn1。推论2：在无向连通图中，一个回路和任何一棵生成树的补至少有一条公共边。证明：若有一个回路和一棵生成树的补无公共边，那么，这个回路包含在该生成树中，这与树的定义矛盾。,推论3：在无向连通图中，一个边割集和任何一棵生成树至少有一条公共边。证明：若有一个边割集和一棵生成树无公共边，那么，删除这个边割集所得的子图必包含该生成树，从而该子图是连通的。这与边割集的定义矛盾。设G为无向连通图，有n个结点和m条边。T为G的生成树，T有n个结点和n-1条边。所以要得到G的一棵生成树，必须删除G的m-(n-1)=mn1条边。,最小生成树设无向连通带权图G=,T是G的一棵生成树，T的各边权之和称为T的权，记作W(T)。G的所有生成树中权最小的生成树称为G的最小生成树。求最小生成树的算法很多，我们只介绍避圈法（克鲁斯克尔Kruskal算法）。,设n阶无向连通带权图G=有m条边,不妨设G中无环(否则可先删去)，算法为：将m条边按权从小到大顺序排列，设为e1,e2,em。(2)取e1在T中，然后依次检查e2,em，若ej(j=2,3,m)与T中的边不能构成回路，则取ej在T中，否则放弃ej，考虑下一条边，直至jm。(3)算法停止时得到的T为G的最小生成树。,Kruskal算法一种求最小生成树的算法,例：下图(a)给出了一个赋权图G，用kruskal算法求出G的最小生成树。解：先将m条边按权由小到大排列：(v4,v5)，(v1,v8)，(v5,v7)，(v6,v7)，(v4,v6)，(v5,v6)，(v2,v7)，(v2,v5)，(v7,v8)，(v2,v3)，(v3,v4)，(v1,v2)。它们的权分别是：3,4,5,6,6.5,7,7.5,8,10.5,11,12,13。逐次取边：(v4,v5),(v1,v8),(v5,v7),(v6,v7),(v2,v7),(v7,v8),(v2,v3)构成的生成树在下图(b)，这是G的最小生成树。最小生成树T的权C(T)=3+4+5+6+7.5+10.5+11=47。,例:用避圈法求下图所示的最小生成树,a,b,c,d,e,f,5,5,5,5,1,3,6,6,4,2,解:W(T)=1+2+3+4+5=15，图中黄色为最小生成树。,3,例：铺设一个连接各个城市的光纤通信网络。图中蓝色为最小生成树。,破圈法求最小生成树,避圈法是贪婪地增加不构成回路的边，以求得最小生成树。从另一个角度来考虑最小成树问题，由G的圈（回路）最优条件，我们也可以在原连通权图G中逐步删除构成回路中权最大的边，最后剩下的无回路的生成子图为最小成树。我们把这种方法称为“破圈法”。,例：在图(a)中给出了一个连通图,求此图的生成树。,(a),8,7,7,6,5,5,4,4,4,普里姆(Prim)算法,普里姆算法的基本思想：从连通网络N=V,E中的某一顶点u0出发，选择与它关联的具有最小权值的边(u0,v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。,用普里姆(Prim)算法构造最小生成树的过程,从节点开始，选最小权值的边1，节点（，）入U;从U中选最小权值边4，且对应节点不在U中，入U;从U中选最小权值边2，且对应节点不在U中，入U;从U中选最小权值边5，且对应节点不在U中，入U;从U中选最小权值边3，且对应节点不在U中，入U;,根树及其应用一个有向图，略去方向后是树，则称这个有向图为有向树。如果一棵有向树恰有一个结点入度为0，其余所有结点入度为1，此有向树称为根树。在根树中，入度为0的结点称为树根，出度为0的结点称为树叶，出度不为0的结点称为分枝点或内点。从此定义可以看出，在根树中，除了树叶都是分枝点或内点外，树根也是分枝点。,(1),(2),v0,v1,v2,v3,v4,v5,v6,v7,v0,v1,v2,v3,v4,v5,v6,v7,例:下图(1)为一棵根树。V0为树根,v1,v4,v3,v6,v7为树叶,v2,v5为内点,v0,v2,v5为均为分支点,由于在根树中有向边的方向均一致,故可省掉其方向,如图(2)。,v0,v1,v2,v3,v4,v5,v6,v7,从树根到T的任意顶点v的通路（路径）长度称为v的层数，层数最大顶点的层数称为树高，平凡树也称为根树。例：下图中,v1,v2,v3,在第一层上，v4,v5在第二层上，v6,v7在第三层上。树高为3。,家族树设T为非平凡的根树，u，v为其两个顶点，,a)若u可达v，则称u是v的祖先，v是u的后代；,b)若u邻接到v，则称u是v的父亲，v是u的儿子；,c)若u，v有相同的父亲，则称u，v是兄弟；,d)称v及其后代的导出子图为T以v为根的根子树。,在根树中，若每个结点的最大出度为m，则称该树为m叉树。在m叉树中，若每个结点的出度恰等于0或m，则称该树为完全m叉树。在完全m叉树中，若所有树叶层数相同，则称该树为正则m叉树。当m=2时，m叉树就是二叉树，完全m叉树就是完全二叉树。,（a）是2叉树，（b）是正则2叉树（c）是完全2叉树。,定理：在完全m叉树中，其树叶数为t，分枝点数为i，则(m-1)i=t-1。证明：由定理的条件知，该树有it个结点，该树边数为it-1。另一方面，由完全m叉树定义知，该树出度的和为：mi，这也是该树的边数，于是有mi=it-1。整理后有(m-1)i=t-1。,最优二叉树：设T是有t片叶子的二叉树,其中t片叶子分别带有权1,2,t,称T为带权二叉树称为二叉树T的权,其中li为带权i的树叶vi的层数。在所有带权1,2,t的二叉树中,带权最小的二叉树称为最优二叉树。,在下图所示的三棵树中,都是带权1,3,4,5,6的二元树,W(T1)=47,W(T2)=54,W(T3)=42,但它们中有无最优二叉树。是否有最优二叉树?最优权重是多少？,T1,T2,T3,4,5,1,6,3,3,4,5,6,1,1,3,6,4,5,Huffman算法一种求最优二叉树的算法,1952年,哈夫曼给出了求最优二叉树的算法,该算法的核心思想为:从带权1+2,3,t的最优二叉树可得到带权1,2,t的最优二叉树.基本步骤如下:(1)连接1,2为权的两片叶子,得一分枝点,其权为1+2。(2)在1+2,3,t中选出两个最小的权,连接它们对应的顶点(不一定都是树叶)的分枝点及所带的权。(3)重复(2),直到形成t-1个分枝点,t片叶子为止。,例:求带权1,3,4,5,6的最优二元树。,4,4,8,1,3,3,8,4,3,1,1,3,4,5,6,4,4,11,5,6,1,4,8,11,19,最优二叉树在通信编码中的应用,设=12n-1n为长为n的符号串,称其子串1,12,12n-1分别为该符号串的长度为1,2,n-1的前缀。设B=1,2,m为一个符号串集合,若对于任意的i,jB,ij,i,j,互不为前缀,则称B为前缀码。若符号串中i(i=1,2,m)只出现0,1两个符号,则称B为二元前缀码。,又如：1,00,011,0101,01001,01000是前缀码。而1,00,0101,0100,01001,01000不是前缀码，因为0100是01001的前缀，也是01000的前缀。,例：0,10,110,11111,01,001,0001等是前缀码而1,11,101,001,0011不是前缀码,若使用前缀码中的0、1序列表示英文字母，当接收者收到0、1组成的长串时，就可以惟一的、准确无误地分割成字母对应的0、1序列。定理：任意一个二叉树，可以产生惟一的前缀码。证明：在二叉树中，每一个分枝点引出的左侧边标记0，右侧边标记1。由根结点到树叶的路经上各边的标记组成的0、1序列作为该片树叶的标记。显然，没有一片树叶的标记是另一片树叶的标记的前缀。所有树叶的标记构成了一个前缀码。,由上面做法知，vi处的符号串的前缀均在vi所在的通路上除vi外的顶点处达到，因而所得符号串集合为二元前缀码。,0,1,0,1,1,0,1,0,1,00,0100,0101,011,11,例：右图所示的二元树产生的前缀吗为11,00,011,0100,0101,利用Huffman算法求出的最优2叉树产生的前缀码称为最佳前缀码。,例:在通信中,0,1,2,3,4,5,6,7出现的频率如下0：30,1：20,2：153：10,4：10,5：56：5,7：5求传输它们的最佳前缀码,100,60,40,30,30,20,20,15,15,10,5,5,5,0,1,0,1,0,1,0,1,0,1,0,1,10,10,0,1,00000,00001,0001,001,100,101,11,01,解:将各字符出现的频率作为其相应的权1=5,2=5,3=5,4=10,5=10,6=15,7=20,8=30为8个权,利用Huffman算法求出的最优2叉树如图所示(码长取3,如101传5),图中方框中的8个码子是最佳前缀码。树T是带权1,2,8的最优二叉树。带权为i的树叶vi对应的码子传输出现频率为i,的数字，即,11传1101传401传00001传5001传200001传6100传300000传7。,决策树若树的每个内点都对应着一次决策,这些顶点的子树都对应着该决策的每种可能结果,这样的有序树称为决策树。例：有8枚外观相同的硬币,其中有7枚重量相同,而剩余的一枚伪币较轻,要求以比较重量的方法用一架天平去找出伪币。解:用1-8标记硬币,每次衡量有3种可能:左旁低下,保持水平,右旁低下,下图给出这一解决过程的决策图。图中表示不会出现的结果。,决策树的结点左侧标记着状态,这里表示包含有伪币的硬币集合,右侧标记测试内容。,1,2,3,8,1,2,3对6,7,8,右旁低下,左旁低下,1,2,3,1对3,3,2,1,5,4,8,7,6,说明:(1)决策树的每一内部结点对应于一个部分解;每个叶子对应于一个解。每一内部结点联结于一个获得新信息的测试。从每一结点出发的每一枝标记着不同的测试结果。一个解决过程的执行对应于通过从根到叶的一条路。一个决策树是所有可能的解决路的集合。(2)可以用决策树估计排序的最坏情况时间。排序问题可描述为:将n个元素x1,x2,xn按升序或降序排列。这里将研究的排序算法基于二叉比较,即一次比较两个元素，每次这样的比较都缩小了可能的排序集合。因此,基于二叉比较的排序算法可以表示成二叉树,其中每个内点表示两个元素的一次比较,每个树叶表示n个元素的n!种排列种的一种。,二叉树的遍历,二叉树的遍历访问一棵根树的每个顶点一次且仅一次称为树的遍历。遍历一棵二叉树的方法常有如下三种：（1）中序遍历法：访问顺序为“左子树、树根、右子树”；（2）前序遍历法：访问顺序为“树根、左子树、右子树”；（3）后序遍历法：访问顺序为“左子树、右子树、树根”。,例：试用三种周游方式行遍下图。,+,+,+,-,a,。,。,。,。,。,b,c,e,f,g,h,i,d,j,中序行遍法访问此树：(a(b+c)+def)(g+(h-i)j),前序行遍法访问此树：(+(a(+bc)d(ef)+g(-hij),后序行遍法访问此树：abc+def+ghi-j+,图G的一个顶点v的离径R(v)定义为:图G的半径R(G)定义为,所有满足R(v)=R(G)的顶点v都称为G的中心.显然一个图的直径为:例：求下图G的每个结点的离径及图G的直径,半径和心.,定理设P=u1u2ulul+1是树T的一条最长路,则(1)T的直径为l;(2)若l为奇数,设l=2k-1,则T的半径为k。T有两个相邻的中心,即为ukuk+1。并且每一条长为l的路都通过这两个中心。(3)若l为偶数,设l=2k,则T的半径为k。T中只有一个中心,即为uk+1。并且每一条长为l的路都通过该中心。,定理的证明,若ik,因为d(ui,uk)=k-i,故d(u,uk)=d(u,ui)+d(ui,uk）i-1+k-ik,则d(u,uk)=d(u,ui)+d(ui,uk)l+1-i+i-k=l+1-k=2k-k=k(l=2k-1)所以对T中的任意结点u有d(u,uk)k,故R(uk)k从而R(T)k.综合上述论证易得R(T)=k,且R(uk)=k,即uk为T的一个中心.同理可证uk+1为T的一个中心.下证长为l的任意一条路P一定过中心uk与uk+1.设P的两个端点分别是u和u,则u和u均不在P上.对P上的任意两个内部点ui和uj,由T的连通性,T中一定存在u-ui路Q1和u-uj路Q2,使得(V(Q1)-ui)V(P)=;(V(Q2)-uj)V(P)=.不妨设ij.因为T是树,故P=Q1P(ui,uj)Q2.若ijk,则d(u,u)d(u,ui)+d(ui,uj)+d(uj,u)(i-1)+(j-i)+(j-1)=2(j-1)2(k-1)2k-1=l同理,若kij,则d(u,u)0表示i城市到j城市的距离。若i与j之间无路可通，那么d(ij)就是无穷大。又有d(ii)=0。通过这个距离矩阵D，把任意两个城市之间的最短路径找出来。分析：对于任何一个城市而言，i到j的最短距离不外乎存在经过i与j之间的k和不经过k两种可能，所以可以令k=1，2，3，.，n(n是城市的数目)，检查d(ij)与d(ik)+d(kj)的值；d(ik)与d(kj)分别是目前为止所知道的i到k与k到j的最短距离，因此d(ik)+d(kj)就是i到j经过k的最短距离。,所以，若有d(ij)d(ik)+d(kj)，就表示从i出发经过k再到j的距离要比原来的i到j距离短，自然把i到j的d(ij)重写为d(ik)+d(kj)，每当一个k查完了，d(ij)就是目前的i到j的最短距离。重复这一过程，最后当查完所有的k时，d(ij)里面存放的就是i到j之间的最短距离了。这就是动态规划中的记忆化搜索。,定义：已知矩阵A(aij)ml，B(bjk)1n，规定CA*B(cij)mn，其中cijmin(ai1bjk)lnb1j,ai2b2j,ailblj)定义：已知矩阵A(aij)mn，B(bij)mn，规定D=AB(dij)mn，其中dijmin(aij,bij)可以利用上面定义的运算求任意两点间的最短距离。已知n阶加权简单图G，设D(dij)mn是图G的边权矩阵，即dij(i,j)(若G是有向图，则dij),若结点i到结点j无边相连时，则取dij。然后依次计算出矩阵D2,D3,Dn及S。,其中D2D*D()nn，d2ij=mindi1+d1j，di2+d2j，dindnjd2ij表示从vi出发两步可以到达vi的道路中距离最短者。D3D2*D()nn，dkij表示从vi出发k步可以到达vj的道路中距离最短者DnDn-1*D()nnSDD2D3Dn(Sij)nn由定义可知dkij表示从结点i到j经k边的路（在有向图中即为有向路）中的长度最短者，而Sij为结点i到j的所有路（若是有向图即为有向路）中的长度最短者。Floyd算法的时间复杂性是O(n4)。,求下图各点间的最短路径,解：,D2,121371236,121371236,*,23482364,3465,D3,D5,D4,6,类似可得：,所以：,SDD2D3D4D5(sij)66,Floyd-Warshall算法,Floyd-Warshall算法是解决任意两点间的最短路径的一种算法。基本思想：通过求解矩阵序列D(0)，D(1)，D(n)来实现问题的求解。,其中：D(0)图的距离矩阵；D(n)最终解；dij边(vi,vj)的权值；d(k)ij从vi到vj在所经过的顶点号k最短路径长度。即通过依次比较顶点修改路径实现求解的。对于任意两个顶点vi，vj，对于新比较的顶点vk一旦出现d(k-1)ijdikdkj，则修改对应的d(k)ij。,例：求下图各点间的最短路径,解：比较经过顶点号1的矩阵,D(1),121371236,123456,123456,无改变,解：比较经过顶点号2的矩阵,D(2),121371236,123456,123456,4,8,d(1)14d12d24所以修改d(2)14,d(1)16d12d26所以修改d(2)16,解：比较经过顶点号3的矩阵,D(3),12481371236,123456,123456,4,2,3,3,d(2)14d13d34,d(2)15d13d35,d(2)24d23d34,d(2)25d23d35,解：比较经过顶点号4的矩阵,D(4),1234812371236,123456,123456,6,5,4,d(3)16d13d34d46,d(3)26d23d34d46,d(3)36d34d46,解：比较经过顶点号5的矩阵,D(5),12346123512436,123456,123456,无改变,解：比较经过顶点号6的矩阵,D(6),12346123512436,123456,123456,无改变,D(6)就是最终解，可以看到，和Floyd方法求得的结果是一样的。,D(6),Warshall算法求有向网络G=(V,E)中任两点间距离。设D为G的距离矩阵，n=|V|。(1)输入D矩阵;(2)k1;(3)i1;(4)dijmindij,dik+dkj，j=1.n;(5)ii+1，若in，转(4);(6)kk+1，若kn，转(3);(7)Stop。,计算复杂度O(n3),1962年我国的管梅谷首先提出并研究了如下的问题：邮递员从邮局出发经过他投递的每一条街道，然后返回邮局，邮递员希望找出一条行走距离最短的路线。这个问题被称为中国邮递员问题。,中国邮递员问题,我们把邮递员的投递区域看作一个连通的带权无向图G，其中G的顶点看作街道的交叉口和端点，街道看作边，权看作街道的长度，解决中国邮递员问题，就是在连通带权无向图中，寻找经过每边至少一次且权和最小的回路。,如果图G只有两个奇点x和y，则存在一条以x和y为端点的欧拉链，因此，由这条欧拉Euler链加x到y最短路即是所求的最优投递路线。,如果连通图G不是欧拉图也不是半欧拉欧拉图，由于图G有偶数个奇点，对于任两个奇点x和y，在G中必有一条路连结它们。将这条路上的每条边改为二重边得到新图H1，则x和y就变为H1的偶点，在这条路上的其它顶点的度数均增加2，即奇偶数不变，于是H1的奇点个数比G的奇点个数少2。,定理:设P是加权连通图G中一条包含G的所有边至少一次的回路，则P是最优回路的充要条件（具有最小长度）是：(1)P中无二重以上的边；(2)在G的每个圈中C中，重复边集E的长度之和不超过这个圈的长度的一半，即W(E)1/2W(C).,奇偶点作业法:(1)把G中所有奇度顶点配成对，将每对奇度顶点之间的一条路上的每边改为二重边，得到一个新图G1，新图G1中无奇度顶点，即G1为多重欧拉图.(2)若G1中某对结点间有多于两条边连接，则去掉其中偶数条边，留下一条或两条边连接这两个结点，直到每对相邻结点至多由2条边连接。得到图G2.,(3)检查G2的每个圈C，若某个圈C上重复边集E的权和超过这个圈的权和的一半，则将C按定理1必要性证明中的方法进行调整，直到对G2所有的圈其重复边的权和不超过此圈权和的一半，得到图G3.(4)用Fleury算法求G3的欧拉回路.,例：求下图G的最优回路.,v1,v2,v3,v4,v5,v6,v7,v8,v9,v10,v11,v12,245,5364,646,5447,938,A,v1v10v9v8,v26v114v126v7,5543477,v3