1第五章圖論與網(wǎng)絡(luò)優(yōu)化2§5-1引論§5-2圖論基本概念

§5-3樹及其優(yōu)化問題§5-4最短路問題§5-5最大流問題§5-6中國郵遞員問題3這是一個(gè)非常有趣的問題，該問題可描述為：

一個(gè)郵遞員從郵局出發(fā)，要走遍他所負(fù)責(zé)的每一條街道去送信，如圖5-15所示。中國郵遞員問題在物流配送中應(yīng)用比較多，也經(jīng)常作為其它問題的子問題。§5-6中國郵遞員問題問應(yīng)當(dāng)如何選擇適當(dāng)?shù)穆肪€，可使所走的總路程最短。5v3v8v7v6v5v4v2v1v9v13v12v11v10

31111112223336445圖5-154

由于這個(gè)問題是我國學(xué)者菅梅谷于1962年首先提出來的，因此國際上稱它為中國郵遞員問題。

本問題用圖的語言來描述，就是給定一個(gè)連通圖G，在每條邊上有一個(gè)非負(fù)的權(quán)，要尋求一個(gè)圈，經(jīng)過G的每條邊至少一次，并且圈的權(quán)數(shù)最小。相關(guān)的游戲題：

“田”字是否可以一筆畫成？“日”字是否可以一筆畫成？“目”字是否可以一筆畫成？

這些問題稱為一筆畫問題，也稱為遍歷問題，是很有實(shí)際意義的問題。5一．Euler(歐拉)圖【定義17】設(shè)圖G連通，若G中存在含所有邊的簡單鏈C，經(jīng)過G的每條邊一次且僅一次，則C稱為Euler鏈，若C為圈，則稱為Euler圈，當(dāng)G存在Euler圈時(shí)。G稱為Euler圖。由此定義可知：一個(gè)圖G如果能夠一筆畫出，那么這個(gè)圖一定是歐拉圖或者含有歐拉鏈；

G有非閉Euler鏈，則G可一筆畫成。始點(diǎn)與終點(diǎn)必不相同；

G有封閉Euler圈，做一筆畫時(shí)，始點(diǎn)與終點(diǎn)一定重合。6【定理9】圖G是歐拉圖的充分必要條件是G連通且無奇點(diǎn)。此定理提供了一個(gè)判斷Euler圖的有效方法。對(duì)于非閉Euler鏈，則有下述同樣明確的結(jié)論：【定理10】圖G有非閉歐拉鏈的充分必要條件是G連通有且僅有兩個(gè)奇點(diǎn)。

由于要求郵遞員送完郵件后必須返回郵局，其投遞路線就成為一個(gè)圈，從而中國郵遞員問題與Euler圖勢必發(fā)生密切的關(guān)系。事實(shí)上，若所走街巷恰是一個(gè)Euler圖時(shí)，則此Euler圖所對(duì)應(yīng)的Euler圈顯然是一條不走一步回頭路的最優(yōu)投遞路線。所以，如何判斷一個(gè)圖為Euler圖就十分重要了。7CADB哥尼斯堡七橋問題可抽象為下圖所示形狀：

因?yàn)橛?個(gè)奇點(diǎn)，所以該圖不是Euler圈，一個(gè)漫步者無論如何也不可能重復(fù)的走完七座橋，并最終回到原出發(fā)地。而在圖5-16中：因?yàn)閮H有兩個(gè)奇點(diǎn)，所以存在一個(gè)非閉的Euler鏈，可以一筆畫出。v5v6v4v2v1v3圖5-168二.最優(yōu)性條件

對(duì)于所走街巷圖正好是Euler圖的問題，找出Euler圈就是最優(yōu)的投遞路線。此時(shí)，街巷圖與路線圖是重合的。而當(dāng)遇到街巷圖不是Euler圖時(shí)，又如何定出最優(yōu)的投遞路線呢?這就是下述一般的優(yōu)化問題：

設(shè)有連通非負(fù)賦權(quán)圖G=(V,E,W)，R為含E中所有邊的圈。求圈R*，使其滿足：即要求一個(gè)含E中所有邊且總權(quán)為最小的圈。9

當(dāng)G中無奇點(diǎn)，問題已獲解。今設(shè)G有奇點(diǎn)，故而任一蘊(yùn)含E的R必含重復(fù)邊。此時(shí)，郵遞員難免要在某些街巷上走回頭路（回頭路，即重復(fù)邊。目的是為了改變點(diǎn)的度，使所有點(diǎn)的度都為偶數(shù)）。因此，問題的目標(biāo)就是使得重復(fù)邊的總權(quán)最小。此目標(biāo)達(dá)到與否的一種判別方法由下述定理給出。【定理11】設(shè)連通非負(fù)賦權(quán)圖G=(V,E,W)，R為包含E的圈。R

有最小總權(quán)的充分必要條件為：(1)每邊最多重復(fù)一次；(2)在G的每個(gè)初等圈(圈中各點(diǎn)不相同

)上，重復(fù)邊總權(quán)不超過圈總權(quán)的一半。10三.圖上作業(yè)法

