關(guān)于的中國的郵遞員問地的題目和歐拉圖地的應(yīng)用

1、實用標準文案關(guān)于中國郵遞員問題和歐拉圖應(yīng)用中國郵遞員問題：1962年有管梅谷先生提出中國郵遞員問題（簡稱 CPP）。一個郵遞員從郵局出發(fā)，要走完他所管轄的每一條街道， 可重復(fù)走一條街道，然后返回郵局。任何選擇一條盡可能短的路線。 這個問題可以轉(zhuǎn)化為：給定一個具有非負權(quán)的賦權(quán)圖G，（1 ）用添加重復(fù)邊的方法求G的一個Euler賦權(quán)母圖G*，使得盡可能小。（2 ）求G*的Euler環(huán)游。人們也開始關(guān)注另一類似問題，旅行商問題（簡稱TSP）。TSP是點路優(yōu)化問題，它是 NPC的。而CPP是弧路優(yōu)化問題，該問題有幾種變形，與加權(quán)圖奇點的最小完全匹配或網(wǎng)絡(luò)流等價，有多項式算法。1歐拉圖：圖G中經(jīng)過每條邊

2、一次并且僅一次的回路稱作歐拉回路。存在歐拉回路的圖稱為歐拉圖。無向圖歐拉圖判定：無向圖G為歐拉圖，當且僅當 G為連通圖且所有頂點的度為偶數(shù)。有向圖歐拉圖判定：有向圖G為歐拉圖，當且僅當 G的基圖2連通，且所有頂點的入度等于出度。歐拉回路性質(zhì)：性質(zhì)1設(shè)C是歐拉圖G中的一個簡單回路，將C中的邊從圖G中刪去得到一個新的圖 G 則G 的每一個極大連通子圖都有一條歐拉回路。性質(zhì)2 設(shè)C1、C2是圖G的兩個沒有公共邊，但有至少一個公共頂點的簡單回路，我們可以將它們合并成一個新的簡單回路C。歐拉回路算法:1在圖G中任意找一個回路 C;2將圖G中屬于回路C的邊刪除；3在殘留圖的各極大連通子圖中分別尋找歐拉回路

3、；4將各極大連通子圖的歐拉回路合并到C中得到圖G的歐拉回路。由于該算法執(zhí)行過程中每條邊最多訪問兩次，因此該算法的時間復(fù)雜度為0(|E|)。如果使用遞歸形式，得注意|E|的問題。使用非遞歸形式防止棧溢出。如果圖 是有向圖，我們?nèi)匀豢梢允褂靡陨纤惴?。有向圖歐拉圖和半歐拉圖判定 On li ne/problem?id=2337輸出路徑中國郵遞員問題：一個郵遞員從郵局出發(fā)，要走完他所管轄的每一條街道，可重復(fù)走一條街道，然后返回郵局。所有街道都是雙向通行的，且每條街道都有一個長度值。任何選擇一條盡可能短的路線。分析：雙向連通，即給定無向圖 G。如果G不連通，則無解。如果G是歐拉圖，則顯然歐拉回路就是最優(yōu)

4、路線。如果G連通，但不是歐拉圖，說明圖中有奇點3。奇點都是成對出現(xiàn)的，證明從略。對于最簡單情況，即 2個奇點，設(shè)（u, v ）。我們可以在 G中對（u , v）求最短路徑R,構(gòu) 造出新圖G = G U R。此時G就是歐拉圖。證明：u和v加上了一條邊，度加一，改變了奇偶性。而R中其他點度加二，奇偶性不變。由此可知，加一次 R,能夠減少兩個奇點。推廣到 k個奇點的情況，加 k/2個R就能使度 全為偶數(shù)。接下的問題是求一個k個奇點的配對方案，使得k/2個路徑總長度最小。這個就是無向完全圖最小權(quán)匹配問題。有一種Edmonds算法，時間復(fù)雜度 0 ( “鋁)。4也可轉(zhuǎn)換為二分圖，用松弛優(yōu)化的KM算法，時

