网络的最佳巡回

网络的最佳巡回姓名：杨艳芬班级：13统计本（1）班学号：130513040一、问题重述求如下所示网络的最佳巡回。3214v6v3v4v5v1v2514236图G【摘要】：由于图G中的V1、V2、V4、V6为奇次顶点，故图G不是欧拉图。要想得到最佳巡回的前提是此图必须为欧拉图。所以需要通过对奇次顶点之间引入重复边，使它成为欧拉图。运用floyd算法求出之间的最短路径和距离，从而做出以V1、V2、V4、V6为顶点的完备图G1。进而求出G1的最小权完美匹配M={（V1，V2），（V4，V6）}。在图G中沿V1到V2，沿V4到V6的最短路径添加重复边，得到欧拉图G2。G2中一条欧拉巡回就是图G的一条最佳巡回，其权值为37。【关键词】：欧拉图最佳巡回floyd二、问题分析1、根据欧拉图的定义可知，图G不是欧拉图，则图G的任何一个巡回经过某些边必定多于一次。2、若要找出最佳巡回，需在一些点对之间引入重复边（重复边与它平行的边具有相同的权），使原图G成为欧拉图。3、引入重复边的点必须是奇次顶点。4、在配对时，要求最佳配对，即点对之间距离总和最小。再沿点对之间的（注：欧拉图定义：设G=（V，E)是连通无向图。（1）经过G的每边至少一次的闭通路称为巡回；（2）经过G的每边正好一次的巡回称为欧拉巡回；（3)存在欧拉巡回的图称为欧拉图；（4）经过G的每边正好一次的道路称为欧拉道路。三、模型建立及求解1、模型的建立符号说明G原图G1以V1、V2、V4、V6为顶点的完备图G2沿V1到V2，沿V4到V6的最短路径添加重复边后得的欧拉图W带权邻接矩阵D最短距离矩阵R插入点矩阵PvivjVi与Vj之间的最短路径ij（16，16）d(Vi，Vj）Vi与Vj之间的最短距离ij（16，16）M最小权完美匹配2、求解过程图G中有V1、V2、V4、V6四个奇次顶点，用floyd算法求出它们之间的最短路径和距离：把带权邻接矩阵W作为距离矩阵的初值。对本问题，用MATLAB编程road2.m和floyd.m如下，其中主程序为road2.m%road2.mW=0634infinf603inf213302infinf4inf2015inf2inf104inf1inf540[D,R]=floyd(W)%floyd.mfunction[D,R]=floyd(W)n=size(W,1);D=Wfori=1:nforj=1:nR(i,j)=j;endendRfork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)D(i,j)D(i,j)=D(i,k)+D(k,j);R(i,j)=R(i,k);endendendkDRend运行程序road2.m，得：D=045Inf1Inf401Inf2Inf5102Inf4InfInf203312Inf306InfInf4360R=123456123456123456123456123456123456k=1D=045Inf1Inf401Inf2Inf510264InfInf2033126306InfInf4360R=123456123456123416123456121456123456k=2D=045Inf1Inf401Inf2Inf510234InfInf2033123306InfInf4360R=123456123456123426123456122456123456k=3D=045719401325510234732033123306954360R=123353123353123426333456122456333456k=4D=045719401325510234732033123306954360R=123353123353123426333456122456333456k=5D=034417301325410234432033123306754360R=155555523353223426533456122456533456k=6D=034417301325410234432033123306754360R=155555523353223426533456122456533456D=034417301325410234432033123306754360R=155555523353223426533456122456533456即求得最短距离矩阵D034417301325410234432033123306754360D155555523353223426533456122456533456R则V1、V2、V4、V6之间的最短路径和距离为Pv1v2＝Ｖ１Ｖ５Ｖ２，d(V１，V２）＝３Pv１v４＝Ｖ１Ｖ５Ｖ４，d(V１，V４）＝４Pv１v６＝Ｖ１Ｖ５Ｖ６，d(V１，V６）＝７Pv２v４＝Ｖ２Ｖ３Ｖ４，d(V２，V４）＝３Pv２v６＝Ｖ２Ｖ３Ｖ６，d(V２，V６）＝５Pv4v６＝Ｖ4Ｖ６，d(V4，V６）＝3以V1、V2、V4、V6为顶点，它们之间的距离为边权构造完备图G1图G1求出G1的最小权完美匹配M={（V1，V2），（V4，V6）}在图G中沿V1到V2，沿V4到V6的最短路径添加重复边，得到欧拉图G2。图G2中一条欧拉巡回就是图G的一条最佳巡回，其权值为37。四、结果分析图G一共有4个奇次顶点，添加重复边如图所示：欧拉巡回为：1→5→2→3→4→6→3→1→2→5→6→4→5→1，巡回长度为37。该结果为图G的最佳欧拉巡回长度，在图G中不可能再找出比巡回长度37更短的距离，即图G只有一个最佳欧拉巡回。五、参考文献[1]赵静,但琦.高等教育出版社•北京，2000.[2]贺定修,冯天祥.西南交通大学出版社•成都,2011.