運籌學-郵遞員問題

一．一筆畫問題一筆畫問題，也稱為遍歷問題，是很有實際意義的。設有一個連通多重圖G，如果在G中存在一條鏈，經過G的每條邊一次且僅一次，那么這條鏈叫做歐拉鏈。如在G中存在一個簡單圈，經過G的每條邊一次，那么這個圈叫做歐拉圈一個圖如果有歐拉圈，那么這個圖叫做歐拉圖。很明顯，一個圖G如果能夠一筆畫出，那么這個圖一定是歐拉圖或者含有歐拉鏈。1第一頁，共20頁。

定理一個連通多重圖G是歐拉圖的充分必要條件是G中無奇點。證:必要性，顯然。充分性，不妨設，連通多重圖G至少有三點，對G的邊數(shù)q用數(shù)學歸納法。因為G是連通的，并且不含奇點，故q>=3。當q=3時，顯然G是歐拉圖。假設q=n時成立，看q=m+1的情形：由于G是無奇點的連通圖，并且G的點數(shù)p>=3，因此存在三個點μ，v,w,使得[μ，v],[w,v]∈E。從G中去掉邊[μ，v],[w,v]，增加新的邊[μ，w]，得到一個新的多重圖G1，G1有q-1條邊，且仍不含奇點，G1至多有兩個分圖。2第二頁，共20頁。

若G1是連通的，則由歸納假設，G1有歐拉圈C1。把C1中的邊[w,μ]換成[μ,v],[w,v]，即是G中的歐拉圈。若G1有兩個分圖G1’，G1’’，令v在G1’中。由歸納假設，G1’，G1’’分別有歐拉圈C1’，C1’’，把C1”中的邊[μ,w]換成[μ,v],C1’及[v,w]即是G中的歐拉圈。

推論一個多重連通圖G有歐拉鏈的充分必要條件是G有且僅有兩個奇點。這個推論的證明留給讀者作為習題。從這個定理的證明可以看出，識別一個連通圖能否一筆畫出的條件是它是否有奇點。若有奇點，就不能一筆畫出。若沒有奇點，就能夠一筆畫出，并回到原出發(fā)地。3第三頁，共20頁。

比如前面提到的哥尼斯堡七橋問題，歐拉把它抽象成具有四個項點，并且都是奇點的圖8.26的形狀。很明顯，一個漫步者無論如何也不可能重復的走完七座橋，并最終回到原出發(fā)地。圖8.27。僅有兩個奇點，可以一筆畫出。圖8.26BADC圖8.27v5v6v4v2v1v34第四頁，共20頁。

二．圖上作業(yè)法從一筆畫問題的討論可知，一個郵遞員在他所負責投遞的街道范圍內，如果街道構成的圖中沒有奇點，那么他就可以從郵局出發(fā)，經過每條街道一次，且僅一次，并最終回到原出發(fā)地。但是，如果街道構成的圖中有奇點，他就必然要在某些街道重復走幾次。例如,在圖8.27表示的街道圖中，v1表示郵局所在地，每條街道的長度是1，郵遞員可以按照以下的路線行走：5第五頁，共20頁。

v1-v2-v4-v3-v2-v4-v6-v5-v4-v6-v5-v3-v1,總長是12。也可以按照另一條路線走：v1-v2-v3-v2-v4-v5-v6-v4-v3-v5-v3-v1,總長是11。按照第1條路線走，在邊[v2,v4],[v4,v6],[v6,v5]上各走3兩次，按照第2條路線走，在邊[v3,v2],[v3,v5]上各走了兩次。6第六頁，共20頁。

在連通圖G中，如果在邊[vi,vj]上重復走幾次，那么就在點vi,vj之間增加了幾條相應的邊，每條邊的權和原來的權相等，并把新增加的邊叫做重復邊。顯然，這條路線構成新圖中的歐拉圈。如圖8.28a,b所示。并且，郵遞員的兩條邊走路線總路程的差等于新增加重復邊總權的差。7第七頁，共20頁。

v1-v2-v4-v3-v2-v4-v6-v5-v4-v6-v5-v3-v1

圖8.28v5v6v4v2v1v3av5v6v4v2v1v3bv1-v2-v3-v2-v4-v5-v6-v4-v3-v5-v3-v18第八頁，共20頁。

