基于圖論模型的快遞員最優投遞路線設計

時文俊

摘 要：隨著網絡的普及，“網購”的流行，導致快遞員派送快件的工作量增大。本文根據快遞員投遞快件的實際問題建立圖論模型，利用圖論中求歐拉回路的算法，為快遞員設計最優投遞路線，從而節約快遞員的工作時間，減少其勞動強度，提高勞動效率。

關鍵詞：歐拉圖；歐拉回路；權數

圖論是以圖為研究對象的數學分支，近年來發展迅速，應用非常廣泛. 它已經廣泛地應用在物理學、化學、控制論、信息科學、科學管理、電子計算機等各個領域. 在實際生活、生產和科學研究中，有很多問題都可以用圖論的理論和方法來解決。

隨著網絡的普及，“網上購物”成為時下比較流行的一種購物方式，它有著價格比實體店優惠、購物不受時間限制、方便、快捷的優點，還可以送過貨上門，足不出戶就能買到所需要的物品. 網上購物的流行，促使了快遞行業的快速發展，“快遞”成了婦孺皆知的詞語了，但這也無疑加大了快遞員的工作量. 本文根據實際問題建立圖論模型，利用圖論的理論和方法設計合理的投遞路線，以減少快遞員的工作時間和勞動強度，提高其勞動效率。

一、圖論概念介紹

定義1. 1稱數學結構■為一有向圖，其中V（G）是非空集合，■是從集合E（G）到V（G）×V（G）的一個映射。稱V（G）和E（G）分別為圖G的頂點集合和邊集合，■為G的關聯函數. 若■，則簡寫成e=uv，稱u是有向邊e的尾，v為有向邊e的頭。 若圖G為無向圖，e=uv時，稱頂點u與v是邊e的端點。 若■，稱e1與e2是重邊。

定義1. 2在頂邊交錯鏈■中，■■■且■，則稱W是圖G的一條道路，其中允許vi=vj或ei=ej，i≠j，稱Vo是W的起點，Vk是W的終點，K為路長，■稱為W的內點。 各邊相異的道路稱為行跡，各頂相異的道路稱為軌道，記成P（Vo，Vk），起點與終點重合的道路稱為回路，起點與終點重合的軌道叫圈，長K的圈稱為K階圈；u，v兩頂的距離是指u與v為起止點的最短軌道的長度，記成d（u，v），若存在道路以u，v為起止頂，則稱u與v在圖G中連通，G中任二頂皆連通時，稱G為連通圖。

定義1. 3 設G是連通的無向圖，在圖G中包含一切邊的行跡叫做歐拉行跡，包含一切邊的閉行跡叫做歐拉回路。若G中存在歐拉回路，則稱G為歐拉圖。

定理1. 1連通圖G是歐拉圖的充分必要條件是對任意的V∈V（G），d（v）是偶數，其中d（v）表示v的次數，即與v相關聯的邊數。

定義1. 4圖G中的橋是指G中的一邊e∈E（G），使得G-e的連通分支數增加。

二、模型的建立

這個問題的實際模型為：快遞員從快遞公司選好快件去投遞，然后返回快遞公司，他必須經過由他負責投遞的每條街道至少一次，為這位快遞員設計一條投遞線路，使其行走的路程最短，耗時最少。

該問題的圖論模型為：把快遞員所負責的投遞區域看成一個加權的連通圖G，其頂點為街道的交叉口，邊為每條街道，權為每條街道的長度（正數）。快遞員的最優投遞路線即為求G的一個包含一切邊（至少一次）的回路W，使這條回路W的總權數最小. 若對G中對每條邊e∈E（G），用一非負實數w（e）表示其權，求G的包含一切邊的回路W，使得W的總權數■。

三、問題的解決

1.快遞員負責的投遞區域對應的街道圖是歐拉圖若快遞員負責的投遞區域對應的街道圖G是歐拉圖，根據定義1. 3，G中必含有歐拉回路，即包含G的一切邊的閉行跡. 那么所求的最優投遞路線就是G的一條歐拉回路。

根據定理1. 1，如果某快遞員所負責的投遞區域的街道圖中沒有奇頂點（頂點的次數是奇數），那么他就可以從快遞公司出發，經過每個街道一次，且僅一次，最后回到快遞公司。