從一筆畫問題的討論可知，一個(gè)郵遞員在他所負(fù)責(zé)投遞的街道范圍內(nèi)，如果街道構(gòu)成的圖中沒有奇點(diǎn)，那么他就可以從郵局出發(fā)，經(jīng)過每條街道一次，且僅一次，并最終回到原出發(fā)地。但是，如果街道構(gòu)成的圖中有奇點(diǎn)，他就必然要在某些街道重復(fù)走幾次。例如，在圖5-16表示的街道圖中，v1表示郵局所在地，每條街道的長度是1。11郵遞員可以按照以下的路線行走：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]上各走了兩次；按照第2條路線走，在邊[v3,v2],[v3,v5]上各走了兩次。如上面圖5-16（a）、圖5-16（b）所示。圖5-16(b)v1v3v2v4v6v5v2v6圖5-16(a)v1v3v4v5v5v6v4v2v1v3圖5-1612

在連通圖G中，如果在邊[vi,vj]上重復(fù)走了幾次，那么就在點(diǎn)vi,vj之間增加幾條相應(yīng)的邊，每條邊的權(quán)和原來的權(quán)相等，并把新增加的邊叫做重復(fù)邊。顯然，這條路線構(gòu)成新圖中的歐拉圈。如上面圖5-16(a)和圖5-16(b)所示。13

于是，中國郵遞員問題也可以表示為：在一個(gè)有奇點(diǎn)的連通圖中，要求增加一些重復(fù)邊，使得新的連通圖不含有奇點(diǎn)，并且增加的重復(fù)邊總權(quán)最小。我們把增加重復(fù)邊后不含奇點(diǎn)的新的連通圖叫做郵遞路線，而總權(quán)最小的郵遞路線叫做最優(yōu)郵遞路線。下面我們來介紹初始郵遞路線的確定，改進(jìn)，以及一個(gè)郵遞路線是否是最優(yōu)路線的判定標(biāo)準(zhǔn)的方法——圖上作業(yè)法。141.算法基本流程這里給出一種求解算法，步驟如下（共5步）：Step1:計(jì)算G的奇點(diǎn)數(shù)p0，當(dāng)p0=0時(shí)，R*為Euler圈；當(dāng)p0=2k(k=1,2,…,K；2K≤p)時(shí)，轉(zhuǎn)Step2。Step2:將奇點(diǎn)配成k對(duì)，每對(duì)之間確定一條鏈，再重復(fù)鏈上各邊，得一個(gè)多重Euler圖G(0)，存在Euler圈R(0)。Step3:檢驗(yàn)定理11中的最優(yōu)性條件1(每邊最多重復(fù)一次)：若滿足，則轉(zhuǎn)Step5,否則，轉(zhuǎn)Step4。15Step4:成對(duì)去掉同一邊上重復(fù)邊，使每邊最多有一條重復(fù)邊，得精簡后的Euler圖G(1)，存在Euler圈R(1)。Step5：檢驗(yàn)定理11中的最優(yōu)性條件2（按一定的搜索圈的方法，逐圈檢驗(yàn)圈上重復(fù)邊總權(quán)）：當(dāng)重復(fù)邊總權(quán)不大于圈總權(quán)之半，則保留原來的重復(fù)邊；當(dāng)重復(fù)邊總權(quán)大于圈總權(quán)之半，則去掉原來的重復(fù)邊而改為同圈的其余邊上添加重復(fù)邊。所有圈搜索并檢驗(yàn)完后，即得總權(quán)最小的Euler圖G*，存在Euler圈R*。162.郵遞員問題的算法（1）初始郵遞路線的確定方法由于任何一個(gè)圖中，奇點(diǎn)的個(gè)數(shù)為偶數(shù)，所以如果一個(gè)連通圖有奇點(diǎn)，就可以把它們兩兩配成對(duì)，而每對(duì)奇點(diǎn)之間必有一條鏈（圖是連通的），我們把這條鏈的所有邊作為重復(fù)邊追加到圖中去，這樣得到的新連通圖必?zé)o奇點(diǎn)，這就給出了初始投遞路線。17例如，在圖5-17中，v1是郵局所在地，并有四個(gè)奇點(diǎn)v2,v4,v6,v8,將它們兩兩配對(duì)，比如v2和v4為一對(duì)，v6和v8為一對(duì)。255944346443v1v8v7v2v3v4v5v6v9圖5-1718

