数学建模之最佳巡回

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

1、2、求如下所示网络的最佳巡回。图G摘要：由于图中的为其次顶点，故图不是欧拉图。求得最佳巡回的前提为此图为欧拉图。所以需要通过对奇次顶点之间引入重复边，使之成为欧拉图。运用floyd算法求出之间的最短路径和距离，从而做出以为顶点的完备图G1。进而求出G1的最小权完美匹配.在图中沿到，沿到的最短路径添加重复边，得欧拉图G2。G2中一条欧拉巡回就是G的一条最佳巡回，其权值为37关键词：欧拉图最佳巡回floyd问题分析：图G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次。若要找出最佳巡回，需在一些点

2、对之间引入重复边（重复边与它平行的边具有相同的权），使原图成为欧拉图。引入重复边的点必须是奇次顶点。在配对时，要求最佳配对，即点对之间距离总和最小。再沿点对之间的最短路径添加重复边得欧拉图，其欧拉巡回便是原图的最佳巡回．模型建立及求解符号说明G原图G1以为顶点的完备图G2沿到，沿到的最短路径添加重复边后得的欧拉图W带权邻接矩阵D最短距离矩阵R插入点矩阵之间的最短路径之间的最短距离M最小权完美匹配求结过程首先，图G中有四个奇次定点，用floyd算法求出它们之间的最短路径和距离：把带权邻接矩阵W作为距

3、离矩阵的初值。在MATLAB中输入：[D,R]=floyd(W)求得最短距离矩阵则之间的最短路径和距离为其次，以为顶点，它们之间的距离为边权构造完备图G1图G1再次，求出G1的最小权完美匹配最后，在图中沿到，沿到的最短路径添加重复边，得欧拉图G2。G2中一条欧拉巡回就是G的一条最佳巡回，其权值为37