数学建模之最佳巡回

2、求如下所示网络的最佳巡回。

v35124v141v22v4336v6

v5图G

摘要：由于图中的

V1、V2、V3、V4为其次顶点，故图不是欧拉图。求得最佳

巡回的前提为此图为欧拉图。所以需要通过对奇次顶点之间引入重复边，使之成为欧拉图。运用floyd算法求出以

V1、V2、V3、V4V1、V2、V3、V4之间的最短路径和距离，从而做出

为顶点的完备图G1。进而求出G1的最小权完美匹配

V2，V4,VV6MV1到,VV2，沿4到6的最短路径添加重复边，得.在图中沿

欧拉图G2。G2中一条欧拉巡回就是G的一条最佳巡回，其权值为37

关键词：欧拉图 最佳巡回 floyd

问题分析：图G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次。若要找出最佳巡回，需在一些点对之间引入重复边（重复边与它平行的边具有相同的权），使原图成为欧拉图。引入重复边的点必须是奇次顶点。在配对时，要求最佳配对，即点对之间距离总和最小。再沿点对之间的最短路径添加重复边得欧拉图，其欧拉巡回便是原图的最佳巡回．

模型建立及求解 符号说明 G 原图

MV1,V2，V4,V6G1 以

V1、V2、V3、V4为顶点的完备图

V2，V4,VVM沿,VVV1到2，沿4到66G2 的最短路径添加重复边后得的欧拉图

W 带权邻接矩阵

D 最短距离矩阵 R 插入点矩阵

1i6，1Pvivj Vi与Vj之间的最短路径 （j6）

d(Vi,Vj) Vi与Vj之间的最短距离 （ 1i6，1j6）

M 最小权完美匹配

求结过程

首先，图G中有

V1、V2、V3、V4四个奇次定点，用floyd算法求出它们之间

的最短路径和距离：

把带权邻接矩阵W作为距离矩阵的初值。在MATLAB中输入：  0 4 5 Inf 1 Inf 4 0 1 Inf 2 Inf 5 1 0 2 Inf 4 W

Inf Inf 2 0 3 3 1 2 Inf 3 0 6 Inf Inf 4 3 6 0[D,R]=floyd(W) 求得最短距离矩阵

 0 3 4 4 1 7 1 5 5 5 5 5 3 0 1 3 2 5 5 2 3 3 5 3 4 1 0 2 3 4 2 2 3 4 2 6D R

4 3 2 0 3 3 5 3 3 4 5 6 1 2 3 3 0 6 1 2 2 4 5 6 7 5 4 3 6 0 5 3 3 4 5 6 则

V1、V2、V3、V4之间的最短路径和距离为

Pv1v2VV15V2,d(V1,V2)3Pv1v4VV15V4,d(V1,V4)4Pv1v6VV15V6,d(V1,V6)7Pv2v4V2V3V4,d(V2,V4)3Pv2v6V2V3V6,d(V1,V2)5

Pv4v6V4V6,d(V4,V6)3V1、V2、V3、V4

其次，以为顶点，它们之间的距离为边权构造完备图G1

图G1

再次，求出G1的最小权完美匹配

MV1,V2，V4,V6

V2，V4VMV1到,VV2，沿4,V66的最短路径添加重复边，得欧拉图G2。G2最后，在图中沿到

中一条欧拉巡回就是G的一条最佳巡回，其权值为37

