01-中國(guó)郵遞員問(wèn)題

中國(guó)郵遞員問(wèn)題廈門(mén)大學(xué)數(shù)學(xué)科學(xué)學(xué)院金賢安

引言中國(guó)郵遞員問(wèn)題是由山東師范大學(xué)管梅谷同志1960年首先提出的。這是數(shù)學(xué)中為數(shù)不多的幾個(gè)以“中國(guó)”命名的問(wèn)題或定理之一。該問(wèn)題涉及著名的的哥尼斯堡(K?nigsberg)七橋問(wèn)題。七橋問(wèn)題是圖論和拓?fù)鋵W(xué)的起源。

引言1哥尼斯堡七橋問(wèn)題2歐拉圖及判定定理3Fleury算法4中國(guó)郵遞員問(wèn)題5奇偶點(diǎn)圖上作業(yè)法6理論根據(jù)（選講）哥尼斯堡七橋問(wèn)題哥尼斯堡(K?nigsberg)今稱(chēng)加里寧格勒，建城于1255年，是位于波羅的海海岸的俄羅斯海港城市與加里寧格勒州的首府。加里寧格勒州位于波蘭北方、立陶宛西南，原為德國(guó)東普魯士一部分，現(xiàn)為俄羅斯的外飛地。圖1 加里寧格勒哥尼斯堡七橋問(wèn)題圖2 哥尼斯堡七橋示意圖有一條普雷格爾(Pregel)河流經(jīng)哥尼斯堡，河上有七個(gè)橋。哥尼斯堡七橋問(wèn)題一個(gè)散步者能否從某處出發(fā)走遍七個(gè)橋且每個(gè)橋只走一次，最后回到出發(fā)點(diǎn)？哥尼斯堡七橋問(wèn)題大數(shù)學(xué)家歐拉在1736年解決了這個(gè)問(wèn)題。哥尼斯堡七橋問(wèn)題萊昂哈德·歐拉（LeonhardEuler，1707年4月15日－1783年9月18日）瑞士數(shù)學(xué)家和物理學(xué)家，近代數(shù)學(xué)先驅(qū)之一。歐拉是18世紀(jì)數(shù)學(xué)界最杰出的人物之一。歐拉是科學(xué)史上最多產(chǎn)的一位杰出的數(shù)學(xué)家，據(jù)統(tǒng)計(jì)他那不倦的一生，共寫(xiě)下了886本書(shū)籍和論文。30歲左右右眼幾乎完全失明，60歲左右左眼又幾乎完全失明。在1775年，他平均每周就完成一篇數(shù)學(xué)論文。1783年9月18日于俄國(guó)彼得堡去逝。歐拉Euler(1707-1783)哥尼斯堡七橋問(wèn)題A將上圖中A，B，C和D這四個(gè)B 區(qū)域各看成一個(gè)頂點(diǎn)，兩區(qū)域之間有一個(gè)橋相連，就將相應(yīng)的兩個(gè)頂點(diǎn)連一條邊，得到一個(gè)圖。CD圖3 七橋問(wèn)題對(duì)應(yīng)圖歐拉Euler(1707-1783)歐拉圖及判定定理哥尼斯堡問(wèn)題即圖3是否是歐拉圖的問(wèn)題。A給定一個(gè)連通圖，我們稱(chēng)經(jīng)過(guò)圖的所有邊一次且只有一次的走法為一個(gè)歐拉通路。如果進(jìn)一步該走法還回到出發(fā)點(diǎn)，則稱(chēng)之為歐拉環(huán)游（回路）。具有歐拉環(huán)游的圖稱(chēng)之為歐拉圖。CBD圖3 七橋問(wèn)題對(duì)應(yīng)圖歐拉圖及判定定理一筆畫(huà)問(wèn)題：什么樣的圖形可以一筆畫(huà)成，筆不離紙，而且每條線都只畫(huà)一次不準(zhǔn)重復(fù)？如果一個(gè)連通圖有歐拉環(huán)游，即從某個(gè)頂點(diǎn)出發(fā)，經(jīng)過(guò)該圖所有邊一次，且不重復(fù)，最后回到出發(fā)點(diǎn)，則對(duì)中間經(jīng)過(guò)的任一頂點(diǎn)都是一進(jìn)一出，而出發(fā)點(diǎn)開(kāi)始出去最后又進(jìn)來(lái)，也是一進(jìn)一出。注意有的頂點(diǎn)可能有若干次一進(jìn)一出。不論如何，都意味著該圖的每個(gè)頂點(diǎn)都應(yīng)該是偶點(diǎn)（即進(jìn)出總共偶數(shù)條邊）。頂點(diǎn)可能重復(fù)經(jīng)過(guò)一次 且不重復(fù)偶點(diǎn)一進(jìn)一出歐拉圖及判定定理歐拉圖及判定定理定理1（判定定理）一個(gè)連通圖是歐拉圖當(dāng)且僅當(dāng)它的所有點(diǎn)都是偶點(diǎn)。思考1：如何證明充分性？對(duì)邊數(shù)用歸納法。設(shè)連通圖G的所有點(diǎn)都是偶點(diǎn)，則G中必定有圈C。G-E(C)的每個(gè)連通分支的每個(gè)頂點(diǎn)都是偶點(diǎn)，由歸納假設(shè)，都是歐拉圖，有歐拉環(huán)游。這些歐拉環(huán)游連同C如上圖所示將一起構(gòu)成G的一個(gè)歐拉環(huán)游。定理1（判定定理）C1C2C3C歐拉圖及判定定理Fleury算法下一步不能走⑨，為什么？①③④思考2：給定歐拉圖，如何找一歐拉環(huán)游呢？⑤ ⑥② ⑦⑧輸入：歐拉圖GStep 1

