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