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

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

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

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

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

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

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

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