任取G的一個(gè)頂點(diǎn)v0,令W0=v0。Step2設(shè)Wi=v0e1v1

…eivi已取，在E-

{e1

，

e2，

…，ei}中取ei+1使ei+1與vi關(guān)聯(lián)；除非別無(wú)選擇ei+1不是Gi=G-{e1

，

e2，

…，ei}的橋。設(shè)vi+1是ei+1的另一個(gè)端點(diǎn)。在Wi上添加ei+1和vi+1得到Wi+1。Step 3

直到Step

2不能執(zhí)行時(shí)為止。輸出：WmFleury算法Fleury算法思考3：如何證明Fleury算法是可行的呢？中國(guó)郵遞員問(wèn)題是郵遞員在某一片區(qū)的信件投遞路程問(wèn)題。郵遞員每天從郵局出發(fā)，走遍片區(qū)所有街道再返回郵局，問(wèn)題是他應(yīng)如何安排送信的路線可以使所走的總路程最短。中國(guó)郵遞員問(wèn)題以交叉路口為頂點(diǎn)，街道為邊，街道的長(zhǎng)度為邊的權(quán)得到一賦權(quán)圖，我們稱(chēng)之為街道圖。不妨設(shè)郵局在一條街道上。若街道圖是歐拉圖，有歐拉環(huán)游，無(wú)需重復(fù)走街道，沿著一個(gè)歐拉環(huán)游作為投遞路線即可。中國(guó)郵遞員問(wèn)題若街道圖不是歐拉圖，則有些街道需要重復(fù)走，那么中國(guó)郵遞員問(wèn)題就變?yōu)椋褐貜?fù)走哪些街道，使總路程最短？中國(guó)郵遞員問(wèn)題用圖的語(yǔ)言來(lái)講，將街道圖中那些邊通過(guò)添加平行邊使之成為歐拉圖，并使得添加的平行邊的總長(zhǎng)度最短？給一個(gè)連通賦權(quán)圖（權(quán)都是正的）即街道圖。通過(guò)添加一些平行邊，其中添加的平行邊的權(quán)與原邊相同，使原圖變?yōu)闅W拉圖。求添加的平行邊的總長(zhǎng)度最短的添加方式。中國(guó)郵遞員問(wèn)題將使街道圖成為歐拉圖所添加的平行邊稱(chēng)為一個(gè)可行方案，添加的平行邊總長(zhǎng)度最短的可行方案為最優(yōu)方案。那么不難看出：(1)

在最優(yōu)方案中，對(duì)街道圖的任意一邊，所添加的平行邊的次數(shù)不會(huì)超過(guò)1。事實(shí)上，若在某可行方案中，對(duì)街道圖的某邊，所添加的平行邊的次數(shù)大于等于2，那么在該方案中去掉該邊2次，將得到一個(gè)新的更優(yōu)的可行方案，矛盾。奇偶點(diǎn)圖上作業(yè)法(2)

在最優(yōu)方案中，對(duì)街道圖的任意一個(gè)圈，圈上添加平行邊的邊的長(zhǎng)度之和應(yīng)該不超過(guò)不加平行邊的邊的長(zhǎng)度之和。事實(shí)上，若在最優(yōu)方案中，對(duì)街道圖的某個(gè)圈，圈上添加平行邊的邊的長(zhǎng)度之和大于不加平行邊的邊的長(zhǎng)度之和。那么將該圈上要添加平行邊的邊改成不添加；不添加平行邊的邊改成添加，則得到一個(gè)新的更優(yōu)的方案，矛盾。奇偶點(diǎn)圖上作業(yè)法奇偶點(diǎn)圖上作業(yè)法按下面步驟先給出一個(gè)可行方案Step

