《2022年数学建模之最佳巡归类》由会员分享,可在线阅读,更多相关《2022年数学建模之最佳巡归类(3页珍藏版)》请在金锄头文库上搜索。
1、2、求如下所示网络的最佳巡回。3214v6v3v4v5v1v2514236图 G 摘要:由于图中的1234VVVV、为其次顶点,故图不是欧拉图。求得最佳巡回的前提为此图为欧拉图。 所以需要通过对奇次顶点之间引入重复边,使之成为欧拉图。运用 floyd 算法求出1234VVVV、之间的最短路径和距离, 从而做出以1234VVVV、为 顶点 的完 备图G1。 进 而 求 出 G1 的最 小权 完美 匹配1246V ,VV ,VM,.在图中沿1246V ,VV ,VM,到2V,沿4V到6V的最短路径添加重复边,得欧拉图 G2。G2 中一条欧拉巡回就是G 的一条最佳巡回,其权值为37 关键词:欧拉图最
2、佳巡回floyd 问题分析:图 G 不是欧拉图,则G 的任何一个巡回经过某些边必定多于一次。若要找出最佳巡回, 需在一些点对之间引入重复边 (重复边与它平行的边具有相同的权),使原图成为欧拉图。 引入重复边的点必须是奇次顶点。在配对时,要求最佳配对, 即点对之间距离总和最小。 再沿点对之间的最短路径添加重复边得欧拉图,其欧拉巡回便是原图的最佳巡回模型建立及求解符号说明G 原图G1 以1234VVVV、为顶点的完备图G2 沿1246V ,VV ,VM,到2V,沿4V到6V的最短路径添加重复边后得的欧拉图W 带权邻接矩阵D 最短距离矩阵R 插入点矩阵Pijv vijVV与之间的最短路径ij(16,
3、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 I
4、nf 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
5、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 页 - - - - - - - - -