圖論與特殊圖概述

圖論圖論什么是圖?ABCD哥尼斯堡七橋示意圖問題1(哥尼斯堡七橋問題):

能否從任一陸地出發(fā)通過每座橋恰好一次而回到出發(fā)點？ABDC七橋問題模擬圖歐拉指出：如果每塊陸地所連接的橋都是偶數(shù)座，則從任一陸地出發(fā)，必能通過每座橋恰好一次而回到出發(fā)地.(——著名的歐拉圖問題)問題2(哈密頓環(huán)球旅行問題):

十二面體的20個頂點代表世界上20個城市，能否從某個城市出發(fā)在十二面體上依次經(jīng)過每個城市恰好一次最后回到出發(fā)點？哈密頓圈（環(huán)球旅行游戲）問題3(四色問題):

對任何一張地圖進(jìn)行著色，兩個共同邊界的國家染不同的顏色，則只需要四種顏色就夠了.問題4(關(guān)鍵路徑問題):

一項工程任務(wù),大到建造一座大壩,一座體育中心,小至組裝一臺機(jī)床,一架電視機(jī),都要包括許多工序.這些工序相互約束,只有在某些工序完成之后,一個工序才能開始.即它們之間存在完成的先后次序關(guān)系,一般認(rèn)為這些關(guān)系是預(yù)知的,而且也能夠預(yù)計完成每個工序所需要的時間.

這時工程領(lǐng)導(dǎo)人員迫切希望了解最少需要多少時間才能夠完成整個工程項目,影響工程進(jìn)度的要害工序是哪幾個？圖論的基本概念

圖論中的“圖”并不是通常意義下的幾何圖形或物體的形狀圖,而是以一種抽象的形式來表達(dá)一些確定的事物之間的聯(lián)系的一個數(shù)學(xué)系統(tǒng).

定義1一個有序二元組(V,E)稱為一個圖,記為G=(V,E),其中

①V稱為G的頂點集,V≠,其元素稱為頂點或結(jié)點,簡稱點;②

E稱為G的邊集,其元素稱為邊,它聯(lián)結(jié)V中的兩個點,如果這兩個點是無序的,則稱該邊為無向邊,否則,稱為有向邊.

如果V={v1,v2,…,vn}是有限非空點集,則稱G為有限圖或n階圖.

如果E的每一條邊都是無向邊,則稱G為無向圖(如圖1);

如果E的每一條邊都是有向邊,則稱G為有向圖(如圖2);

否則,稱G為混合圖.圖1圖2并且常記V={v1,v2,…,vn},|V|

=n;E={e1,e2,…,em}(ek=vivj),|E|

=m.稱點vi,vj為邊vivj的端點.在有向圖中,稱點vi,vj分別為邊vivj的始點和終點.

對于一個圖G=(V,E),人們常用圖形來表示它,

稱其為圖解.

凡是有向邊,

在圖解上都用箭頭標(biāo)明其方向.

例如,設(shè)V={v1,v2,v3,v4},E={v1v2,v1v3,v1v4,v2v3,v2v4,v3v4},則G=(V,E)是一個有4個頂點和6條邊的圖,G的圖解如下圖所示.歐拉圖歐拉回路歐拉回路問題是圖論中最古老的問題之一。它誕生于十八世紀(jì)的歐洲古城哥尼斯堡。普瑞格爾河流經(jīng)這座城市，人們在兩岸以及河中間的兩個小島之間建了七座橋（如圖1）。于是產(chǎn)生了這樣一個問題：是否可以找到一種方案，使得人們從自己家里出發(fā)，不重復(fù)地走遍每一座橋，然后回到家中？這個問題如果用數(shù)學(xué)語言來描述，就是在圖2中找出一條回路，使得它不重復(fù)地經(jīng)過每一條邊。這便是著名的“哥尼斯堡七橋問題”。圖1圖2歐拉圖歐拉回路無數(shù)熱衷于此的人試圖解決這個問題，但均以失敗告終。問題傳到了歐拉（LeonhardEuler,1707-1783）那里，立即引起了這位大數(shù)學(xué)家的重視。經(jīng)過悉心研究，歐拉終于在1736年發(fā)表了論文《哥尼斯堡的七座橋》，不但成功地證明了“七橋問題”無解，而且找到了對于一般圖是否存在這類回路的充要條件。后人為了紀(jì)念歐拉這位偉大的數(shù)學(xué)家，便將這類回路稱為歐拉回路。歐拉圖歐拉回路首先介紹相關(guān)概念和定理。設(shè)是一個圖。