盡管由定理1. 1可以很輕松地判定給定的街道圖是否為歐拉圖，但如果沿著一條隨意的路線走，也是無法找到歐拉回路的. 假如街道圖如圖1，如果按照圖中箭頭所示的方向從頂點V6出發走了3步以后，就無法再進行下去了。其失敗的原因是用了V6V5邊之后，在未用過的邊的導出子圖中V5V7是橋，提前過橋的后果是斷了去左側的5-圈的后路。

因此，非必要時，不要通過未用過的邊的導出子圖的橋，根據這一思路，1921年，Fleury設計了一個求歐拉回路的有效算法，簡記為FE算法：

（1）任取■，令Wo=Vo，

（2）設路■已選定，則從E（G）-E（W）中選一條邊ei+1，使得ei+1與vi相關聯，且非必要時，ei+1不要選G-E（W）的橋。

（3）反復執行（2），直至每邊皆入選為止。

FE算法是有效算法，其時間復雜度為■

用FE算法在圖1中可選得一條符合條件的最優路，即歐拉回路：■。但符合條件的歐拉回路并不唯一，■也是滿足條件的一條歐拉回路。

2.快遞員負責的投遞區域對應的街道圖是非歐拉圖

因為所對應的街道圖是非歐拉圖，而快遞員要從快遞公司出發，他必須經過由他負責投遞的每條街道至少一次，并回到快遞公司，因此有些街道要走不止一次。重復走某條街道相當于在街道圖中為該街道添加一條重邊。問題轉化為在圖中添加一些重邊，構造成一個歐拉圖并且要求添加的重邊的權數之和最小。

把一個非歐拉圖通過添加重邊變成歐拉圖，也就是通過添加重邊把圖中每個頂點的度數均變為偶數。因此，在添加重邊時，很明顯應該選擇某個奇度頂點為端點添加重邊，如果重邊的另一端點也是奇度頂點，那么這條重邊將這兩個奇度頂點均變為偶度頂點；如果重邊的另一端點是偶度頂點，則添加重邊后，還必須從偶度頂點出發再添加一條重邊與其他一個奇度頂點相連，因為原來的偶度頂點又變成了奇度頂點。

添加重邊時還要注意兩個原則：（1）不能重復添加重邊，重復的重邊應成對去掉，這樣并不改變每一個頂點的奇偶性；（2）每一個圈上添加的重邊的總長不能超過圈長的一半，否則應將此圈上添加的重邊去掉，改在此圈上原來沒有添加重邊的路線上添加重邊，這樣也不改變每一個頂點的奇偶性。

以上兩個原則既保證了添加重邊后每個頂點都是偶度頂點，又保證了添加重邊的總長最短。因此，添加重邊后的街道圖必存在歐拉回路。根據FE算法，即可找到滿足條件的最優線路。下面看一具體的例子。

假設某快遞公司的某快遞員負責的投遞范圍為鄭州市二七區的中原路以南、隴海路以北、大學路以西、嵩山路以東的范圍. 以街道的交叉口為頂點，街道為邊，街道的長度（單位：百米）為權數建立一個加權圖，如圖2所示。

在這個圖中，街道的交叉點共有16個，但三次點有12個，因此要想構造出歐拉圖，需要添加的重邊至少有6條。根據添加重邊的原則，每一個圈上添加的重邊的總長不能超過圈長的一半，根據街道圖的特點，圖中包含的圈比較多，但很明顯，大圈之中包含著小圈，故只要每個小圈中添加的重邊的權數不超過圈長的一半，那么在大圈中必然也滿足添加重邊的權數不超過圈長的一半。因此，我們容易得到圖3、圖4兩種添加重邊的方案，

圖3的方案是從N 點出發增加3條重邊，最終將街道圖的每個頂點均為偶度頂點，圖4的方案是添加重邊IJ ，把頂點J 變成了奇度頂點，再添加重邊JK 將J，K 均變為偶度頂點。根據各邊的權數大小，可知這兩種方案添加的重邊的權數之和是相等的，也是最小的。 假設快遞公司在N 點，從圖3、圖4中，可分別找到一條歐拉回路：

（1）NQFEDPBCDEONMLKABPONMHILKJIHON

（2）NOPBCDEFQHIJKABPDEONMLIJKLMHQN

快遞員沿著這兩條路線派送快件，即是最優路線。 由于FE算法中，歐拉回路不唯一，所以快遞員派送快件的最優路線也不唯一。

參考文獻：

[1]王樹禾.圖論[M].北京：科學出版社，2009.

[2]王桂平，王衍，任嘉辰.圖論算法理論、實現及應用[M].北京：北京大學出版社，2011.

[3]徐俊明.圖論及其應用[M].合肥：中國科學技術大學出版社，2010.endprint

