【教程】大學(xué)競(jìng)賽數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)行遍性問(wèn)題ppt(編輯修改稿)
2024-08-28 16:20 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 一條邊 e i+ 1 ，使： a ） e i+ 1 與 v i 相關(guān)聯(lián) b ）除非不能選擇，否則一定要使 e i+ 1 不是 G i =G [ E { e 1 ,e 2 , … ,e i }] 的割邊． （３）第（２）步不能進(jìn)行時(shí)就停止． 2 . G 不是歐拉圖 若 G不是歐拉圖，則 G的任何一個(gè)巡回經(jīng)過(guò)某些邊必定多于一次． 解決這類問(wèn)題的一般方法是：在一些點(diǎn)對(duì)之間 引入重復(fù)邊（重復(fù)邊與它平行的邊具有相同的權(quán)）， 使原圖成為歐拉圖，但希望所有添加的重復(fù)邊的 權(quán)的總和為最?。? 情形１ G 正好有兩個(gè)奇次頂點(diǎn) （１）用 Di j k s t r a 算法求出奇次頂點(diǎn) u 與 v 之間的最短路徑 P ． （２）令 G * = G ? P ，則 G * 為歐拉圖 . （３）用 F l e u r y 算法求出 G * 的歐拉巡回，這就是 G 的最佳巡回． v7 e3 v1 v2 v3 v4 e1 e2 e4 e5 v5 v6 e6 e7 e8 e9 情形２ G 有２ n 個(gè)奇次頂點(diǎn)（ n ? ２） E d m o n d s 最小對(duì)集算法：基本思想 ： 先將奇次頂點(diǎn)配對(duì)，要求最佳配對(duì)，即點(diǎn)對(duì)之間距離總和最小．再沿點(diǎn)對(duì)之間的最短路徑添加重復(fù)邊得歐拉圖 G * ， G * 的歐拉巡回便是原圖的最佳巡回． 算法步驟：（１）用 F l o y d 算法求出所有奇次頂點(diǎn)之間的最短路徑和距離． （２）以 G 的所有奇次頂點(diǎn)為頂點(diǎn)集（偶數(shù)個(gè)元素），作一完備圖，邊上的權(quán)為兩端點(diǎn)在原圖 G 中的最短距離，將此完備加權(quán)圖記為 G 1 ． （４）在 G 中沿配對(duì)頂點(diǎn)之間的最短路徑添加重復(fù)邊得歐拉圖 G * ． （５）用 F l e u r y 算法求出 G * 的歐拉巡回，這就是 G 的最佳巡回． （３）求出 G1的 最小權(quán)理想匹配 M，得到奇次頂點(diǎn)的最佳配對(duì) ． 例 求右圖所示投遞區(qū)的一條最佳郵遞路線．1
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1