【正文】 ???1v 2v 3v4v 5v 6v? ?1 1 1 1 1 1 1 1 1 投遞路線 歐拉圖 1454256536321 vvvvvvvvvvvvvC ：結(jié)論 ： 對任意一個含奇點的郵路圖 G，由于奇點的個數(shù)為偶數(shù)個，把每兩個配成一對，由于 G為連通圖，每對奇點之間至少存在一條鏈，對該條鏈上的每一條邊增加一條重復(fù)邊，可得一歐拉圖，該歐拉圖對應(yīng)一條投遞路線 尋找最佳投遞路線方法 ： 在原郵路圖上增加一些重復(fù)邊得一個歐拉圖，在所得歐拉圖上找出一條歐拉回路。計算重復(fù)邊的權(quán)和，重復(fù)邊權(quán)和最小歐拉回路既為所求的最佳投遞路線 管梅谷 —— 奇偶點圖上作業(yè)法 奇偶點圖上作業(yè)法 ： 例：求解右圖所示的郵路問題 第一步：確定一個初始可行方案 方法： 檢查圖 G中是否有奇點 無奇點： ，找出一條以 v1為 起點的歐拉回路 ，該回路就是最佳投遞路線 有奇點： 圖 G已是歐拉圖 把所有奇點兩兩配成一對，每對奇點找一條鏈，在該條鏈上的每一條邊增加一條重復(fù)邊，得一個歐拉圖 G1， 由 G1所確定的歐拉回路即為一個可行方案 v2 ， v8 ， v4 ， v6 G中有奇點： 取 v2到 v4的一條鏈： v2v1v6v7v8v9v4 取 v6到 v8的一條鏈： v6v1v2v3v4v9v8 )( 1為郵局vG ?1v?2v?3v?6v4v?5v?2 4 3 4 6 9 5 ?7v?8v?9v4 4 3 5 4 G1 顯然 G1不是最佳方案 G1是歐拉圖， 第二步：調(diào)整可行方案， 使重復(fù)邊權(quán)和下降 重復(fù)邊權(quán)和 = 若圖中某條邊有兩條或多于兩條的重復(fù)邊 同時去掉偶數(shù)條， G2 使圖中每一條邊最多有一條重復(fù)邊 G2的重復(fù)邊權(quán)和 = ?1v?2v?3v?6v4v?5v?2 4 3 4 6 9 5 ?7v?8v?9v4 4 3 5 步驟 可得到重復(fù)邊權(quán)和較小的歐拉圖 4 G2 ?1v?2v?3v?6v4v?5v?2 4 3 4 6 9 5 ?7v?8v?9v4 4 3 5 4 51 21 ?1v?2v?3v?6v4v?5v?2 4 3 4 6 9 5 ?7v?8v?9v4 4 3 5 G2是歐拉圖， 重復(fù)邊權(quán)和 =21 G2 4 使圖中每個初等圈重復(fù)邊的 權(quán)和不大于該圈權(quán)和的一半 9個初等圈 ?1v?2v?3v?6v4v?5v?2 4 3 4 6 9 5 ?7v?8v?9v4 4 3 5 G2 4 3 G3是歐拉圖， 重復(fù)邊權(quán)和 =17 G3 ?1v?2v?3v?6v4v?5v?2 4 3 4 6 9 5 ?7v?8v?9v4 4 3 5 4 6 （ 1） v1v2v5v6v1 16 √ 7 （ 2） v6v5v8v7v6 14 √ 10 （ 3） v2v3v4v5v2 24 √ 4 （ 4） v5v4v9v8v5 16 √ G3的初等圈 權(quán)和 重復(fù)邊權(quán)和 13 （ 5） v1v2v5v8v7v6v1 24 G4 ?1v?2v?3v?6v4v?5v?2 4 3 4 6 9 5 ?7v?8v?9v4 4 3 5 4 G4 ?2v?3v?6v4v?5v?2 4 3 4 6 9 5 ?7v?8v?9v4 4 3 5 4 7 （ 1） v1v2v5v6v1 16 √ 4 （ 2） v6v5v8v7v6 14 √ 4 （ 3） v2v3v4v5v2 24 √ 8 （ 4） v5v4v9v8v5 16 √ G4的初等圈 權(quán)和 重復(fù)邊權(quán)和 11 （ 5） v1v2v5v8v7v6v1 24 ?1v√ （ 6） v2v3v4v9v8v5v2 32 4 √ （ 8） v6v5v4v9v8v7v6 （ 7） v1v2v3v4v5v6v1 28 11 √ 22 4 √ （ 9） v1v2v3v4v9v8v7v6v1 36 7 √ G4是最佳方案 最佳投遞路線：16785894561254321 vvvvvvvvvvvvvvvvv奇偶點圖上作業(yè)法 ： 第一步：確定一個初始可行方案 方法： 檢查圖 G中是否有奇點。 無奇點： ，找出一條以 v0為起點的 歐拉回路，該回路就是最佳投遞路線 有奇點： 圖 G已是歐拉圖 把所有奇點兩兩配成一對，每對奇點找一條鏈，在該條鏈上的每一條邊增加一條重復(fù)邊 第二步：調(diào)整可行方案，使重復(fù)邊權(quán)和下降 使圖中每一條邊最多有一條重復(fù)邊 若圖中某條邊有兩條或多于兩條的重復(fù)邊， 同時去掉偶數(shù)條 使圖中每個初等圈重復(fù)邊的權(quán)和 ≤ 該圈權(quán)和的一半 若圖中某初等圈重復(fù)邊的權(quán)和大于該圈權(quán)和的一半 去掉圈中的重復(fù)邊同時將圈中沒有重復(fù)邊的邊加上重復(fù)邊 ? 車輛從某配送中心（ v1）出發(fā)，給街道邊上的超市（ v2,v3,v4,v5,v6,v7,v8,v9）送貨，如圖48所示。 案例 v1 v3 v2 v4 v8 v7 v6 v5 v9 2 5 4 3 3 9 5 4 6 4 4 4 圖 1 ? 顯然街區(qū)圖上有奇點（ 4個 ），不滿足 “ 一筆畫 ” 的條件，則必然有一些街道要被重復(fù)走過（ 添加重復(fù)邊 ）才能回到原出發(fā)點。此時得到的圖就無奇點。 ? 那么該怎樣添加重復(fù)邊，使得圖中全為偶點呢？ ? 其實可以通過連接匹配的奇點得到！ 第一步：確定初始可行方案 v1 v3 v2 v4 v8 v7 v6 v5 v9 2 5 4 3 3 9 5 4 6 4 4 4 圖 2 ? 這樣就得到初始方案 .在這個圖中，沒有奇點，故稱它為歐拉圖。對應(yīng)于這個可行方案，重復(fù)邊總權(quán)為 51。 想一想 ? 這樣的可行方案是不是只有一種呢？ ? 在確定一個可行方案后，怎么判斷這個方案是否為最優(yōu)方案？ ? 若不是最優(yōu)方案，如何調(diào)整這個方案？ 第二步：調(diào)整可行方案 ? 最優(yōu)方案必須滿足以下（ 1）（ 2）兩個條件： ? （ 1）在最優(yōu)方案中 ,圖的每一邊最多有一條重復(fù)邊 ? （ 2）在最優(yōu)方案中 ,圖中每個圈上的重復(fù)邊的總權(quán)不大于該圈總權(quán)的一半。 為什么 ? 第二步：調(diào)整可行方案 ? 首先，去掉多余的重復(fù)邊，使圖中每一邊最多有一條重復(fù)邊。見圖 3 v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 4 4 4 3 4 2 3 4 6 9 5 5 圖 3 第二步：調(diào)整可行方案 ? 其次，如果把圖中某個圈上的重復(fù)邊去掉，而給原來沒有重復(fù)邊的邊上加上重復(fù)邊，圖中仍然沒有奇點。因而如果在某個圈上重復(fù)邊的總權(quán)數(shù)大于這個圈的總權(quán)數(shù)的一半，像上面所說的那樣做一次調(diào)整，將會得到一個總權(quán)下降的可行方案。 第二步：調(diào)整可行方案 ? 在圖 410中，圈（ v2,v3,v4, v9,v2）的總長度為 24，但圈上重復(fù)邊總權(quán)為 14，大于該圈總長度的一半，因此可以做一次調(diào)整，以 [v2,v9]， [v9,v4]上的重復(fù)邊代[v2,v3]， [v3,v4]上的重復(fù)邊，使重復(fù)邊總長度下降為 17。見圖 4 v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 4 4 4 3 4 2 3 4 6 9 5 5 圖 4 ? 檢查圖 4中圈（ v1,v2, v9, v6,v7, v8,v1）的總長度為 24，但圈上重復(fù)邊總權(quán)為 13，大于該圈總長度的一半，因此可以做一次調(diào)整，使重復(fù)邊總長度下降為 15。見圖 5。 v1v2v3v4v5v6v7v8v9444342346955圖 5 ? 檢查圖 5，均滿足條件（ 1）和（ 2），于是得到最優(yōu)方案。圖 5中的任一歐拉圈都是汽車的最優(yōu)配送路線。 ? 如： v1v2v9v8v1v8v7v6v5v4v9v6v9v4v3v2v1是汽車的一條最優(yōu)配送路線。 課堂練習(xí) v 1 v 2 v 3 v 4 v 5 v 6 3 2 4 4 5 2 6 4 8 配送路線與車輛調(diào)度 單中心配送路線選