摘 要：隨著網絡的普及，“網購”的流行，導致快遞員派送快件的工作量增大。本文根據快遞員投遞快件的實際問題建立圖論模型，利用圖論中求歐拉回路的算法，為快遞員設計最優投遞路線，從而節約快遞員的工作時間，減少其勞動強度，提高勞動效率。

關鍵詞：歐拉圖；歐拉回路；權數

圖論是以圖為研究對象的數學分支，近年來發展迅速，應用非常廣泛. 它已經廣泛地應用在物理學、化學、控制論、信息科學、科學管理、電子計算機等各個領域. 在實際生活、生產和科學研究中，有很多問題都可以用圖論的理論和方法來解決。

隨著網絡的普及，“網上購物”成為時下比較流行的一種購物方式，它有著價格比實體店優惠、購物不受時間限制、方便、快捷的優點，還可以送過貨上門，足不出戶就能買到所需要的物品. 網上購物的流行，促使了快遞行業的快速發展，“快遞”成了婦孺皆知的詞語了，但這也無疑加大了快遞員的工作量. 本文根據實際問題建立圖論模型，利用圖論的理論和方法設計合理的投遞路線，以減少快遞員的工作時間和勞動強度，提高其勞動效率。

一、圖論概念介紹

定義1. 1稱數學結構■為一有向圖，其中V（G）是非空集合，■是從集合E（G）到V（G）×V（G）的一個映射。稱V（G）和E（G）分別為圖G的頂點集合和邊集合，■為G的關聯函數. 若■，則簡寫成e=uv，稱u是有向邊e的尾，v為有向邊e的頭。 若圖G為無向圖，e=uv時，稱頂點u與v是邊e的端點。 若■，稱e1與e2是重邊。

定義1. 2在頂邊交錯鏈■中，■■■且■，則稱W是圖G的一條道路，其中允許vi=vj或ei=ej，i≠j，稱Vo是W的起點，Vk是W的終點，K為路長，■稱為W的內點。 各邊相異的道路稱為行跡，各頂相異的道路稱為軌道，記成P（Vo，Vk），起點與終點重合的道路稱為回路，起點與終點重合的軌道叫圈，長K的圈稱為K階圈；u，v兩頂的距離是指u與v為起止點的最短軌道的長度，記成d（u，v），若存在道路以u，v為起止頂，則稱u與v在圖G中連通，G中任二頂皆連通時，稱G為連通圖。

定義1. 3 設G是連通的無向圖，在圖G中包含一切邊的行跡叫做歐拉行跡，包含一切邊的閉行跡叫做歐拉回路。若G中存在歐拉回路，則稱G為歐拉圖。

定理1. 1連通圖G是歐拉圖的充分必要條件是對任意的V∈V（G），d（v）是偶數，其中d（v）表示v的次數，即與v相關聯的邊數。

定義1. 4圖G中的橋是指G中的一邊e∈E（G），使得G-e的連通分支數增加。

二、模型的建立

這個問題的實際模型為：快遞員從快遞公司選好快件去投遞，然后返回快遞公司，他必須經過由他負責投遞的每條街道至少一次，為這位快遞員設計一條投遞線路，使其行走的路程最短，耗時最少。

該問題的圖論模型為：把快遞員所負責的投遞區域看成一個加權的連通圖G，其頂點為街道的交叉口，邊為每條街道，權為每條街道的長度（正數）。快遞員的最優投遞路線即為求G的一個包含一切邊（至少一次）的回路W，使這條回路W的總權數最小. 若對G中對每條邊e∈E（G），用一非負實數w（e）表示其權，求G的包含一切邊的回路W，使得W的總權數■。

三、問題的解決

1.快遞員負責的投遞區域對應的街道圖是歐拉圖若快遞員負責的投遞區域對應的街道圖G是歐拉圖，根據定義1. 3，G中必含有歐拉回路，即包含G的一切邊的閉行跡. 那么所求的最優投遞路線就是G的一條歐拉回路。

根據定理1. 1，如果某快遞員所負責的投遞區域的街道圖中沒有奇頂點（頂點的次數是奇數），那么他就可以從快遞公司出發，經過每個街道一次，且僅一次，最后回到快遞公司。

盡管由定理1. 1可以很輕松地判定給定的街道圖是否為歐拉圖，但如果沿著一條隨意的路線走，也是無法找到歐拉回路的. 假如街道圖如圖1，如果按照圖中箭頭所示的方向從頂點V6出發走了3步以后，就無法再進行下去了。其失敗的原因是用了V6V5邊之后，在未用過的邊的導出子圖中V5V7是橋，提前過橋的后果是斷了去左側的5-圈的后路。

