【教程】大學(xué)競(jìng)賽數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)行遍性問(wèn)題ppt-在線瀏覽
2024-09-11 16:20本頁(yè)面
【正文】 ．圖中有 v 4 、 v 7 、 v 8 、 v 9 四個(gè)奇次頂點(diǎn)用 F l o y d 算法求出它們之間的最短路徑和距離：3),(,6),(,9),(,6)(,3),(,5),(,9898979787879,49848484747234989787948474????????????vvdvvPvvdvvPvvdvvPvvdvvvPvvdvvPvvdvvvvPvvvvvvvvvvvv2 ．以 v 4 、 v 7 、 v 8 、 v 9 為頂點(diǎn)，他們之間的距離為邊權(quán)構(gòu)造完備圖 G 1 ． 3 ．求出 G 1 的最小權(quán)完美匹配 M= {( v 4, ,v 7 ) ,( v 8 ,v 9 )} . 4 ．在 G 中沿 v 4 到 v 7 的最短路徑添加重復(fù)邊，沿 v 8 到 v 9 的最短路徑 v 8 v 9 添加重復(fù)邊，得歐拉圖 G 2 ． G 2 中一條歐拉巡回就是 G 的一條最佳巡回．其權(quán)值為 64 ． 返回 哈 密 爾 頓 圖 定義 設(shè) G =( V , E ) 是連通無(wú)向圖 . （１） 經(jīng)過(guò) G 的每個(gè)頂點(diǎn)正好一次的路徑，稱(chēng)為 G 的一條 哈密爾頓路徑 ． （２） 經(jīng)過(guò) G 的每個(gè)頂點(diǎn)正好一次的圈，稱(chēng)為 G 的 哈密爾 頓圈 或 H 圈． （３）含 H 圈的圖稱(chēng)為 哈密爾頓圖 或 H 圖． 返回 推銷(xiāo)員問(wèn)題 定義 流動(dòng)推銷(xiāo)員需要訪問(wèn)某地區(qū)的所有城鎮(zhèn)，最后回到出發(fā)點(diǎn)．問(wèn)如何安排旅行路線使總行程最?。@就是 推銷(xiāo)員問(wèn)題 ． 若用頂點(diǎn)表示城鎮(zhèn)，邊表示連接兩城鎮(zhèn)的路，邊上的權(quán)表示距離（或時(shí)間、或費(fèi)用），于是推銷(xiāo)員問(wèn)題就成為在加權(quán)圖中尋找一條經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次的最短閉通路問(wèn)題． 定義 在加權(quán)圖 G=(V,E)中 ， （ １ ） 權(quán)最小的哈密爾頓圈稱(chēng)為 最佳 H圈 ． （ ２ ） 經(jīng)過(guò)每個(gè)頂點(diǎn)至少
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1