圖論與特殊圖概述

1、什么是圖什么是圖?ABCD哥尼斯堡七橋示意圖哥尼斯堡七橋示意圖問題問題1(1(哥尼斯堡七橋哥尼斯堡七橋問題問題):): 能否從任一陸地出發(fā)通過每座橋恰好一次而能否從任一陸地出發(fā)通過每座橋恰好一次而回到出發(fā)點？回到出發(fā)點？ABDC七橋問題模擬圖七橋問題模擬圖歐拉指出：歐拉指出： 如果每塊陸地所連接的橋都是偶數(shù)座，則如果每塊陸地所連接的橋都是偶數(shù)座，則從任一陸地出發(fā)，必能通過每座橋恰好一次而從任一陸地出發(fā)，必能通過每座橋恰好一次而回到出發(fā)地回到出發(fā)地. (. (著名的歐拉圖問題著名的歐拉圖問題) )問題問題2(2(哈密頓環(huán)球旅行哈密頓環(huán)球旅行問題問題):): 十二面體的十二面體的2020個頂點代表

2、世界上個頂點代表世界上2020個城市，個城市，能否從某個城市出發(fā)在十二面體上依次經(jīng)過每個能否從某個城市出發(fā)在十二面體上依次經(jīng)過每個城市恰好一次最后回到出發(fā)點？城市恰好一次最后回到出發(fā)點？哈密頓圈（環(huán)球旅行游戲）哈密頓圈（環(huán)球旅行游戲）問題問題3(3(四色問題四色問題):): 對任何一張地圖進行著色，兩個共同邊界的對任何一張地圖進行著色，兩個共同邊界的國家染不同的顏色，則只需要四種顏色就夠了國家染不同的顏色，則只需要四種顏色就夠了. .問題問題4(4(關鍵路徑問題關鍵路徑問題):): 一項工程任務一項工程任務, ,大到建造一座大壩大到建造一座大壩, ,一座體育一座體育中心中心, ,小至組裝一臺機

3、床小至組裝一臺機床, ,一架電視機一架電視機, , 都要包括都要包括許多工序許多工序. .這些工序相互約束這些工序相互約束, ,只有在某些工序完只有在某些工序完成之后成之后, , 一個工序才能開始一個工序才能開始. . 即它們之間存在完即它們之間存在完成的先后次序關系成的先后次序關系, ,一般認為這些關系是預知的一般認為這些關系是預知的, , 而且也能夠預計完成每個工序所需要的時間而且也能夠預計完成每個工序所需要的時間. . 這時工程領導人員迫切希望了解最少需要多這時工程領導人員迫切希望了解最少需要多少時間才能夠完成整個工程項目少時間才能夠完成整個工程項目, , 影響工程進度影響工程進度的要害

4、工序是哪幾個？的要害工序是哪幾個？ 圖論中的圖論中的“圖圖”并不是通常意義下的幾何圖并不是通常意義下的幾何圖形或物體的形狀圖形或物體的形狀圖, , 而是以一種抽象的形式來表而是以一種抽象的形式來表達一些確定的事物之間的聯(lián)系的一個數(shù)學系統(tǒng)達一些確定的事物之間的聯(lián)系的一個數(shù)學系統(tǒng). . 定義定義1 一個有序二元組一個有序二元組(V, E ) 稱為一個稱為一個圖圖, 記為記為G = (V, E ), 其中其中 V稱為稱為G的頂點集的頂點集, V , 其元素稱為其元素稱為頂頂點點或或結點結點, 簡稱簡稱點點; E稱為稱為G的邊集的邊集, 其元素稱為其元素稱為邊邊, 它聯(lián)結它聯(lián)結V 中的兩個點中的兩個點

5、, 如果這兩個點是無序的如果這兩個點是無序的, 則稱該邊則稱該邊為為無向邊無向邊, 否則否則, 稱為稱為有向邊有向邊. 如果如果V = v1, v2, , vn是有限非空點是有限非空點集集, 則稱則稱G為為有限圖有限圖或或n階圖階圖. 如果如果E的每一條邊都是無向邊的每一條邊都是無向邊, 則稱則稱G為為無向無向圖圖( (如圖如圖1)1); 如果如果E的每一條邊都是有向邊的每一條邊都是有向邊, 則稱則稱G為為有向圖有向圖( (如圖如圖2)2); 否則否則, 稱稱G為為混合圖混合圖. 圖圖1 1圖圖2 2并且常記并且常記V = v1, v2, , vn, |V | = n ;E = e1, e2,