因此，非必要時，不要通過未用過的邊的導出子圖的橋，根據這一思路，1921年，Fleury設計了一個求歐拉回路的有效算法，簡記為FE算法：

（1）任取■，令Wo=Vo，

（2）設路■已選定，則從E（G）-E（W）中選一條邊ei+1，使得ei+1與vi相關聯，且非必要時，ei+1不要選G-E（W）的橋。

（3）反復執行（2），直至每邊皆入選為止。

FE算法是有效算法，其時間復雜度為■

用FE算法在圖1中可選得一條符合條件的最優路，即歐拉回路：■。但符合條件的歐拉回路并不唯一，■也是滿足條件的一條歐拉回路。

2.快遞員負責的投遞區域對應的街道圖是非歐拉圖

因為所對應的街道圖是非歐拉圖，而快遞員要從快遞公司出發，他必須經過由他負責投遞的每條街道至少一次，并回到快遞公司，因此有些街道要走不止一次。重復走某條街道相當于在街道圖中為該街道添加一條重邊。問題轉化為在圖中添加一些重邊，構造成一個歐拉圖并且要求添加的重邊的權數之和最小。

把一個非歐拉圖通過添加重邊變成歐拉圖，也就是通過添加重邊把圖中每個頂點的度數均變為偶數。因此，在添加重邊時，很明顯應該選擇某個奇度頂點為端點添加重邊，如果重邊的另一端點也是奇度頂點，那么這條重邊將這兩個奇度頂點均變為偶度頂點；如果重邊的另一端點是偶度頂點，則添加重邊后，還必須從偶度頂點出發再添加一條重邊與其他一個奇度頂點相連，因為原來的偶度頂點又變成了奇度頂點。

添加重邊時還要注意兩個原則：（1）不能重復添加重邊，重復的重邊應成對去掉，這樣并不改變每一個頂點的奇偶性；（2）每一個圈上添加的重邊的總長不能超過圈長的一半，否則應將此圈上添加的重邊去掉，改在此圈上原來沒有添加重邊的路線上添加重邊，這樣也不改變每一個頂點的奇偶性。

以上兩個原則既保證了添加重邊后每個頂點都是偶度頂點，又保證了添加重邊的總長最短。因此，添加重邊后的街道圖必存在歐拉回路。根據FE算法，即可找到滿足條件的最優線路。下面看一具體的例子。

假設某快遞公司的某快遞員負責的投遞范圍為鄭州市二七區的中原路以南、隴海路以北、大學路以西、嵩山路以東的范圍. 以街道的交叉口為頂點，街道為邊，街道的長度（單位：百米）為權數建立一個加權圖，如圖2所示。

在這個圖中，街道的交叉點共有16個，但三次點有12個，因此要想構造出歐拉圖，需要添加的重邊至少有6條。根據添加重邊的原則，每一個圈上添加的重邊的總長不能超過圈長的一半，根據街道圖的特點，圖中包含的圈比較多，但很明顯，大圈之中包含著小圈，故只要每個小圈中添加的重邊的權數不超過圈長的一半，那么在大圈中必然也滿足添加重邊的權數不超過圈長的一半。因此，我們容易得到圖3、圖4兩種添加重邊的方案，

圖3的方案是從N 點出發增加3條重邊，最終將街道圖的每個頂點均為偶度頂點，圖4的方案是添加重邊IJ ，把頂點J 變成了奇度頂點，再添加重邊JK 將J，K 均變為偶度頂點。根據各邊的權數大小，可知這兩種方案添加的重邊的權數之和是相等的，也是最小的。 假設快遞公司在N 點，從圖3、圖4中，可分別找到一條歐拉回路：

（1）NQFEDPBCDEONMLKABPONMHILKJIHON

（2）NOPBCDEFQHIJKABPDEONMLIJKLMHQN

快遞員沿著這兩條路線派送快件，即是最優路線。 由于FE算法中，歐拉回路不唯一，所以快遞員派送快件的最優路線也不唯一。

參考文獻：

[1]王樹禾.圖論[M].北京：科學出版社，2009.

[2]王桂平，王衍，任嘉辰.圖論算法理論、實現及應用[M].北京：北京大學出版社，2011.

[3]徐俊明.圖論及其應用[M].合肥：中國科學技術大學出版社，2010.endprint