在連接v2和v4的鏈中任取一條，比如鏈(v2,v1,v8,v7,v6,v5,v4）,

再加入重復(fù)邊[v2,v1],[v1,v8],[v8,v7],[v7,v6],[v6,v5],[v5,v4]；同樣，任取連接v6和v8的一條鏈(v8,v1,v2,v3,v4,v5,v6)，再加入重復(fù)邊[v8,v1],[v1,v2],[v2,v3],[v3,v4],[v4,v5],[v5,v6]。于是，得到圖5-17a。由于沒有奇點(diǎn)，故它是歐拉圖。對(duì)于這條郵遞路線，重復(fù)邊的總長為:2W12+W23+W34+2W45+2W56+W67+W78+2W18

=51v8255944346443v3v2v1v7v6v5v4v9圖5-17a19（2）改進(jìn)郵遞路線，使重復(fù)邊的總長不斷減少從圖5-17a中可以看出，在邊[v1,v2]旁邊有兩條重復(fù)邊，但是如果把他們都從圖中去掉，所得到的連通圖仍然無奇點(diǎn)，還是一個(gè)郵遞路線，而總長度卻有所減少。同理，在邊[v1,v8],[v4,v5],[v5,v6]旁邊的重復(fù)邊也是一樣的。20

判定標(biāo)準(zhǔn)1:

在最優(yōu)郵遞路線上，圖中的每一條邊至多有一條重復(fù)邊。按此判定標(biāo)準(zhǔn)，將圖5-17a改為圖5-17b，這時(shí)重復(fù)邊的總權(quán)減少為21。圖5-17b25594434v1v2v3v4v5v6v7v8v96434v8255944346443v3v2v1v7v6v5v4v9圖5-17a

一般地，在郵遞路線上，如果在邊[vi,vj]旁邊有兩條以上的重復(fù)邊，從中去掉偶數(shù)條，那么可以得到一個(gè)總長度較少的郵遞路線。21

不難看出，如果把圖中某個(gè)圈上的重復(fù)邊去掉，而給原來沒有重復(fù)邊的邊上加上重復(fù)邊，圖中仍然沒有奇點(diǎn)。因此，如果在某個(gè)圈上重復(fù)邊的總權(quán)大于這個(gè)圈總權(quán)的一半，按照以上所說的作一次調(diào)整，將會(huì)得到一個(gè)總權(quán)減少的郵遞路線。

判定標(biāo)準(zhǔn)2:在最優(yōu)郵遞路線上，圖中每一個(gè)圈的重復(fù)邊的總權(quán)小于或者等于該圈總權(quán)的一半。22比如在圖5-17b中，圈（v2,v3,v4,v9,v2）的總權(quán)為24，但圈上重復(fù)邊的總權(quán)為14，大于該圈總權(quán)的一半。圖5-17b25594434v1v2v3v4v5v6v7v8v9643425594434v1v2v3v4v5v6v7v8v96434圖5-17c因此作一次改進(jìn)，在該圈上去掉重復(fù)邊[v2,v3],[v3,v4],加上重復(fù)邊[v2,v9],[v9,v4]，如圖5-17c所示。這時(shí)重復(fù)邊的總權(quán)減少為10。23

在圖5-17c中，圈(v1,v2,v9,v6,v7,v8,v1)中重復(fù)邊總權(quán)為13，而該圈的總權(quán)為24，不滿足判定標(biāo)準(zhǔn)2。

再次經(jīng)過改進(jìn)后，得到圖5-17d。此時(shí)，該圈中重復(fù)邊的總權(quán)為11，小于該圈的總權(quán)24。25594434v1v2v3v4v5v6v7v8v96434圖5-17c25594434v1v2v3v4v5v6v7v8v96434圖5-17d

檢查圖5-17d中的每一個(gè)圈，判定標(biāo)準(zhǔn)1和2均已滿足。于是，圖中的歐拉圈就是最優(yōu)郵遞路線。24

從這個(gè)例子可知：一個(gè)最優(yōu)郵遞路線一定滿足判定標(biāo)準(zhǔn)1和判定標(biāo)準(zhǔn)2；反之，一個(gè)郵遞路線如果滿足判定標(biāo)準(zhǔn)1和判定標(biāo)準(zhǔn)2，那么它一定是最優(yōu)郵遞路線。即：這兩個(gè)判定標(biāo)準(zhǔn)是最優(yōu)郵遞路線判定的充分必要條件。值得注意的是，這個(gè)方法主要困難在于檢查判定標(biāo)準(zhǔn)2。它要求對(duì)于圖中的每一個(gè)圈都檢查一遍。當(dāng)一個(gè)連通圖所包含的圈數(shù)比較多時(shí)，將會(huì)大大提高運(yùn)算的工作量。到目前為止，關(guān)于中國郵遞員問題，已經(jīng)找到了更好的算法，由于篇幅所限，我們就不去介紹它了。255v3v8v7v6v5v4v2v1v9v13v12v11v10

31111112223336445例11求解圖5-15所示網(wǎng)絡(luò)的中國郵路問題圖5-15265v3v8v7v6v5v4v2v1v9v13v12v11v10

31111112223336445（1）找出奇點(diǎn)，配對(duì)并畫出相應(yīng)的重復(fù)邊。圖5-15a275v3v8v7v6v5v4v2v1v9v13v12v11v10

31111112223336445根據(jù)條件(1)每邊最多重復(fù)一次；成對(duì)去掉同一邊上重復(fù)邊，使每邊最多有一條重復(fù)邊，得圖5-15b：右圖同時(shí)滿足條件(2)，因此右圖就是最優(yōu)解。圖5-15b28例12（書P147例10）：如下圖所示之G是一幅街道，點(diǎn)v6表示郵局。求最優(yōu)投遞路線3v1v2v4v5v6G含兩個(gè)奇點(diǎn)v2,v4。29

取鏈{v2,v6,v5,v4},作重