6、 , em(ek=vivj ) , |E | = m.稱點稱點vi , vj為邊為邊vivj的的端點端點. 在有向圖中在有向圖中, 稱點稱點vi , vj分別為邊分別為邊vivj的的始點始點和和終點終點. 對于一個圖對于一個圖G = (V, E ), 人們常用圖形來人們常用圖形來表示它表示它, 稱其為稱其為圖解圖解. 凡是有向邊凡是有向邊, 在圖解上都在圖解上都用箭頭標明其方向用箭頭標明其方向. 例如例如, 設設V = v1 , v2 , v3 , v4, E = v1v2 , v1v3 , v1v4 , v2v3 , v2v4 , v3v4, 則則G = (V, E ) 是一個有是一個有4個

7、頂點和個頂點和6條邊的圖條邊的圖, G的圖解如下圖所示的圖解如下圖所示. 歐拉圖歐拉圖 歐拉回路歐拉回路 歐拉回路問題是圖論中最古老的問題之一。它誕生于十八世紀的歐洲古城哥尼斯堡。普瑞格爾河流經(jīng)這座城市，人們在兩岸以及河中間的兩個小島之間建了七座橋（如圖1）。 于是產(chǎn)生了這樣一個問題：是否可以找到一種方案，使得人們從自己家里出發(fā)，不重復地走遍每一座橋，然后回到家中？這個問題如果用數(shù)學語言來描述，就是在圖2中找出一條回路，使得它不重復地經(jīng)過每一條邊。這便是著名的“哥尼斯堡七橋問題”。圖1圖2歐拉圖歐拉圖 歐拉回路歐拉回路 無數(shù)熱衷于此的人試圖解決這個問題，但均以失敗告終。問題傳到了歐拉（Leon

8、hard Euler, 1707-1783）那里，立即引起了這位大數(shù)學家的重視。經(jīng)過悉心研究，歐拉終于在1736年發(fā)表了論文哥尼斯堡的七座橋，不但成功地證明了“七橋問題”無解，而且找到了對于一般圖是否存在這類回路的充要條件。后人為了紀念歐拉這位偉大的數(shù)學家，便將這類回路稱為歐拉回路。 歐拉圖歐拉圖 歐拉回路歐拉回路 首先介紹相關概念和定理。設是首先介紹相關概念和定理。設是 一個圖。一個圖。 歐拉通路歐拉通路(回路回路)：通過圖G（無向圖或有向圖）中所有邊邊一次且僅一次行遍圖中所有頂點的通路(回路)稱為歐拉通路(回路)。歐拉圖與半歐拉圖歐拉圖與半歐拉圖：具有歐拉回路的圖稱為歐拉圖，具有歐拉通路而

9、無歐拉回路的圖稱為半歐拉圖。橋橋：設無向圖G=，若存在邊集E的一個非空子集非空子集E1，使得p(G-E1)p(G)，而對于E1的任意真子集真子集E2，均有p(G-E2)=p(G)，則稱E1是G的邊割集，或簡稱割集；若E1是單元集，即E1=e，則稱e為割邊或橋橋。p(G)表示圖G的連通分支數(shù).),(EVG a) 是歐拉圖；b) 不是歐拉圖，但存在歐拉通路；c) 即不是歐拉圖，也不存在歐拉通路。甲、乙兩只螞蟻分別位于如下圖中的結點a，b處，并設圖中的邊長度是相等的。甲、乙進行比賽：從它們所在的結點出發(fā)，走過圖中的所有邊最后到達結點c處。如果它們的速度相同，問誰先到達目的地？ 無向圖存在歐拉回路的充

10、要條件：連通且沒有奇點。 無向圖存在歐拉路徑的充要條件：連通且奇點個數(shù)為2。(1)既無歐拉回路,也無歐拉通路.(2)中存在歐拉通路,但無歐拉回路.(3)中存在歐拉回路. 圖圖a)a)存在一條歐拉通路：存在一條歐拉通路：v v3 3v v1 1v v2 2v v3 3v v4 4v v1 1； 圖圖(b)(b)中存在歐拉回路中存在歐拉回路v v1 1v v2 2v v3 3v v4 4v v1 1v v3 3v v1 1，因而，因而(b)(b)是歐拉是歐拉圖；圖； 圖圖(c)(c)中有歐拉回路中有歐拉回路v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6v v7 7v v8