1管梅谷證明了滿足上述兩個(gè)條件的可行方案是最優(yōu)方案并據(jù)此給出了奇偶點(diǎn)圖上作業(yè)法。Step

1按下面步驟先給出一個(gè)可行方案找出圖的所有奇點(diǎn)將奇點(diǎn)任意兩兩配對(duì)找出各對(duì)奇點(diǎn)間的一條走法將每條走法上的邊都加上平行邊奇偶點(diǎn)圖上作業(yè)法判斷該可行方案是否最優(yōu)，即驗(yàn)證先給出一個(gè)可行方案Step

1Step

2奇偶點(diǎn)圖上作業(yè)法Step

2 判斷該可行方案是否最優(yōu)，即驗(yàn)證每條邊所添加的平行邊的條數(shù)不超過(guò)1每個(gè)圈上添加平行邊的邊的總長(zhǎng)度不超過(guò)不加平行邊的邊的總長(zhǎng)度奇偶點(diǎn)圖上作業(yè)法Step

1Step

2Step

3不是最優(yōu)方案最優(yōu)方案奇偶點(diǎn)圖上作業(yè)法Step

3 按下面的方法調(diào)整方案得到一個(gè)更優(yōu)的可行方案若一條邊添加的平行邊數(shù)大于等于2，則去掉偶數(shù)條使其至多只有一條平行邊若有一圈平行邊的總長(zhǎng)度超過(guò)非平行邊的總長(zhǎng)度，則將該圈上平行邊改為非平行邊，非平行邊改為平行邊奇偶點(diǎn)圖上作業(yè)法Step

1Step

2Step

3不是最優(yōu)方案最優(yōu)方案新的可行方案奇偶點(diǎn)圖上作業(yè)法圖上作業(yè)法主要困難在于要檢驗(yàn)街道圖的所有圈是否滿足條件(2)，而當(dāng)街道圖比較復(fù)雜時(shí)，圈的數(shù)目會(huì)很大。74122243例：2 353step

1step

3奇偶點(diǎn)圖上作業(yè)法step

21973年Edmonds和Johnson給出了中國(guó)郵遞員問(wèn)題的一個(gè)更好的解決方法。奇偶點(diǎn)圖上作業(yè)法理論依據(jù)（選講）引理1：歐拉圖的邊集是一些邊不交的圈的邊的并。思考：如何證明？設(shè)G是歐拉圖，取它的一個(gè)歐拉環(huán)游，從一個(gè)頂點(diǎn)出發(fā)沿歐拉環(huán)游前進(jìn)，第一次遇到頂點(diǎn)重復(fù)時(shí)，形成一個(gè)圈，去掉該圈上的邊，繼續(xù)前行，再次遇到頂點(diǎn)重復(fù)時(shí)，形成另一個(gè)圈，該圈與前面的圈邊不交，去掉該圈上的邊，繼續(xù)前行，以此類(lèi)推可證。定理2：若兩個(gè)可行方案a,b（都是街道圖的邊子集）都滿足上述兩個(gè)條件，則這兩個(gè)方案的邊的總長(zhǎng)度相同。理論依據(jù)（選講）由于滿足條件(1)，a和b都是街道圖的邊集的子集，不會(huì)是多重的。設(shè)原街道圖為G，則G+a和G+b都是歐拉圖。設(shè)c是a和b的公共邊，即c=a∩b。令G'=G[a+b-c]，則在G'的任意一個(gè)圈上，由條件(2)，a中邊的總長(zhǎng)度等于b中邊的總長(zhǎng)度（為什么？）。另一方面，G'的每個(gè)頂點(diǎn)都是偶點(diǎn)，因此G'是由一些邊不交的圈構(gòu)成的（引理1）。這就得到a-c和b-c的邊的總長(zhǎng)度相同，因此兩個(gè)可行方案的邊的總長(zhǎng)度相同。理論依據(jù)（選講）推論:

滿足上述兩個(gè)條件的可行方案是最優(yōu)方案。證明:設(shè)a是任意一個(gè)滿足上述兩條件的一個(gè)可行方案，b是最優(yōu)方案。由b是最優(yōu)方案可得b也滿足上述兩條件。由定理2，a和b這兩個(gè)方案的邊的總長(zhǎng)度相同因此