歐拉通路(回路)：通過圖G（無向圖或有向圖）中所有邊一次且僅一次行遍圖中所有頂點的通路(回路)稱為歐拉通路(回路)。歐拉圖與半歐拉圖：具有歐拉回路的圖稱為歐拉圖，具有歐拉通路而無歐拉回路的圖稱為半歐拉圖。橋：設(shè)無向圖G=<V,E>，若存在邊集E的一個非空子集E1，使得p(G-E1)>p(G)，而對于E1的任意真子集E2，均有p(G-E2)=p(G)，則稱E1是G的邊割集，或簡稱割集；若E1是單元集，即E1={e}，則稱e為割邊或橋。[p(G)表示圖G的連通分支數(shù).]

圖中,(3)不是歐拉圖,(4)是歐拉圖.例是歐拉圖；不是歐拉圖，但存在歐拉通路；即不是歐拉圖，也不存在歐拉通路。例1、(螞蟻比賽問題)甲、乙兩只螞蟻分別位于如下圖中的結(jié)點a，b處，并設(shè)圖中的邊長度是相等的。甲、乙進(jìn)行比賽：從它們所在的結(jié)點出發(fā)，走過圖中的所有邊最后到達(dá)結(jié)點c處。如果它們的速度相同，問誰先到達(dá)目的地？例2、一筆畫問題無向歐拉圖的判定無向圖存在歐拉回路的充要條件：

連通且沒有奇點。無向圖存在歐拉路徑的充要條件：

連通且奇點個數(shù)為2。(1)既無歐拉回路,也無歐拉通路.(2)中存在歐拉通路,但無歐拉回路.(3)中存在歐拉回路.圖a)存在一條歐拉通路：v3v1v2v3v4v1；圖(b)中存在歐拉回路v1v2v3v4v1v3v1，因而(b)是歐拉圖；圖(c)中有歐拉回路v1v2v3v4v5v6v7v8v2v4v6v8v1因而(c)是歐拉圖。有向歐拉圖的判定有向圖存在歐拉回路的充要條件：

基圖連通且所有頂點入度等于出度。有向圖存在歐拉路徑的充要條件：

基圖連通且存在某頂點入度比出度大1，另一頂點出度比入度大1，其余頂點入度等于出度。歐拉回路存在性的判斷歐拉回路問題可以分為無向圖中的歐拉回路和歐拉通路，有向圖中的歐拉回路和歐拉通路。這幾個問題大抵相像。有向歐拉回路有：定理：假設(shè)有像多重圖D有性質(zhì)：當(dāng)忽略有向邊上的方向時，得到的圖是連通的，那么D有有向歐拉回路當(dāng)且僅當(dāng)D的每個頂點的入度和出度相等。類似的，對有向歐拉通路有：定理：D有有向歐拉通路，當(dāng)且僅當(dāng)除兩個不同頂點B和C之外，D的其它頂點的入度和出度相等，且B的出度比入度大1，C的入度比出度大1。在這種情況下，有向歐拉通路自B出發(fā)，至C終止。由上面的定理可以知道，如果要判斷一個有向圖的歐拉回路是否存在，需要先判斷連通性，再判斷出度入度。對于無向圖，判斷方法類似。判斷連通性可以通過DFS或者并查集來實現(xiàn)。求無向圖歐拉回路的算法在圖中任意找一個回路C；將圖中屬于C的邊刪除；在殘留圖的各個極大連通分量中求歐拉回路；將各極大連通分量中的歐拉回路合并到C上。歐拉回路的構(gòu)建在構(gòu)建歐拉回路之前需要判斷歐拉回路是否存在。構(gòu)建歐拉回路可以使用Fleury算法（能不走橋就不走橋）：Fleury算法：（1）任取v0∈V(G)，令P0=v0；（2）設(shè)Pi=v0e1v1e2...eivi已經(jīng)行遍，按下面方法來從E(G)-{e1,e2,...,ei}中選取ei+1：