11、 8v v2 2v v4 4v v6 6v v8 8v v1 1因而因而(c)(c)是歐拉圖。是歐拉圖。 有向圖存在歐拉回路的充要條件：基圖連通且所有頂點入度等于出度。 有向圖存在歐拉路徑的充要條件：基圖連通且存在某頂點入度比出度大1，另一頂點出度比入度大1，其余頂點入度等于出度。歐拉回路存在性的判斷歐拉回路存在性的判斷 歐拉回路問題可以分為無向圖中的歐拉回路和歐拉通路，有向圖中的歐拉回路和歐拉通路。這幾個問題大抵相像。 有向歐拉回路有： 定理：假設有像多重圖定理：假設有像多重圖D有性質(zhì)：當忽略有向邊上的方向時，得到有性質(zhì)：當忽略有向邊上的方向時，得到的圖是連通的，那么的圖是連通的，那么D有有

12、向歐拉回路當且僅當有有向歐拉回路當且僅當D的每個頂點的入的每個頂點的入度和出度相等。度和出度相等。 類似的，對有向歐拉通路有： 定理：定理：D有有向歐拉通路，當且僅當除兩個不同頂點有有向歐拉通路，當且僅當除兩個不同頂點B和和C之外，之外，D的其它頂點的入度和出度相等，且的其它頂點的入度和出度相等，且B的出度比入度大的出度比入度大1，C的入度的入度比出度大比出度大1。在這種情況下，有向歐拉通路自。在這種情況下，有向歐拉通路自B出發(fā)，至出發(fā)，至C終止。終止。 由上面的定理可以知道，如果要判斷一個有向圖的歐拉回路是否存在，需要先判斷連通性，再判斷出度入度。對于無向圖，判斷方法類似。 判斷連通性可以通

13、過DFS或者并查集來實現(xiàn)。1.在圖中任意找一個回路C；2.將圖中屬于C的邊刪除；3.在殘留圖的各個極大連通分量中求歐拉回路；4.將各極大連通分量中的歐拉回路合并到C上。歐拉回路的構建歐拉回路的構建在構建歐拉回路之前需要判斷歐拉回路是否存在。構建歐拉回路可以使用Fleury算法（能不走橋就不走橋）：Fleury算法：算法：（1）任取v0V(G)，令P0=v0；（2）設Pi=v0e1v1e2.eivi已經(jīng)行遍，按下面方法來從 E(G)-e1,e2,.,ei中選取ei+1： （a）ei+1與vi想關聯(lián)； （b）除非無別的邊可供行遍，否則ei+1不應該為 Gi=G-e1,e2,.,ei中的橋.（3）當

14、（2）不能再進行時，算法停止?？梢宰C明，當算法停止時所得簡單回路Pm=v0e1v1e2.emvm（vm=v0）為G中的一條歐拉回路。構建歐拉回路的Fleury算法可以實用DFS來實現(xiàn)。算法的圖示動態(tài)過程： 歐拉算法描述歐拉算法描述 void DFS(Graph &G,SqStack &S,int x,int t) k=0;/一個標志,來標記當前訪問的節(jié)點是否還有鄰接邊可供訪問 Push(S,x); /將本次遍歷邊所經(jīng)由的點入棧 for(i=t;i0) k=1; Gix=0; Gxi=0; /此邊已訪問,刪除此邊 DFS(G,S,i,0);/尋找下一條關聯(lián)的邊,本次找到的是與x關

15、聯(lián)的i,在 /下一層中將尋找與i關聯(lián)的邊 break; /if,for歐拉算法描述歐拉算法描述 if(k=0) /如果k=0,說明與當前頂點關聯(lián)的邊已窮盡 Pop(S); GetTop(S,m); Gxm=1;Gmx=1;/恢復在上一層中被刪除的邊 a=x+1;/如果可能的話,從當前節(jié)點的下一條關聯(lián)邊開始搜尋 if(StackLength(S)!=e)/繼續(xù)搜尋,邊還沒有全部遍歷完 Pop(S); /還原到上一步去 DFS(G,S,m,a);/ /if else /搜尋完畢,將最后節(jié)點也入棧 Push(S,x); /if/DFS歐拉算法描述歐拉算法描述 void Euler(Graph &am

16、p;G,int x)/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個盤子，每個盤子上寫著一個僅由小寫字母組成的英文單詞。 你需要給這些盤子按照合適的順序排成一行，使得相鄰兩個盤子中，前一個盤子上面單詞的末字母等于后一個盤子上面單詞的首字母。 請你編寫一個程序，判斷是否能達到這

