時文俊

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

關鍵詞：歐拉圖；歐拉回路；權數(shù)

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

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

一、圖論概念介紹

定義1. 1稱數(shù)學結構■為一有向圖，其中V（G）是非空集合，■是從集合E（G）到V（G）×V（G）的一個映射。稱V（G）和E（G）分別為圖G的頂點集合和邊集合，■為G的關聯(lián)函數(shù). 若■，則簡寫成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的內(nèi)點。 各邊相異的道路稱為行跡，各頂相異的道路稱為軌道，記成P（Vo，Vk），起點與終點重合的道路稱為回路，起點與終點重合的軌道叫圈，長K的圈稱為K階圈；u，v兩頂?shù)木嚯x是指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）是偶數(shù)，其中d（v）表示v的次數(shù)，即與v相關聯(lián)的邊數(shù)。

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

二、模型的建立

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

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

三、問題的解決

1.快遞員負責的投遞區(qū)域?qū)慕值缊D是歐拉圖若快遞員負責的投遞區(qū)域?qū)慕值缊DG是歐拉圖，根據(jù)定義1. 3，G中必含有歐拉回路，即包含G的一切邊的閉行跡. 那么所求的最優(yōu)投遞路線就是G的一條歐拉回路。

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

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

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

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

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

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

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

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

2.快遞員負責的投遞區(qū)域?qū)慕值缊D是非歐拉圖

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

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

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

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

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

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

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

（1）NQFEDPBCDEONMLKABPONMHILKJIHON

（2）NOPBCDEFQHIJKABPDEONMLIJKLMHQN

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

參考文獻：

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

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

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

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

關鍵詞：歐拉圖；歐拉回路；權數(shù)

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

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

一、圖論概念介紹

定義1. 1稱數(shù)學結構■為一有向圖，其中V（G）是非空集合，■是從集合E（G）到V（G）×V（G）的一個映射。稱V（G）和E（G）分別為圖G的頂點集合和邊集合，■為G的關聯(lián)函數(shù). 若■，則簡寫成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的內(nèi)點。 各邊相異的道路稱為行跡，各頂相異的道路稱為軌道，記成P（Vo，Vk），起點與終點重合的道路稱為回路，起點與終點重合的軌道叫圈，長K的圈稱為K階圈；u，v兩頂?shù)木嚯x是指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）是偶數(shù)，其中d（v）表示v的次數(shù)，即與v相關聯(lián)的邊數(shù)。

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

二、模型的建立

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

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

三、問題的解決

1.快遞員負責的投遞區(qū)域?qū)慕值缊D是歐拉圖若快遞員負責的投遞區(qū)域?qū)慕值缊DG是歐拉圖，根據(jù)定義1. 3，G中必含有歐拉回路，即包含G的一切邊的閉行跡. 那么所求的最優(yōu)投遞路線就是G的一條歐拉回路。

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

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

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

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

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

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

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

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

2.快遞員負責的投遞區(qū)域?qū)慕值缊D是非歐拉圖

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

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

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

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

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

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

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

（1）NQFEDPBCDEONMLKABPONMHILKJIHON

（2）NOPBCDEFQHIJKABPDEONMLIJKLMHQN

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

參考文獻：

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

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

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

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

關鍵詞：歐拉圖；歐拉回路；權數(shù)

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

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

一、圖論概念介紹

定義1. 1稱數(shù)學結構■為一有向圖，其中V（G）是非空集合，■是從集合E（G）到V（G）×V（G）的一個映射。稱V（G）和E（G）分別為圖G的頂點集合和邊集合，■為G的關聯(lián)函數(shù). 若■，則簡寫成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的內(nèi)點。 各邊相異的道路稱為行跡，各頂相異的道路稱為軌道，記成P（Vo，Vk），起點與終點重合的道路稱為回路，起點與終點重合的軌道叫圈，長K的圈稱為K階圈；u，v兩頂?shù)木嚯x是指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）是偶數(shù)，其中d（v）表示v的次數(shù)，即與v相關聯(lián)的邊數(shù)。

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

二、模型的建立

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

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

三、問題的解決

1.快遞員負責的投遞區(qū)域?qū)慕值缊D是歐拉圖若快遞員負責的投遞區(qū)域?qū)慕值缊DG是歐拉圖，根據(jù)定義1. 3，G中必含有歐拉回路，即包含G的一切邊的閉行跡. 那么所求的最優(yōu)投遞路線就是G的一條歐拉回路。

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

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

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

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

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

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

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

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

2.快遞員負責的投遞區(qū)域?qū)慕值缊D是非歐拉圖

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

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

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

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

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

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

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

（1）NQFEDPBCDEONMLKABPONMHILKJIHON

（2）NOPBCDEFQHIJKABPDEONMLIJKLMHQN

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

參考文獻：

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

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

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