5、間復(fù)雜度也是 0 (NT )。完整的算法流程如下:1 如果G是連通圖，轉(zhuǎn)2，否則返回無解并結(jié)束;2 檢查G中的奇點，構(gòu)成圖 H的頂點集;3 求出G中每對奇點之間的最短路徑長度，作為圖 H對應(yīng)頂點間的邊權(quán);4 對H進行最小權(quán)匹配;5 把最小權(quán)匹配里的每一條匹配邊代表的路徑，加入到圖G中得到圖G6 在G中求歐拉回路，即所求的最優(yōu)路線。中國郵遞員問題：和相似，只是所有街道都是單向通行的。分析：單向連通，即給定有向圖 G。和的分析一樣，我們來討論如何從G轉(zhuǎn)換為歐拉圖G首先計算每個頂點 v的入度與出度之差 d （ v）。如果G中所有的v都有d （ v）=0 ,那么G中已經(jīng)存在歐拉回路。d （ v）0說明

6、得加上出度。d （ v）0說明得加上入度。而當d （v）=0 ,則不能做任何新增路徑的端點。可以看出這個模型很像網(wǎng)絡(luò)流模型。頂點d （ v）0對應(yīng)于網(wǎng)絡(luò)流模型中的源點，它發(fā)出d （v）個單位的流；頂點 d （ v）0的頂點v連邊(s,v)，容量為d (v)，費用為0 ;4 從所有d (v)0的頂點向匯點t連邊(u,t)，容量為-d (v)，費用為0。完整的算法流程如下：1 如果G的基圖連通且所有頂點的入、出度均不為0,轉(zhuǎn)2 ,否則返回無解并結(jié)束;2 計算所有頂點v的d (v)值；3 構(gòu)造網(wǎng)絡(luò)N ;4 在網(wǎng)絡(luò)N中求最小費用最大流；5 對N中每一條流量f(u,v)的邊(u,v)，在圖G中增加f(u

7、,v)次得到G ;6 在G中求歐拉回路，即為所求的最優(yōu)路線。NPC問題：如果部分街道能夠雙向通行，部分街道只能單向通行。這個問題已被證明是NPC的。5精彩文檔1 大城市郵政投遞問題及其算法研討2 忽略有向圖所有邊的方向，得到的無向圖稱為該有向圖的基圖。3 度為奇數(shù)的頂點稱為奇點。4 J. Edmon ds, E. Joh nsonM atch ing, Euler tours, and the Chin ese postma n5 C. PapadimitriouThe complexity of edge travers ing中國郵遞員問題的 C+實現(xiàn)源代碼/PKU 2337#in clu

8、de #in clude #in clude #in clude #i nclude using n amespace std;con st int MAX = 1100; char strMAX25;int n, i nMAX, outMAX;vector words30;in t vis30;int f30, ss, is, os, ps;int seqMAX, step;void fin d_euler(i nt pos)int i,j;while(outpos) .for(; vispos = 0) .fe = s;int mai n().int t,i,j;scanf(%d, &t)

9、;while(t -) .scan f(%d, &n);getchar();for(i=0;i30;i+) wordsi.clear(); memset(i n, O,sizeof( in);memset(out,0,sizeof(out); memset(f,-1,sizeof(f);ss = is = os = ps = 0;for(i=0;i n ;i+) .gets(stri);int len = strle n(stri);int chs = striO -a;int che = strile n-1 - a; wordschs.push_back(stri ng(stri); in che +;outchs +;union _f(chs, che);bool flag = true;for(i=0;i 1) flag = false;if( !(os=0 & is=0) & !(os=1 & is=1) ) flag = false; if(!flag) .puts(*);else .int spos;if(os = 1 & is = 1) .for(i=0;i30;i+).if(i ni