摘 要：隨著網絡的普及，“網購”的流行，導致快遞員派送快件的工作量增大。本文根據快遞員投遞快件的實際問題建立圖論模型，利用圖論中求歐拉回路的算法，為快遞員設計最優投遞路線，從而節約快遞員的工作時間，減少其勞動強度，提高勞動效率。

關鍵詞：歐拉圖；歐拉回路；權數

圖論是以圖為研究對象的數學分支，近年來發展迅速，應用非常廣泛. 它已經廣泛地應用在物理學、化學、控制論、信息科學、科學管理、電子計算機等各個領域. 在實際生活、生產和科學研究中，有很多問題都可以用圖論的理論和方法來解決。

隨著網絡的普及，“網上購物”成為時下比較流行的一種購物方式，它有著價格比實體店優惠、購物不受時間限制、方便、快捷的優點，還可以送過貨上門，足不出戶就能買到所需要的物品. 網上購物的流行，促使了快遞行業的快速發展，“快遞”成了婦孺皆知的詞語了，但這也無疑加大了快遞員的工作量. 本文根據實際問題建立圖論模型，利用圖論的理論和方法設計合理的投遞路線，以減少快遞員的工作時間和勞動強度，提高其勞動效率。

一、圖論概念介紹

定義1. 1稱數學結構■為一有向圖，其中V（G）是非空集合，■是從集合E（G）到V（G）×V（G）的一個映射。稱V（G）和E（G）分別為圖G的頂點集合和邊集合，■為G的關聯函數. 若■，則簡寫成e=uv，稱u是有向邊e的尾，v為有向邊e的頭。 若圖G為無向圖，e=uv時，稱頂點u與v是邊e的端點。 若■，稱e1與e2是重邊。

定義1. 2在頂邊交錯鏈■中，■■■且■，則稱W是圖G的一條道路，其中允許vi=vj或ei=ej，i≠j，稱Vo是W的起點，Vk是W的終點，K為路長，■稱為W的內點。 各邊相異的道路稱為行跡，各頂相異的道路稱為軌道，記成P（Vo，Vk），起點與終點重合的道路稱為回路，起點與終點重合的軌道叫圈，長K的圈稱為K階圈；u，v兩頂的距離是指u與v為起止點的最短軌道的長度，記成d（u，v），若存在道路以u，v為起止頂，則稱u與v在圖G中連通，G中任二頂皆連通時，稱G為連通圖。

定義1. 3 設G是連通的無向圖，在圖G中包含一切邊的行跡叫做歐拉行跡，包含一切邊的閉行跡叫做歐拉回路。若G中存在歐拉回路，則稱G為歐拉圖。

定理1. 1連通圖G是歐拉圖的充分必要條件是對任意的V∈V（G），d（v）是偶數，其中d（v）表示v的次數，即與v相關聯的邊數。

定義1. 4圖G中的橋是指G中的一邊e∈E（G），使得G-e的連通分支數增加。

二、模型的建立

這個問題的實際模型為：快遞員從快遞公司選好快件去投遞，然后返回快遞公司，他必須經過由他負責投遞的每條街道至少一次，為這位快遞員設計一條投遞線路，使其行走的路程最短，耗時最少。

該問題的圖論模型為：把快遞員所負責的投遞區域看成一個加權的連通圖G，其頂點為街道的交叉口，邊為每條街道，權為每條街道的長度（正數）。快遞員的最優投遞路線即為求G的一個包含一切邊（至少一次）的回路W，使這條回路W的總權數最小. 若對G中對每條邊e∈E（G），用一非負實數w（e）表示其權，求G的包含一切邊的回路W，使得W的總權數■。

三、問題的解決

1.快遞員負責的投遞區域對應的街道圖是歐拉圖若快遞員負責的投遞區域對應的街道圖G是歐拉圖，根據定義1. 3，G中必含有歐拉回路，即包含G的一切邊的閉行跡. 那么所求的最優投遞路線就是G的一條歐拉回路。

根據定理1. 1，如果某快遞員所負責的投遞區域的街道圖中沒有奇頂點（頂點的次數是奇數），那么他就可以從快遞公司出發，經過每個街道一次，且僅一次，最后回到快遞公司。

盡管由定理1. 1可以很輕松地判定給定的街道圖是否為歐拉圖，但如果沿著一條隨意的路線走，也是無法找到歐拉回路的. 假如街道圖如圖1，如果按照圖中箭頭所示的方向從頂點V6出發走了3步以后，就無法再進行下去了。其失敗的原因是用了V6V5邊之后，在未用過的邊的導出子圖中V5V7是橋，提前過橋的后果是斷了去左側的5-圈的后路。

