网络的最佳巡回

《网络的最佳巡回》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、网络的最佳巡回姓名：杨艳芬班级：13统计本（1）班学号：130513040一、问题重述求如下所示网络的最佳巡回。v35124v4vv43v1263126v5图G【摘要】：由于图G中的V1、V2、V4、V6为奇次顶点，故图G不是欧拉图。要想得到最佳巡回的前提是此图必须为欧拉图。所以需要通过对奇次顶点之间引入重复边，使它成为欧拉图。运用floyd算法求出之间的最短路径和距离，从而做出以V1、V2、V4、V6为顶点的完备图G1。进而求出G1的最小权完美匹配M={（V1，V2），（V4，V6）}。在图G中沿V1到V2，沿

2、V4到V6的最短路径添加重复边，得到欧拉图G2。G2中一条欧拉巡回就是图G的一条最佳巡回，其权值为37。【关键词】：欧拉图最佳巡回floyd二、问题分析1、根据欧拉图的定义可知，图G不是欧拉图，则图G的任何一个巡回经过某些边必定多于一次。2、若要找出最佳巡回，需在一些点对之间引入重复边（重复边与它平行的边具有相同的权），使原图G成为欧拉图。3、引入重复边的点必须是奇次顶点。4、在配对时，要求最佳配对，即点对之间距离总和最小。再沿点对之间的（注：欧拉图定义：设G=（V，E)是连通无向图。（1）经过G的每边至少一次的

3、闭通路称为巡回；（2）经过G的每边正好一次的巡回称为欧拉巡回；（3)存在欧拉巡回的图称为欧拉图；（4）经过G的每边正好一次的道路称为欧拉道路。三、模型建立及求解1、模型的建立符号说明G原图G1以V1、V2、V4、V6为顶点的完备图G2沿V1到V2，沿V4到V6的最短路径添加重复边后得的欧拉图W带权邻接矩阵D最短距离矩阵R插入点矩阵PvivjVi与Vj之间的最短路径（1i6，1j6）d(Vi，Vj）Vi与Vj之间的最短距离（1i6，1j6）M最小权完美匹配2、求解过程图G中有V1、V2、V4、V6四

4、个奇次顶点，用floyd算法求出它们之间的最短路径和距离：把带权邻接矩阵W作为距离矩阵的初值。对本问题，用MATLAB编程road2.m和floyd.m如下，其中主程序为road2.m%road2.m045inf1inf401inf2inf5102inf4W=infinf203312inf306infinf4360[D,R]=floyd(W)%floyd.mfunction[D,R]=floyd(W)n=size(W,1);D=Wfori=1:nforj=1:nR(i,j)

5、=j;endendRfork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)

6、6306InfInf4360R=123456123456123416123456121456123456k=2D=045Inf1Inf401Inf2Inf510234InfInf2033123306InfInf4360R=123456123456123426123456122456123456k=3D=045719401325510234732033123306954360R=123353123353123426333456122456333456k=4D=0457194013255102347320331233

7、06954360R=123353123353123426333456122456333456k=5D=034417301325410234432033123306754360R=155555523353223426533456122456533456k=6D=034417301325410234432033123306754360R=155555523353223426533456122456533456D=034417301325410234432033123306754360R=155555523353223

8、426533456122456533456即求得最短距离矩阵D034417155555301325523353410234223426DR432033533456123306122456754360533456则V1、V2、V4、V6之间的最短路径和距离为Pv1v2＝Ｖ１Ｖ５Ｖ２，d(V１