17、一要求。如果能，請給出一個合適的順序。 malformmouseacmmalformmouseacmmmmm 以26個英文字母作為頂點。 對于每一個單詞，在圖中從它的首字母向末字母連一條有向邊。 問題轉化為在圖中尋找一條不重復地經(jīng)過所有邊的路徑，即歐拉路徑歐拉路徑。 這個問題能夠在O(|E|)時間內(nèi)解決。實例：實例：PKU 2337問題描述問題描述給出一些字符串，讓你首尾串起來串成一串，并且輸出一個字典序最小的方案。如果不能，輸出“*”。否則輸出字典序最小的回路。輸入輸入26alohaarachniddoggopherrattiger3oakmapleelm輸出輸出aloha.arachnid

18、.dog.gopher.rat.tiger*實例：實例：PKU 2337在沒有特殊要求的情況下，DFS遍歷圖的結點順序是可以任選的。但是這里由于加上了字典序最小的要求，所以DFS遍歷時需要按照以下的優(yōu)先順序：1. 如果有不是橋的邊，遍歷這些邊中字典序最小的邊。2. 否則，遍歷這些這些橋中字典序最小的邊。比如一個單詞，abcde，那么就連接一條a到e的有向邊。如此構成的圖一共最多有26個節(jié)點。每條邊都代表一個單詞，那么就轉化成了：找一條路，遍歷所有的邊。就是歐拉通路問題。遍歷歐拉通路的方法：確定一個起點（出度-入度=1，或者等于0（如果存在歐拉回路的話）從起點開始深搜（首先要保證圖中存在歐拉回路

19、或者通路）dfs(vid, eid)其中vid表示當前搜到的點。eid表示當前搜到的邊（一個點可能會有很多邊）對于每條邊，都是等它搜索完了后，把它代表的內(nèi)容（這里是單詞）壓入一個棧中。最后深搜結束后，依次彈棧就是答案。Door Man (South Central USA 2002 ) 大意：給定N(=20)個房間,房間之間有門相隔，門的數(shù)目不超過100道，當前人在第M個房門，當前人每經(jīng)過一道門的時候就把經(jīng)過的門鎖上，問有沒有一條路可以使得我們走到第0個房門的時候所有的門都鎖上了。 思路：我們可以把門看成是兩個房間之間的邊，那么問題可以轉化成找一條歐拉路徑。 PS：判斷的時候只要判斷所有的邊在

20、一起就行了，所有的點不一定連通，當0點和M點不連通的時候，無解。 注意這組數(shù)據(jù)。 定義定義1 設設P(u, v) 是賦權圖是賦權圖G = (V, E , F) 中從中從點點u到到v的路徑的路徑, 用用E(P) 表示路徑表示路徑P(u, v)中全部邊的中全部邊的集合集合, 記記)()()(PEeeFPF則稱則稱F (P)為路徑為路徑P(u, v) 的的權權或或長度長度( (距離距離) ). 定義定義2 若若P0 (u, v) 是是G 中連接中連接u, v的路徑的路徑, 且對且對任意在任意在G 中連接中連接u, v的路徑的路徑P (u, v)都有都有F (P0)F(P), 則稱則稱P0 (u, v

21、) 是是G 中連接中連接u, v的的最短路最短路. 重要性質(zhì)：重要性質(zhì)： 若若v0 v1 vm 是是圖圖G中從中從v0到到vm的最短路的最短路, 則則 1km, v0v1 vk 必為必為G中從中從v0到到vk的的最短路最短路. 即：最短路是一條路，且最短路的任一段也即：最短路是一條路，且最短路的任一段也是最短路是最短路. 求非負賦權圖求非負賦權圖G中某一點到其它各點最短路，中某一點到其它各點最短路，一般用一般用Dijkstra標號算法；求非負賦權圖上任標號算法；求非負賦權圖上任意兩點間的最短路，一般用意兩點間的最短路，一般用Floyd算法算法. .這兩種這兩種算法均適用于有向非負賦權圖算法均適

22、用于有向非負賦權圖. . 這個算法能在更一般的情況下解決最短路的問題。何謂一般，一般在該算法下邊的權值可以為負，可以運用該算法求有向圖的單元最長路徑或者最短路徑。適用條件: 任意邊權為實數(shù)的圖Bellman-Ford算法的思想基于以下事實：“兩點間如果有最短路，那么每個結點最多經(jīng)過一次。也就是說，這條路不超過n-1條邊。”（如果一個結點經(jīng)過了兩次，那么我們走了一個圈。如果這個圈的權為正，顯然不劃算；如果是負圈，那么最短路不存在；如果是零圈，去掉不影響最優(yōu)值）Bellman-Ford算法的運行時間為O(VE)。很多時候，我們的算法并不需要運行|V|-1次就能得到最優(yōu)值。對于一次完整的第3-4行操

23、作，要是一個結點的最短路徑估計值也沒能更新，就可以退出了。經(jīng)過優(yōu)化后，對于多數(shù)情況而言，程序的實際運行效率將遠離O(VE)而變?yōu)镺(kE)，其中k是一個比|V|小很多的數(shù)。 Bellman ford 類似于Dijkstra算法，對每一個節(jié)點v，逐步減小從起點s到終點v最短路的估計量distv直到其達到真正的最短路徑值mindistv。Bellman-ford算法同時返回一個布爾值，如果不存在從源結點可達的負權回路，算法返回布爾值TRUE，反之返回FALSE。1. 枚舉每條邊(u,v) E（G）。2. 對枚舉到的邊進行一次松弛松弛操作。3. 回到步驟1，此過程重復n-1次，以確定沒有可以更優(yōu)化的