因此，非必要時，不要通過未用過的邊的導出子圖的橋，根據這一思路，1921年，Fleury設計了一個求歐拉回路的有效算法，簡記為FE算法：

（1）任取■，令Wo=Vo，

（2）設路■已選定，則從E（G）-E（W）中選一條邊ei+1，使得ei+1與vi相關聯，且非必要時，ei+1不要選G-E（W）的橋。

（3）反復執行（2），直至每邊皆入選為止。

FE算法是有效算法，其時間復雜度為■

用FE算法在圖1中可選得一條符合條件的最優路，即歐拉回路：■。但符合條件的歐拉回路并不唯一，■也是滿足條件的一條歐拉回路。

2.快遞員負責的投遞區域對應的街道圖是非歐拉圖

因為所對應的街道圖是非歐拉圖，而快遞員要從快遞公司出發，他必須經過由他負責投遞的每條街道至少一次，并回到快遞公司，因此有些街道要走不止一次。重復走某條街道相當于在街道圖中為該街道添加一條重邊。問題轉化為在圖中添加一些重邊，構造成一個歐拉圖并且要求添加的重邊的權數之和最小。

把一個非歐拉圖通過添加重邊變成歐拉圖，也就是通過添加重邊把圖中每個頂點的度數均變為偶數。因此，在添加重邊時，很明顯應該選擇某個奇度頂點為端點添加重邊，如果重邊的另一端點也是奇度頂點，那么這條重邊將這兩個奇度頂點均變為偶度頂點；如果重邊的另一端點是偶度頂點，則添加重邊后，還必須從偶度頂點出發再添加一條重邊與其他一個奇度頂點相連，因為原來的偶度頂點又變成了奇度頂點。

添加重邊時還要注意兩個原則：（1）不能重復添加重邊，重復的重邊應成對去掉，這樣并不改變每一個頂點的奇偶性；（2）每一個圈上添加的重邊的總長不能超過圈長的一半，否則應將此圈上添加的重邊去掉，改在此圈上原來沒有添加重邊的路線上添加重邊，這樣也不改變每一個頂點的奇偶性。

以上兩個原則既保證了添加重邊后每個頂點都是偶度頂點，又保證了添加重邊的總長最短。因此，添加重邊后的街道圖必存在歐拉回路。根據FE算法，即可找到滿足條件的最優線路。下面看一具體的例子。

假設某快遞公司的某快遞員負責的投遞范圍為鄭州市二七區的中原路以南、隴海路以北、大學路以西、嵩山路以東的范圍. 以街道的交叉口為頂點，街道為邊，街道的長度（單位：百米）為權數建立一個加權圖，如圖2所示。

在這個圖中，街道的交叉點共有16個，但三次點有12個，因此要想構造出歐拉圖，需要添加的重邊至少有6條。根據添加重邊的原則，每一個圈上添加的重邊的總長不能超過圈長的一半，根據街道圖的特點，圖中包含的圈比較多，但很明顯，大圈之中包含著小圈，故只要每個小圈中添加的重邊的權數不超過圈長的一半，那么在大圈中必然也滿足添加重邊的權數不超過圈長的一半。因此，我們容易得到圖3、圖4兩種添加重邊的方案，

圖3的方案是從N 點出發增加3條重邊，最終將街道圖的每個頂點均為偶度頂點，圖4的方案是添加重邊IJ ，把頂點J 變成了奇度頂點，再添加重邊JK 將J，K 均變為偶度頂點。根據各邊的權數大小，可知這兩種方案添加的重邊的權數之和是相等的，也是最小的。 假設快遞公司在N 點，從圖3、圖4中，可分別找到一條歐拉回路：

（1）NQFEDPBCDEONMLKABPONMHILKJIHON

（2）NOPBCDEFQHIJKABPDEONMLIJKLMHQN

快遞員沿著這兩條路線派送快件，即是最優路線。 由于FE算法中，歐拉回路不唯一，所以快遞員派送快件的最優路線也不唯一。

參考文獻：

[1]王樹禾.圖論[M].北京：科學出版社，2009.

[2]王桂平，王衍，任嘉辰.圖論算法理論、實現及應用[M].北京：北京大學出版社，2011.

[3]徐俊明.圖論及其應用[M].合肥：中國科學技術大學出版社，2010.endprint