（a）ei+1與vi想關(guān)聯(lián)；

（b）除非無別的邊可供行遍，否則ei+1不應(yīng)該為Gi=G-{e1,e2,...,ei}中的橋.（3）當(dāng)（2）不能再進(jìn)行時，算法停止?？梢宰C明，當(dāng)算法停止時所得簡單回路Pm=v0e1v1e2...emvm（vm=v0）為G中的一條歐拉回路。構(gòu)建歐拉回路的Fleury算法可以實用DFS來實現(xiàn)。算法的圖示動態(tài)過程：歐拉算法描述

voidDFS(Graph&G,SqStack&S,intx,intt){

k=0;//一個標(biāo)志,來標(biāo)記當(dāng)前訪問的節(jié)點是否還有鄰接邊可供訪問

Push(S,x);//將本次遍歷邊所經(jīng)由的點入棧

for(i=t;i<v;i++)//v是頂點數(shù),e是邊數(shù)

if(G[i][x]>0)

{

k=1;

G[i][x]=0;G[x][i]=0;//此邊已訪問,刪除此邊

DFS(G,S,i,0);//尋找下一條關(guān)聯(lián)的邊,本次找到的是與x關(guān)聯(lián)的i,在

//下一層中將尋找與i關(guān)聯(lián)的邊

break;

}//if,for歐拉算法描述

if(k==0)

//如果k=0,說明與當(dāng)前頂點關(guān)聯(lián)的邊已窮盡

{

Pop(S);

GetTop(S,m);

G[x][m]=1;G[m][x]=1;//恢復(fù)在上一層中被刪除的邊

a=x+1;//如果可能的話,從當(dāng)前節(jié)點的下一條關(guān)聯(lián)邊開始搜尋

if(StackLength(S)!=e)//繼續(xù)搜尋,邊還沒有全部遍歷完

{

Pop(S);//還原到上一步去

DFS(G,S,m,a);//

}//if

else

//搜尋完畢,將最后節(jié)點也入棧

Push(S,x);

}//if}//DFS歐拉算法描述

voidEuler(Graph&G,intx){//G是存儲圖的鄰接矩陣,都處理成無向圖形式,值為1代表有邊,0代表無邊,不包括自回路,x是出發(fā)點InitStack(S);//用來存放遍歷邊時依次走過的頂點DFS(G,S,x,0);//深度優(yōu)先遍歷查找,0是指查詢的起點//輸出

while(!StackEmpty(S))

{

GetTop(S,m);

printf("->v%d",m);

Pop(S);

}//while}//Euler例題一單詞游戲有N個盤子，每個盤子上寫著一個僅由小寫字母組成的英文單詞。你需要給這些盤子按照合適的順序排成一行，使得相鄰兩個盤子中，前一個盤子上面單詞的末字母等于后一個盤子上面單詞的首字母。請你編寫一個程序，判斷是否能達(dá)到這一要求。如果能，請給出一個合適的順序。樣例malformmouseacm樣例malformmouseacmmmmm模型以26個英文字母作為頂點。對于每一個單詞，在圖中從它的首字母向末字母連一條有向邊。模型問題轉(zhuǎn)化為在圖中尋找一條不重復(fù)地經(jīng)過所有邊的路徑，即歐拉路徑。這個問題能夠在O(|E|)時間內(nèi)解決。實例：PKU2337問題描述給出一些字符串，讓你首尾串起來串成一串，并且輸出一個字典序最小的方案。如果不能，輸出“***”。否則輸出字典序最小的回路。輸入26alohaarachniddoggopherrattiger3oakmapleelm輸出aloha.arachnid.dog.gopher.rat.tiger***實例：PKU2337在沒有特殊要求的情況下，DFS遍歷圖的結(jié)點順序是可以任選的。但是這里由于加上了字典序最小的要求，所以DFS遍歷時需要按照以下的優(yōu)先順序：1.如果有不是橋的邊，遍歷這些邊中字典序最小的邊。2.否則，遍歷這些這些橋中字典序最小的邊。比如一個單詞，abcde，那么就連接一條a到e的有向邊。如此構(gòu)成的圖一共最多有26個節(jié)點。每條邊都代表一個單詞，那么就轉(zhuǎn)化成了：找一條路，遍歷所有的邊。就是歐拉通路問題。遍歷歐拉通路的方法：確定一個起點（出度-入度=1，或者等于0（如果存在歐拉回路的話））從起點開始深搜（首先要保證圖中存在歐拉回路或者通路）dfs(vid,eid)其中vid表示當(dāng)前搜到的點。eid表示當(dāng)前搜到的邊（一個點可能會有很多邊）對于每條邊，都是等它搜索完了后，把它代表的內(nèi)容（這里是單詞）壓入一個棧中。最后深搜結(jié)束后，依次彈棧就是答案。DoorMan

(SouthCentralUSA2002)大意：給定N(<=20)個房間,房間之間有門相隔，門的數(shù)目不超過100道，當(dāng)前人在第M個房門，當(dāng)前人每經(jīng)過一道門的時候就把經(jīng)過的門鎖上，問有沒有一條路可以使得我們走到第0個房門的時候所有的門都鎖上了。思路：我們可以把門看成是兩個房間之間的邊，那么問題可以轉(zhuǎn)化成找一條歐拉路徑。PS：判斷的時候只要判斷所有的邊在一起就行了，所有的點不一定連通，當(dāng)0點和M點不連通的時候，無解。注意這組數(shù)據(jù)。最短路

定義1

設(shè)P(u,v)是賦權(quán)圖G=(V,E,F)中從點u到v的路徑,用E(P)表示路徑P(u,v)中全部邊的集合,記則稱F(P)為路徑P(u,v)的權(quán)或長度(距離).

定義2

若P0(u,v)是G

中連接u,v的路徑,且對任意在G

中連接u,v的路徑P(u,v)都有F(P0)≤F(P),則稱P0(u,v)是G

中連接u,v的最短路.重要性質(zhì)：

若v0v1…vm是圖G中從v0到vm的最短路,則1≤k≤m,v0v1…vk必為G中從v0到vk的最短路.

即：最短路是一條路，且最短路的任一段也是最短路.

求非負(fù)賦權(quán)圖G中某一點到其它各點最短路，一般用Dijkstra標(biāo)號算法；求非負(fù)賦權(quán)圖上任意兩點間的最短路，一般用Floyd算法.這兩種算法均適用于有向非負(fù)賦權(quán)圖.Bellman-ford算法算法簡單介紹

這個算法能在更一般的情況下解決最短路的問題。何謂一般，一般在該算法下邊的權(quán)值可以為負(fù)，可以運用該算法求有向圖的單元最長路徑或者最短路徑。適用條件:任意邊權(quán)為實數(shù)的圖Bellman-Ford算法Bellman-Ford算法的思想基于以下事實：“兩點間如果有最短路，那么每個結(jié)點最多經(jīng)過一次。也就是說，這條路不超過n-1條邊。”（如果一個結(jié)點經(jīng)過了兩次，那么我們走了一個圈。如果這個圈的權(quán)為正，顯然不劃算；如果是負(fù)圈，那么最短路不存在；如果是零圈，去掉不影響最優(yōu)值）Bellman-Ford算法的運行時間為O(VE)。很多時候，我們的算法并不需要運行|V|-1次就能得到最優(yōu)值。對于一次完整的第3-4行操作，要是一個結(jié)點的最短路徑估計值也沒能更新，就可以退出了。經(jīng)過優(yōu)化后，對于多數(shù)情況而言，程序的實際運行效率將遠(yuǎn)離O(VE)而變?yōu)镺(kE)，其中k是一個比|V|小很多的數(shù)。算法簡單介紹Bellmanford類似于Dijkstra算法，對每一個節(jié)點v，逐步減小從起點s到終點v最短路的估計量dist[v]直到其達(dá)到真正的最短路徑值mindist[v]。Bellman-ford算法同時返回一個布爾值，如果不存在從源結(jié)點可達(dá)的負(fù)權(quán)回路，算法返回布爾值TRUE，反之返回FALSE。算法具體流程枚舉每條邊(u,v)∈E（G）。對枚舉到的邊進(jìn)行一次松弛操作?；氐讲襟E1，此過程重復(fù)n-1次，以確定沒有可以更優(yōu)化的情況。枚舉每條邊（u，v）若仍然存在可以更新的邊，則說明有向圖中出現(xiàn)了負(fù)權(quán)回路，于是返回布爾值FALSE。否則返回布爾值TRUE。voidBellman_ford(void){inti,j,k;for(i=1;i<=C;i++)Dist[i]=INF;Dist[S]=0;for(i=1;i<=C-1;i++){for(j=1;j<=C;j++)for(k=1;k<=C;k++)if(Dist[k]>Dist[j]+Graph[j][k])Dist[k]=Dist[j]+Graph[j][k];}for(j=1;j<=C;j++)for(k=1;k<=C;k++)if(Dist[k]>Dist[j]+Graph[j][k]){printf("-1");return;}return;}.......A1TAnS但松弛操作直接得出的Bellman-Ford算法效率低下

ForTime=1toN-1 For(u,v)∈E Relax(u,v)上圖數(shù)據(jù)中，總運算量高達(dá)N^2而邊(S,A1)雖然被調(diào)用N次。但實際有用的只有一次香甜的黃油

農(nóng)夫John發(fā)現(xiàn)做出全威斯康辛州最甜的黃油的方法：糖。把糖放在一片牧場上，他知道N（1<=N<=500）只奶牛會過來舔它，這樣就能做出能賣好價錢的超甜黃油。當(dāng)然，他將付出額外的費用在奶牛上。

農(nóng)夫John很狡猾。他知道他可以訓(xùn)練這些奶牛，讓它們在聽到鈴聲時去一個特定的牧場。他打算將糖放在那里然后下午發(fā)出鈴聲，以至他可以在晚上擠奶。

農(nóng)夫John知道每只奶牛都在各自喜歡的牧場（一個牧場不一定只有一頭牛）。給出各頭牛在的牧場和牧場間的路線，找出使所有牛到達(dá)的路程和最短的牧場（他將把糖放在那）

香甜的黃油INPUTFORMAT第一行:三個數(shù)，奶牛數(shù)N，牧場數(shù)（2<=P<=800），牧場間道路數(shù)C(1<=C<=1450)第二行到第N+1行:

1到N頭奶牛所在的牧場號第N+2行到第N+C+1行：每行有三個數(shù)：相連的牧場A、B，兩牧場間距離D（1<=D<=255），當(dāng)然,連接是雙向的OUTPUTFORMAT

一行

輸出奶牛必須行走的最小的距離和

香甜的黃油SAMPLEINPUT(filebutter.in)345234121135237243345

香甜的黃油SAMPLEOUTPUT(filebutter.out)8{說明：放在4號牧場最優(yōu)}

負(fù)權(quán)回路輸入數(shù)據(jù)給出一個有N(2<=N<=1,000)個節(jié)點，M(M<=100,000)條邊的帶權(quán)有向圖.要求你寫一個程序,判斷這個有向圖中是否存在負(fù)權(quán)回路.如果從一個點沿著某條路徑出發(fā),又回到了自己,而且所經(jīng)過的邊上的權(quán)和小于0,就說這條路是一個負(fù)權(quán)回路.如果存在負(fù)權(quán)回路,只輸出一行-1;如果不存在負(fù)權(quán)回路,再求出一個點S(1<=S<=N)到每個點的最短路的長度.約定:S到S的距離為0,如果S與這個點不連通,則輸出NoPath.負(fù)權(quán)回路輸入格式（loop.in）第一行:點數(shù)N(2<=N<=1,000),邊數(shù)M(M<=100,000),源點S(1<=S<=N);以下M行,每行三個整數(shù)a,b,c表示點a,b(1<=a,b<=N)之間連有一條邊,權(quán)值為c(-1,000,000<=c<=1,000,000)輸出格式（loop.out）

如果存在負(fù)權(quán)環(huán),只輸出一行-1,否則按以下格式輸出共N行,第i行描述S點到點i的最短路:如果S與i不連通,輸出NoPath;如果i=S,輸出0;

其他情況輸出S到i的最短路的長度.

負(fù)權(quán)回路樣例輸入

68113412634-7642245363451354樣例輸出064-3-27

例題二中國郵遞員問題A城市的交通系統(tǒng)由若干個路口和街道組成，每條街道都連接著兩個路口。所有街道都只能單向通行。每條街道都有一個長度值。例題二中國郵遞員問題一名郵遞員傳送報紙和信件，要從郵局出發(fā)經(jīng)過他所管轄的每一條街道，最后返回郵局。每條街道可以經(jīng)過不止一次。他應(yīng)該如何安排自己的路線，使得走過的總長度最短呢？樣例路線總長度為14分析容易看出題目給出的是一個圖的模型。在有向圖中找一條權(quán)值最小的回路，使得它經(jīng)過圖中的每條邊至少一次。分析如果問題有解，那么一定滿足以下條件：

1、基圖連通；

2、不存在某個頂點入度為0或出度為0。分析為了簡化問題，我們暫時不考慮邊的權(quán)值。問題的核心條件是：“每條邊經(jīng)過至少一次”。轉(zhuǎn)化為如下形式：將圖中的某些邊拆分成若干條平行邊，使得圖中存在歐拉回路。分析設(shè)頂點v的入度與出度之差為p(v)。對于p(v)>0的頂點，需要增加p(v)條從v出發(fā)的邊；對于p(v)<0的頂點，需要增加-p(v)條到v結(jié)束的邊；對于p(v)=0的頂點，需要增加相等數(shù)量的從v出發(fā)的邊和到v結(jié)束的邊。分析p(v)>0網(wǎng)絡(luò)的源點，向網(wǎng)絡(luò)發(fā)出p(v)單位的流；p(v)<0p(v)=0網(wǎng)絡(luò)的匯點，從網(wǎng)絡(luò)接收

-p(v)單位的流；網(wǎng)絡(luò)的中間結(jié)點，接收的流量等于發(fā)出的流量。分析原問題轉(zhuǎn)化為多源多匯的最大流問題。我們可以通過附加超級源s和超級匯t的方法將其轉(zhuǎn)化為單源單匯的經(jīng)典最大流問題。分析下面我們考慮邊的權(quán)值。對于原圖中的邊e，將其費用值w(e)賦為對應(yīng)邊的長度；其余的邊不產(chǎn)生費用，將其費用值賦為0。求網(wǎng)絡(luò)中從s到t的最小費用最大流。最后，我們只需根據(jù)各邊的流量情況將原圖進(jìn)行改造，并在新圖中求歐拉回路即可。小結(jié)本題的解答過程中，運用了歐拉圖的一些性質(zhì)對題目進(jìn)行分析，通過聯(lián)想、類比將問題對應(yīng)到一個流網(wǎng)絡(luò)模型上，并使用最小費用最大流算法解決問題。拓展如果將條件改成“所有街道都能夠雙向通行”，該如何解決？如果將條件改成“部分街道能夠雙向通行，部分街道只能單向通行”呢？例題三賭博機(jī)一臺賭博機(jī)由n個整數(shù)發(fā)生器T1,T2,…,T