2022年数学建模之最佳巡归类 .pdf

2、求如下所示网络的最佳巡回。3214v6v3v4v5v1v2514236图 G 摘要：由于图中的1234VVVV、为其次顶点，故图不是欧拉图。求得最佳巡回的前提为此图为欧拉图。 所以需要通过对奇次顶点之间引入重复边，使之成为欧拉图。运用 floyd 算法求出1234VVVV、之间的最短路径和距离， 从而做出以1234VVVV、为 顶点 的完 备图G1。 进 而 求 出 G1 的最 小权 完美 匹配1246V ,VV ,VM，.在图中沿1246V ,VV ,VM，到2V，沿4V到6V的最短路径添加重复边，得欧拉图 G2。G2 中一条欧拉巡回就是G 的一条最佳巡回，其权值为37 关键词：欧拉图最佳巡回floyd 问题分析：图 G 不是欧拉图，则G 的任何一个巡回经过某些边必定多于一次。若要找出最佳巡回， 需在一些点对之间引入重复边 （重复边与它平行的边具有相同的权），使原图成为欧拉图。 引入重复边的点必须是奇次顶点。在配对时，要求最佳配对， 即点对之间距离总和最小。 再沿点对之间的最短路径添加重复边得欧拉图，其欧拉巡回便是原图的最佳巡回模型建立及求解符号说明G 原图G1 以1234VVVV、为顶点的完备图G2 沿1246V ,VV ,VM，到2V，沿4V到6V的最短路径添加重复边后得的欧拉图W 带权邻接矩阵D 最短距离矩阵R 插入点矩阵Pijv vijVV与之间的最短路径ij（16，16）(,)ijd V VijVV与之间的最短距离ij（16，16）M 最小权完美匹配求结过程首先，图 G中有1234VVVV、四个奇次定点，用floyd算法求出它们之间的最短路径和距离：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 3 页 - - - - - - - - - 把带权邻接矩阵 W作为距离矩阵的初值。在MATLAB 中输入： 0 4 5 Inf 1 Inf 4 0 1 Inf 2 Inf 5 1 0 2 Inf 4Inf Inf 2 0 3 3 1 2 Inf 3 0 6 Inf Inf 4 3 6 0WD,R=floyd(W) 求得最短距离矩阵 0 3 4 4 1 7 3 0 1 3 2 5 4 1 0 2 3 4 4 3 2 0 3 3 1 2 3 3 0 6 7 5 4 3 6 0D1555523353223426533456122456533456R则1234VVVV、之间的最短路径和距离为12141624264615212154141561623424236124646P,(,)3P,(,)4P,(,)7P,(,)3P, (,)5P,(,)3v vv vv vv vv vv vVV Vd V VVV Vd V VVV Vd V VV V Vd V VV VVd V VV Vd V V其次，以1234VVVV、为顶点，它们之间的距离为边权构造完备图G1 图 G1 再次，求出 G1的最小权完美匹配1246V ,VV ,VM，最后，在图中沿1246V ,VV ,VM，到2V，沿4V到6V的最短路径添加重复边，得欧拉图G2 。G2中一条欧拉巡回就是G的一条最佳巡回，其权值为37 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 3 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 3 页 - - - - - - - - -