教案圖與網(wǎng)絡(luò)之二ppt課件-資料下載頁
2025-04-30 18:11本頁面
【正文】 習(xí)題 4，圖 95（ 1）、（ 2）。第六節(jié) 中國郵遞員問題n 哥尼斯堡七橋問題與歐拉圖n 中國郵遞員問題n 求解中國郵遞員問題的奇偶點(diǎn)圖作業(yè)法n 奇偶點(diǎn)圖作業(yè)法的改進(jìn)方法一、哥尼斯堡七橋問題與歐拉圖n 哥尼斯堡七橋問題n 歐拉圖與一筆畫問題二、中國郵遞員問題n 1962年，管梅谷先生提出中國郵遞員問題n 若圖中無奇點(diǎn)，歐拉圈即為所求n 若圖中有奇點(diǎn)，則奇點(diǎn)必為偶數(shù)，在奇點(diǎn)間加邊（重復(fù)走），使其變?yōu)榕紨?shù)而成歐拉圖。n 中國郵遞員問題是要求所加邊的權(quán)之和最小。三、求解中國郵遞員問題的奇偶點(diǎn)圖作業(yè)法n 基本思想：n 把一個(gè)有奇點(diǎn)的圖增加重復(fù)邊后成為不含奇點(diǎn)的歐拉圖，構(gòu)造初始可行方案；n 尋找是否存在使重復(fù)邊路長減少的改進(jìn)的可行方案。奇偶點(diǎn)圖作業(yè)法步驟n 構(gòu)造初始可行方案：由于奇點(diǎn)個(gè)數(shù)必為偶數(shù)，因此奇點(diǎn)必成對(duì)出現(xiàn)；同時(shí)由于圖是連通的，因此每一對(duì)奇點(diǎn)之間必存在一條鏈，在這條鏈上的各邊都加上重復(fù)邊而成為新圖，必定是無奇點(diǎn)的歐拉圖。n 尋找改進(jìn)可行方案：在兩奇點(diǎn)間檢查所有鏈，若某鏈的長度小于已加重復(fù)邊的長度，則在該鏈的每邊加上重復(fù)邊，去掉原重復(fù)邊。n 重復(fù)以上步驟，直到任意兩奇點(diǎn)間加重復(fù)邊的鏈?zhǔn)亲疃痰臑橹?。求解中國郵遞員問題：例子例子的初始可行解例子的修正解四、奇偶點(diǎn)作業(yè)法的改進(jìn)方法n 奇偶點(diǎn)作業(yè)法的瓶頸是需檢查太多的鏈n 可以首先求出任意一對(duì)奇點(diǎn)之間的最短路，從中選出總路長最小的組合方案。n 也可以由奇點(diǎn)構(gòu)成偶圖，求最小匹配得到最優(yōu)解。一個(gè)四奇點(diǎn)的例子習(xí)題n ， 習(xí)題 9n ， 習(xí)題 10：圖 910(A)、 (B)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1