中國郵遞員問題也可以表示為：在一個有奇點的連通圖中。要求增加一些重復邊，使得新的連通圖不含有奇點，并且增加的重復邊總權最小。我們把增加重復邊后不含奇點的新的連通圖叫做郵遞路線，而總權最小的郵遞路線叫做最優(yōu)郵遞路線。(下略)下面我們來介紹初始郵遞路線的確定，改進，以及一個郵遞路線是否是最優(yōu)路線的判定標準的方法-----圖上作業(yè)法。9第九頁，共20頁。

（一）初始郵遞路線的確定方法由于任何一個圖中，奇點的個數(shù)為偶數(shù)，所以如果一個連通圖有奇點，就可以把它們兩兩配成對，而每對奇點之間必有一條鏈（圖是連通的），我們把這條鏈的所有邊作為重復邊追加到圖中去，這樣得到的新連通圖必無奇點，這就給出了初始投遞路線。例如，在圖8.29中，v1是郵局所在地，并有四個奇點v2,v4,v6,v8,將它們兩兩配對，比如v2和v4為一對，v6和v8為一對。10第十頁，共20頁。中國郵遞員問題v7v6v3v4v5v8v1v2圖8.29255944346443v911第十一頁，共20頁。在連接v2和v4的鏈中任取一條，比如鏈（v2,v1,v8,v7,v6,v5,v4）,在加入重復邊[v2,v1],[v1,v8],[v8,v7],[v7,v6],[v6,v5],[v5,v4].同樣，任取連接v6和v8的一條鏈(v8,v1,v2,v3,v4,v5,v6),在加入重復邊[v8,v1],[v1,v2],[v2,v3],[v3,v4],[v4,v5],[v5,v6].于是，得到圖8.30在連通圖8.30中，沒有奇點，故它是歐拉圖。對于這條郵遞路線，重復邊的總長為:2W12+W23+W34+2W45+2W56+W67+W78+2W18=51。

12第十二頁，共20頁。

v7v6v3v4v5v8v1v2圖8.30255944346443v9（v2,v1,v8,v7,v6,v5,v4）(v8,v1,v2,v3,v4,v5,v6)

13第十三頁，共20頁。（二）改進郵遞路線，使重復邊的總長不斷減少。從圖8.30中可以看出，在邊[v1,v2]旁邊有兩條重復邊，但是如果把他們都從圖中去掉，所得到的連通圖仍然無奇點，還是一個郵遞路線，而總長度卻有所減少。同理，在邊[v1,v8],[v4,v5],[v5,v6]旁邊的重復邊也是一樣的。一般地，在郵遞路線上，如果在邊[vi,vj]旁邊有兩條以上的重復邊，從中去掉偶數(shù)條，那么可以得到一個總長度較少的郵遞路線。

14第十四頁，共20頁。

判定標準1。在最優(yōu)郵遞路線上，圖中的每一條邊至多有一條重復邊。按此判定標準，將圖8.30改為圖8.31，這時重復邊的總權減少為21。

v7v6v3v4v5v8v1v2圖8-31255944346443v915第十五頁，共20頁。不難看出，如果把圖中某個圈上的重復邊去掉，而給原來沒有重復邊的邊上加上重復邊，圖中仍然沒有奇點。因此，如果在某個圈上重復邊的總權大于這個圈總權的一半，按照以上所說的作一次調整，將會得到一個總權減少的郵遞路線。

判定標準2。在最優(yōu)郵遞路線上，圖中每一個圈的重復邊的總權小于或者等于該圈總權的一半。

16第十六頁，共20頁。比如在圖8.31中，圈（v2,v3,v4,v9,v2）的總權為24，但圈上重復邊的總權為14，大于該圈總權的一半。因此作一次改進，在該圈上去掉重復邊[v2,v3],[v3,v4],加上重復邊[v2,v9],[v9,v4]，如圖8.32所示。這時重復邊的總權減少為10。

v7v6v3v4v5v8v1v2圖8.32255944346443v917第十七頁，共20頁。

v1v2v3v4v5v6v7v8v9243449556434v1v2v3v4v5v6v7v8v924344955643418第十八頁，共20頁。

v1v2v3v4v5v6v7v8v924344955643419第十九頁，共20頁。從這個例子可知，一個最優(yōu)郵遞路線一定滿足判定標準1和判定標準2。反之，不難證明，一個郵遞路線