24、情況。4. 枚舉每條邊（u，v）若仍然存在可以更新的邊，則說明有向圖中出現(xiàn)了負權回路，于是返回布爾值FALSE。否則返回布爾值TRUE。void Bellman_ford (void) int i, j, k; for(i=1; i=C; i+)Disti = INF ; DistS = 0 ; for(i=1; i=C-1; i+) for(j=1; j=C; j+) for(k=1; kDistj+Graphjk)Distk=Distj+Graphjk; for(j=1; j=C; j+) for(k=1; kDistj+Graphjk) printf(-1); return; retur

25、n ; .A1TAnS但松弛操作直接得出的Bellman-Ford算法效率低下 For Time=1 to N-1 For (u,v)ERelax(u,v)上圖數(shù)據(jù)中，總運算量高達N2而邊(S, A1)雖然被調(diào)用N次。但實際有用的只有一次 農(nóng)夫農(nóng)夫John發(fā)現(xiàn)做出全威斯康辛州最甜的黃油的方法：糖發(fā)現(xiàn)做出全威斯康辛州最甜的黃油的方法：糖。把糖放在一片牧場上，他知道。把糖放在一片牧場上，他知道N（1=N=500）只）只奶牛會過來舔它，這樣就能做出能賣好價錢的超甜黃油。奶牛會過來舔它，這樣就能做出能賣好價錢的超甜黃油。當然，他將付出額外的費用在奶牛上。當然，他將付出額外的費用在奶牛上。 農(nóng)夫農(nóng)夫Jo

26、hn很狡猾。他知道他可以訓練這些奶牛，讓它們很狡猾。他知道他可以訓練這些奶牛，讓它們在聽到鈴聲時去一個特定的牧場。他打算將糖放在那里然在聽到鈴聲時去一個特定的牧場。他打算將糖放在那里然后下午發(fā)出鈴聲，以至他可以在晚上擠奶。后下午發(fā)出鈴聲，以至他可以在晚上擠奶。 農(nóng)夫農(nóng)夫John知道每只奶牛都在各自喜歡的牧場（一個牧場知道每只奶牛都在各自喜歡的牧場（一個牧場不一定只有一頭牛）。給出各頭牛在的牧場和牧場間的路不一定只有一頭牛）。給出各頭牛在的牧場和牧場間的路線，找出使所有牛到達的路程和最短的牧場（他將把糖放線，找出使所有牛到達的路程和最短的牧場（他將把糖放在那）在那） INPUT FORMAT 第一行: 三個數(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），當然,連接是雙向的 OUTPUT FORMAT 一行 輸出奶牛必須行走的最小的距離和 SAMPLE INPUT (file butter.in) 3 4 5 2 3 4 1 2 1 1 3 5 2 3 7 2 4 3 3 4 5 SAMPLE OUTPUT (file but