時(shí)文俊

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

關(guān)鍵詞：歐拉圖；歐拉回路；權(quán)數(shù)

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

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

一、圖論概念介紹

定義1. 1稱數(shù)學(xué)結(jié)構(gòu)■為一有向圖，其中V（G）是非空集合，■是從集合E（G）到V（G）×V（G）的一個(gè)映射。稱V（G）和E（G）分別為圖G的頂點(diǎn)集合和邊集合，■為G的關(guān)聯(lián)函數(shù). 若■，則簡(jiǎn)寫成e=uv，稱u是有向邊e的尾，v為有向邊e的頭。 若圖G為無向圖，e=uv時(shí)，稱頂點(diǎn)u與v是邊e的端點(diǎn)。 若■，稱e1與e2是重邊。

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

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

定理1. 1連通圖G是歐拉圖的充分必要條件是對(duì)任意的V∈V（G），d（v）是偶數(shù)，其中d（v）表示v的次數(shù)，即與v相關(guān)聯(lián)的邊數(shù)。

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

二、模型的建立

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

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

三、問題的解決

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

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

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

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

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

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

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

FE算法是有效算法，其時(shí)間復(fù)雜度為■

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

2.快遞員負(fù)責(zé)的投遞區(qū)域?qū)?yīng)的街道圖是非歐拉圖

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

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

添加重邊時(shí)還要注意兩個(gè)原則：（1）不能重復(fù)添加重邊，重復(fù)的重邊應(yīng)成對(duì)去掉，這樣并不改變每一個(gè)頂點(diǎn)的奇偶性；（2）每一個(gè)圈上添加的重邊的總長(zhǎng)不能超過圈長(zhǎng)的一半，否則應(yīng)將此圈上添加的重邊去掉，改在此圈上原來沒有添加重邊的路線上添加重邊，這樣也不改變每一個(gè)頂點(diǎn)的奇偶性。

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

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

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

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

（1）NQFEDPBCDEONMLKABPONMHILKJIHON

（2）NOPBCDEFQHIJKABPDEONMLIJKLMHQN

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

參考文獻(xiàn)：

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

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

[3]徐俊明.圖論及其應(yīng)用[M].合肥：中國(guó)科學(xué)技術(shù)大學(xué)出版社，2010.endprint

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

關(guān)鍵詞：歐拉圖；歐拉回路；權(quán)數(shù)

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

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

一、圖論概念介紹

定義1. 1稱數(shù)學(xué)結(jié)構(gòu)■為一有向圖，其中V（G）是非空集合，■是從集合E（G）到V（G）×V（G）的一個(gè)映射。稱V（G）和E（G）分別為圖G的頂點(diǎn)集合和邊集合，■為G的關(guān)聯(lián)函數(shù). 若■，則簡(jiǎn)寫成e=uv，稱u是有向邊e的尾，v為有向邊e的頭。 若圖G為無向圖，e=uv時(shí)，稱頂點(diǎn)u與v是邊e的端點(diǎn)。 若■，稱e1與e2是重邊。

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

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

定理1. 1連通圖G是歐拉圖的充分必要條件是對(duì)任意的V∈V（G），d（v）是偶數(shù)，其中d（v）表示v的次數(shù)，即與v相關(guān)聯(lián)的邊數(shù)。

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

二、模型的建立

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

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

三、問題的解決

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

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

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

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

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

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

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

FE算法是有效算法，其時(shí)間復(fù)雜度為■

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

2.快遞員負(fù)責(zé)的投遞區(qū)域?qū)?yīng)的街道圖是非歐拉圖

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

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

添加重邊時(shí)還要注意兩個(gè)原則：（1）不能重復(fù)添加重邊，重復(fù)的重邊應(yīng)成對(duì)去掉，這樣并不改變每一個(gè)頂點(diǎn)的奇偶性；（2）每一個(gè)圈上添加的重邊的總長(zhǎng)不能超過圈長(zhǎng)的一半，否則應(yīng)將此圈上添加的重邊去掉，改在此圈上原來沒有添加重邊的路線上添加重邊，這樣也不改變每一個(gè)頂點(diǎn)的奇偶性。

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

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

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

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

（1）NQFEDPBCDEONMLKABPONMHILKJIHON

（2）NOPBCDEFQHIJKABPDEONMLIJKLMHQN

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

參考文獻(xiàn)：

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

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

[3]徐俊明.圖論及其應(yīng)用[M].合肥：中國(guó)科學(xué)技術(shù)大學(xué)出版社，2010.endprint

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

關(guān)鍵詞：歐拉圖；歐拉回路；權(quán)數(shù)

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

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

一、圖論概念介紹

定義1. 1稱數(shù)學(xué)結(jié)構(gòu)■為一有向圖，其中V（G）是非空集合，■是從集合E（G）到V（G）×V（G）的一個(gè)映射。稱V（G）和E（G）分別為圖G的頂點(diǎn)集合和邊集合，■為G的關(guān)聯(lián)函數(shù). 若■，則簡(jiǎn)寫成e=uv，稱u是有向邊e的尾，v為有向邊e的頭。 若圖G為無向圖，e=uv時(shí)，稱頂點(diǎn)u與v是邊e的端點(diǎn)。 若■，稱e1與e2是重邊。

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

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

定理1. 1連通圖G是歐拉圖的充分必要條件是對(duì)任意的V∈V（G），d（v）是偶數(shù)，其中d（v）表示v的次數(shù)，即與v相關(guān)聯(lián)的邊數(shù)。

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

二、模型的建立

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

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

三、問題的解決

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

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

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

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

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

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

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

FE算法是有效算法，其時(shí)間復(fù)雜度為■

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

2.快遞員負(fù)責(zé)的投遞區(qū)域?qū)?yīng)的街道圖是非歐拉圖

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

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

添加重邊時(shí)還要注意兩個(gè)原則：（1）不能重復(fù)添加重邊，重復(fù)的重邊應(yīng)成對(duì)去掉，這樣并不改變每一個(gè)頂點(diǎn)的奇偶性；（2）每一個(gè)圈上添加的重邊的總長(zhǎng)不能超過圈長(zhǎng)的一半，否則應(yīng)將此圈上添加的重邊去掉，改在此圈上原來沒有添加重邊的路線上添加重邊，這樣也不改變每一個(gè)頂點(diǎn)的奇偶性。

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

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

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

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

（1）NQFEDPBCDEONMLKABPONMHILKJIHON

（2）NOPBCDEFQHIJKABPDEONMLIJKLMHQN

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

參考文獻(xiàn)：

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

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

[3]徐俊明.圖論及其應(yīng)用[M].合肥：中國(guó)科學(xué)技術(shù)大學(xué)出版社，2010.endprint