01-中國郵遞員問題

中國郵遞員問題廈門大學數學科學學院金賢安

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

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

任取G的一個頂點v0,令W0=v0。Step2設Wi=v0e1v1

…eivi已取，在E-

{e1

，

e2，

…，ei}中取ei+1使ei+1與vi關聯；除非別無選擇ei+1不是Gi=G-{e1

，

e2，

…，ei}的橋。設vi+1是ei+1的另一個端點。在Wi上添加ei+1和vi+1得到Wi+1。Step 3

直到Step

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

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

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

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

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

1Step

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

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

1Step

2Step

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

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

1Step

2Step

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

1step

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

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

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