圖論基礎(chǔ)(信息學(xué)奧賽)

圖論及其算法吳聞第一章

基本概念1.1引言1.2圖的定義1.3道路和回路1.4樹1.1引言圖論是一個(gè)應(yīng)用十分廣泛而又極其有趣的數(shù)學(xué)分支。物理、化學(xué)、生物、科學(xué)管理、計(jì)算機(jī)等各個(gè)領(lǐng)域都可找到圖論的足跡。介紹幾個(gè)圖論有關(guān)的簡(jiǎn)單例子1.1引言例1下圖是一個(gè)公路網(wǎng)，V1,V2,...,V10是一些城鎮(zhèn)，每條線旁邊的數(shù)字代表這一段公路的長(zhǎng)度?，F(xiàn)在問，要從V1把貨物運(yùn)到V10，走哪條路最近?1.1引言例1實(shí)際上，就是圖論中的求最短路徑問題。在現(xiàn)實(shí)中有很多此類問題，所以圖論中求最短路徑算法是一個(gè)非常經(jīng)典和重要的算法。1.1引言例2下圖是一個(gè)公路網(wǎng)，V1,V2,...,V10看成公路網(wǎng)的一個(gè)站點(diǎn)，若這個(gè)公路網(wǎng)目前被敵方占領(lǐng)。請(qǐng)分析一下，最少需要破壞其公路網(wǎng)的幾個(gè)站點(diǎn)，就可摧毀敵方整個(gè)運(yùn)輸線1.1引言例2屬于圖的連通性問題。找出圖中的割頂集，就是問題的解。軍事指揮中很多此類問題。1.1引言例3飛行大隊(duì)有若干個(gè)來自各地的駕駛員，專門駕駛一種型號(hào)的飛機(jī)，這種飛機(jī)每架有兩個(gè)駕駛員。由于種種原因，例如相互配合的間題，有些駕駛員不能在同一架飛機(jī)上飛行，問如何搭配駕駛員，才能使出航的飛機(jī)最多。1.1引言例3用V1,V2,...,V10代表這10個(gè)駕駛員。如果兩個(gè)人可以同機(jī)飛行，就在代表他們兩個(gè)之間連一條線;兩個(gè)人不能同機(jī)飛行，就不連。例如V1和V2可以同機(jī)飛行，而V1和V3就不行。1.1引言例3此類問題屬于圖的最大匹配問題將實(shí)際生活中的事物分析轉(zhuǎn)化為圖論問題的實(shí)例還很多...1.2圖的定義圖：由若干個(gè)不同頂點(diǎn)與連接其中某些頂點(diǎn)的邊所組成的圖形。圖的表示：通常用一個(gè)大寫字母G來表示圖，用V來表示所有頂點(diǎn)的集合，E表示所有邊的集合，并且記成G=(V,E)。1.2圖的定義子圖：如果對(duì)圖G=(V,E)與G'=(V',E'),G'的頂點(diǎn)集是G的頂點(diǎn)集的一個(gè)子集(V'?V),G'的邊集是G的邊集的一個(gè)子集(E'?E)，我們說G'是G的子圖1.2圖的定義環(huán)：如果一條邊，它的起點(diǎn)和終點(diǎn)相同，這樣的邊稱為環(huán)。平行邊：若連接兩個(gè)頂點(diǎn)的邊有多條，則這些邊稱之為平行邊。孤立點(diǎn)：不與任何邊關(guān)聯(lián)的頂點(diǎn)稱為孤立點(diǎn)。1.2圖的定義簡(jiǎn)單圖：如果一個(gè)圖沒有環(huán)，并且每?jī)蓚€(gè)頂點(diǎn)之間最多只有一條邊，這樣的圖稱之為簡(jiǎn)單圖。在簡(jiǎn)單圖中，連接Vi與Vj的邊可以記成(Vi,Vj)完全圖：如果G是一個(gè)簡(jiǎn)單圖，并且每?jī)蓚€(gè)頂點(diǎn)之間都有一條邊，我們就稱G為完全圖。通常將具有n個(gè)頂點(diǎn)的完全圖記為Kn。二分圖：如果G是一個(gè)簡(jiǎn)單圖，它的頂點(diǎn)集合V是由兩個(gè)沒有公共元素的子集X={X1,X2,...,Xn}與Y={Yl,Y2,...,Ym}組成的，并且Xi與Xj(1<i,j<n),Ys與Yt(1<s,t<m)之間沒有邊連接，則G叫做二分圖。1.2圖的定義簡(jiǎn)單圖、完全圖、二分圖1.2圖的定義完全二分圖：如果在二分圖G中，IXI=N,IYI=M，每一個(gè)Xi∈X與每一個(gè)Yj∈Y有一條邊相連，則G叫做完全二分圖1.2圖的定義如果G是一個(gè)N個(gè)頂點(diǎn)的簡(jiǎn)單圖，從完全圖Kn中把屬于G的邊全部去掉后，得到的圖稱為G的補(bǔ)圖，通常記為G。一個(gè)圖的補(bǔ)圖的補(bǔ)圖就是自身。1.2圖的定義相鄰：如果圖G的兩個(gè)頂點(diǎn)Vi與Vj之間有邊相連，我們就說Vi與Vj是相鄰的，否則就說Vi與Vj是不相鄰的。如果頂點(diǎn)V是邊e的一個(gè)端點(diǎn)，就說頂點(diǎn)V與邊e是相鄰的，e是從V引出的邊。度數(shù)：從一個(gè)頂點(diǎn)V引出的邊的條數(shù)，稱為V的度數(shù)，記作d(V)。1.2圖的定義下圖中，d(V1)=d(V2)=d(V3)=d(V4)=d(V5)=5-1=4,d(Y3)=2等等。1.2圖的定義K度正則圖：把每個(gè)頂點(diǎn)的度數(shù)為常數(shù)K的圖叫做K度正則圖。經(jīng)常使用下面兩個(gè)符號(hào):1.2圖的定義從頂點(diǎn)度數(shù)問題的討論中，引出一些有趣的結(jié)論:1.2.對(duì)于任意的圖G，奇次頂點(diǎn)的個(gè)數(shù)一定是偶數(shù)。1.2圖的定義例1、空間是否有這樣的多面體存在，它們有奇數(shù)個(gè)面，而每個(gè)面又有奇數(shù)條邊?分析:根據(jù)題意，可以構(gòu)造一個(gè)圖，以面為頂點(diǎn)，當(dāng)且僅當(dāng)兩個(gè)面有公共棱時(shí)，則在G的相應(yīng)兩頂點(diǎn)間連一條邊，得到圖G。依題意，圖的頂點(diǎn)個(gè)數(shù)是奇數(shù)，而且每個(gè)頂點(diǎn)的度數(shù)d(V)是奇數(shù)，從而也是奇數(shù)，與結(jié)論1相違，故這種多面體不存在。1.2圖的定義例2、晚會(huì)上大家握手聯(lián)歡，問是否會(huì)出現(xiàn)握過奇次手的人是奇數(shù)的情況?分析:一個(gè)圖，以人為頂點(diǎn)，兩人握手時(shí)，則相應(yīng)的兩個(gè)頂點(diǎn)之間連一條邊，于是每人握手的次數(shù)即相應(yīng)頂點(diǎn)的度數(shù)。由結(jié)論2，奇次頂點(diǎn)的個(gè)數(shù)總是偶數(shù)，所以握過奇次手的人數(shù)是奇數(shù)的情況不可能出現(xiàn)。1.3道路與回路道路：在圖G中，一個(gè)由不同的邊組成的序列e1,e2...,eg，如果ei是連接Vi-1與Vi(i=1,2,..,g)的，我們就稱這個(gè)序列為從V0到Vg的一條道路，數(shù)g稱為路長(zhǎng)，V0與Vg稱為這條道路的兩個(gè)端點(diǎn)，Vi(1<=i<=g-1)叫做道路的內(nèi)點(diǎn)。如果G是簡(jiǎn)單圖，這條道路也可以記作(V0,V1,...,Vg)1.3道路與回路下圖中e1,e2,e3,e4,e5,e6組成一條道路1.3道路與回路軌道：在道路的定義中，并不要求V0至Vg，互不相同。如果V0至Vg互不相同，這樣的道路稱為軌道，記成P(V0,Vg)。回路：V0=Vg的路稱為回路。圈：V0=Vg的軌道叫做圈。K階圈：長(zhǎng)為K的圈叫做K階圈。顯然，如果有一條從V到V'的道路上去掉若干個(gè)回路，便可得到一條從V到V'的軌道。1.3道路與回路U,V兩頂點(diǎn)的距離：U,V間最短軌道的長(zhǎng)度，記作為D(U,V)。連通圖：若U與Y之間存在道路，則稱U與V相連通。圖G中任意兩個(gè)頂點(diǎn)皆連通時(shí)，稱G為連通圖。1.3道路與回路如果圖G是一條從V0到Vg的道路，那么該條道路上的每一個(gè)內(nèi)點(diǎn)Vi(1<=i<=g-1)都是度數(shù)為偶數(shù)的頂點(diǎn)。因?yàn)閷?duì)Vi來說，有一條進(jìn)入Vi的邊，就有一條從Vi引出的邊，而且進(jìn)出的邊不能重復(fù)已走過的邊，所以與Vi相鄰的邊總是成雙的。故圖G至多有兩個(gè)奇頂點(diǎn)，即V0與Vg。如果G是一條回路，那么根據(jù)上面推理，V0與Vg 的度數(shù)也是偶數(shù)。由此，我們可以引出下面一個(gè)結(jié)論:1.3道路與回路有限圖G是一條道路(即可以一筆畫成)的充分必要條件是G是連通的，且奇頂點(diǎn)的個(gè)數(shù)等于0或2，并且當(dāng)且僅當(dāng)奇頂點(diǎn)的個(gè)數(shù)為0時(shí)，連通圖G是一條回路(孤立點(diǎn)可以看作是回路)。1.3道路與回路七橋問題：一條河從城市穿過，河中有兩個(gè)島A與D，河有七座橋，連接這兩個(gè)島及河的兩岸B,C。如下圖所示：1.3道路與回路問:(1)一個(gè)旅行者能否經(jīng)過每座橋恰好一次，既無重復(fù)也無遺漏?(2)能否經(jīng)過每座橋恰好一次，并且最后能夠回到原來出發(fā)點(diǎn)?七橋問題轉(zhuǎn)換成圖后，實(shí)際上就成了圖的一筆畫問題：能否一筆畫出這個(gè)圖，每條邊既無遺漏，也無重復(fù)？能否一筆畫出這個(gè)圖，并且最后回到出發(fā)點(diǎn)。根據(jù)道路和回路的知識(shí)解答1.3道路與回路顯然，由于七橋問題對(duì)應(yīng)的圖中有4個(gè)奇頂點(diǎn)，因而不能一筆畫成，即一個(gè)旅行者要既無重復(fù)也無遺漏地走過圖中七座橋是不可能的。需要幾筆呢？？？？1.4樹樹：沒有圈的連通圖稱作樹，通常用T表示。T中d(V)=1的頂點(diǎn)叫做葉;森林：每個(gè)連通分支皆為樹的圖叫做森林。平凡樹：孤立的頂點(diǎn)叫做平凡樹。樹的圖論特征：如果樹T的頂點(diǎn)數(shù)為N，那么它的邊數(shù)M=N-1;倒過來，一個(gè)具有N個(gè)頂點(diǎn)、M=N-1條邊的連通圖G，一定是一棵樹。1.4樹《紅樓夢(mèng)》中榮國(guó)府的世系圖就是一棵樹：1.4樹樹T具有以下性質(zhì):1.在T中去掉一邊后所得的圖G是不連通的，2.T添加一條邊后所得的圖G一定有圈;3.T的每一對(duì)頂點(diǎn)V與V'之間有且僅有一條軌道相連。1.4樹設(shè)G是一個(gè)連通圖，如果G中有圈，我們?cè)谶@個(gè)圈中去掉一條邊，得到的G'還是連通的，如果G'仍然有圈，再在圈中去掉一條邊得連通圖G''，......，這樣繼續(xù)下去，最后得到一個(gè)樹T，T與G的頂點(diǎn)是相同的，并且從T陸續(xù)添加一些邊就得到G。具有這樣性質(zhì)的樹稱為連通圖G的生成樹。第二章

求最短路徑的算法及應(yīng)用2.1求最短路2.2服務(wù)點(diǎn)設(shè)置間題1—求圖的中心2.3服務(wù)點(diǎn)設(shè)置間題2—求圖的P中心2.4服務(wù)點(diǎn)設(shè)置間題3—求圖的中央點(diǎn)2.1求最短路一、什么是最短路問題：1.求有向圖(圖中從一個(gè)頂點(diǎn)連到相鄰頂點(diǎn)的邊有方向性)的最短路問題：設(shè)G=(V,A)是一個(gè)有向圖，它的每一條弧Ai都有一個(gè)非負(fù)的長(zhǎng)度L(Ai)，在G中指定一個(gè)頂點(diǎn)Vs，要求把從Vs到G的每一個(gè)頂點(diǎn)Vj的最短有向路找出來(或者指出不存在從Vs到Vj的有向路，即Vs不可達(dá)Vj2.1求最短路2.求無向圖(圖中連接兩個(gè)頂點(diǎn)的邊無方向性)的最短路問題：設(shè)G=(V,E)是一個(gè)無向圖，它的每一條邊ei都有一個(gè)非負(fù)長(zhǎng)度L(ei)。在G中指定一個(gè)頂點(diǎn)Vs，要求把從Vs到G的每一個(gè)頂點(diǎn)Vs的最短無向路找出來(或者指出不存在從Vs到Vj的無向路，即Vs不可達(dá)Vj。2.1求最短路二、求最短有向路的標(biāo)號(hào)法所謂標(biāo)號(hào)，是指與圖的每一個(gè)頂點(diǎn)對(duì)應(yīng)的一個(gè)數(shù)字。設(shè):b(j)：頂點(diǎn)Vj的標(biāo)號(hào)，代表的是Vs到Vj的最短的長(zhǎng)度。Vj已標(biāo)號(hào)則意味著Vs到Vj的最短路以及這條路徑的長(zhǎng)度已經(jīng)求出。顯然初始時(shí)b(s)=0。l(i,j)：弧(Vi,Vj)的非負(fù)長(zhǎng)度。K(i,j)：當(dāng)前有向路加入弧(Vi，Vj)后，Vs到Vj的有向路長(zhǎng)度。2.1求最短路標(biāo)號(hào)法的算法流程如下：2.1求最短路標(biāo)號(hào)法通用于有向、無向圖。2.1求最短路實(shí)例：渡河問題。一個(gè)人帶了一只狼、一只羊和一裸白菜想要過河，河上有一只獨(dú)木船，每次除了人以外，只能帶一樣?xùn)|西。另外如果人不在旁時(shí)狼就要吃羊，羊就要吃白菜。問應(yīng)該怎樣安排渡河，才能做到既把所有東西都帶過河，在河上來回的次數(shù)又最少?分析：設(shè)變量M代表人，W代表狼，S代表羊，V代表白菜，Φ代表空，什么都沒有。開始時(shí)設(shè)人和其它三樣?xùn)|西在河的左岸，這種情況用MWSV表示。2.1求最短路用一個(gè)集合表示左岸的所有可能情況。很顯然，可能出現(xiàn)的情況有16種:剔除下述6種可能發(fā)生狼吃羊、羊吃白菜的情況:2.1求最短路構(gòu)造一個(gè)圖G，它的頂點(diǎn)就是剩下的10種情況。G中的邊是按下述原則來連的:如果經(jīng)過一次渡河，情況甲可以變成情況乙，那么就在情況甲與情況乙之間連一條邊。2.1求最短路作了圖G以后，渡河的問題就歸結(jié)為下述問題了:在G中找一條連接頂點(diǎn)MWSV與Φ，并且包含邊數(shù)最少的路。如果設(shè)G中各邊的長(zhǎng)度都是1，那么也可以把渡河間題歸結(jié)為:“找一條連接MWSV與Φ的最短路”。最終問題歸結(jié)為求最短路徑問題。第三章

求最小生成樹3.1求無向圖的最小生成樹3.2求有向圖的最小樹形圖3.1求無向圖的最小生成樹一、最小生成樹的由來設(shè)G=[V,E]是一個(gè)無向圖，如果T=[V,E1]是由G的全部頂點(diǎn)及一部分邊組成的子圖并且T是樹(連通、沒有圈的圖)，則稱T是G的一個(gè)生成樹。一個(gè)連通圖G一般有許多種生成樹。現(xiàn)在考慮一個(gè)連通圖G=[V,E]，它的每一條邊Ej，有一個(gè)長(zhǎng)度L(Ej)>0。這時(shí)對(duì)于G的任意一個(gè)生成樹T，我們把屬于T的各條邊的長(zhǎng)度之和稱為T的長(zhǎng)度，記作L(T)。3.1求無向圖的最小生成樹一、最小生成樹的由來下圖中，T1和T2是G的生成樹，L(T1)=22,L(T2)=173.1求無向圖的最小生成樹一、最小生成樹的由來最小生成樹問題：如何從G的所有生成樹中，找出長(zhǎng)度最小的生成樹。這個(gè)問題即所謂最小生成樹間題。3.1求無向圖的最小生成樹二、最小生成樹的計(jì)算一開始，先將G圖中的邊都去掉，只留下孤立的頂點(diǎn)，這個(gè)圖即為G圖最初的生成子圖G1。然后逐步地將當(dāng)前最小邊e1加上去，每次加的時(shí)候，，要保持“沒有圈”的性質(zhì)，在加了N-1條邊(N是頂點(diǎn)個(gè)數(shù))后，G1便成為所要求的最小生成樹了。3.1求無向圖的最小生成樹二、最小生成樹的計(jì)算算法步驟如下：第四章

圖的連通性4.1連通性的基本概念和定義4.2深度優(yōu)先搜索(dfs)4.3求割頂和塊4.4求極大強(qiáng)連通子圖4.5求最小點(diǎn)基4.6可靠通訊網(wǎng)的構(gòu)作4.1連通性的基本概念和定義在無向圖G中，如果從頂點(diǎn)V到頂點(diǎn)V'有路徑，則稱V和V'是連通的。如果對(duì)于圖中任意兩個(gè)頂點(diǎn)Vi,Vj∈V,Vi和Vj都是連通的，則稱該圖為連通圖。所謂連通分量指的是無向圖中的極大連通子圖4.1連通性的基本概念和定義在有向圖G中，如果對(duì)于每一對(duì)Vi,Vj∈V,Vi≠Vj,從Vi到Vj，和從Vi到Vj都存在路徑，則稱G是強(qiáng)連通圖。有向圖中的極大強(qiáng)連通子圖稱作有向圖的強(qiáng)連通分量。4.1連通性的基本概念和定義一個(gè)連通圖的生成樹是一個(gè)極小連通子圖，它含圖的全部頂點(diǎn)，但只有足以構(gòu)成一棵樹的N-1條邊超過N-1條邊必有回路，就不再是樹了。4.1連通性的基本概念和定義為更精確的描述圖的連通性，還需引入兩個(gè)概念：頂連通度K(G)邊連通度K'(G)4.1連通性的基本概念和定義頂連通度：V'是連通圖G的一個(gè)頂點(diǎn)子集。在G中刪去V'及與V'相關(guān)聯(lián)的邊后圖不連通，則稱V'是G的割頂集。最小割頂集中頂點(diǎn)的個(gè)數(shù)，記成K(G)，稱為G的連通度。規(guī)定K(完全圖)=頂點(diǎn)數(shù)-1;K(不連通圖)=K(平凡圖)=0。K(G)=1時(shí)，割頂集中的那個(gè)頂點(diǎn)叫做割頂。沒有割頂?shù)膱D叫做塊，G中成塊的極大子圖叫做G的塊。4.1連通性的基本概念和定義下圖中，K(G2)=1,K(G3)=3,K(G4)=5-1=4;G3與G4是塊;G2中有兩個(gè)三角形塊。4.1連通性的基本概念和定義邊連通度K'(G)E'是連通圖G的一個(gè)邊子集。在G中刪去E'中的邊后圖不連通，則稱E'是G的橋集.若G中已無橋集E"，使得|E"|<|E'|，則稱|E'|為G的邊連通度，記成K'(G)。|E'|=1時(shí)，E'中的邊叫做橋。規(guī)定K'(不連通圖)=0,K'(完全圖)=頂點(diǎn)數(shù)-1。4.1連通性的基本概念和定義下圖中，K'(G2)=2,K'(G3)=3,K'(G4)=5-1=4。G2,G3,G4中無橋。4.1連通性的基本概念和定義對(duì)于任意一個(gè)連通圖G，在計(jì)算出上述兩個(gè)量后，我們可以給該圖下一個(gè)定義:K(G)>M,G叫做M連通圖;K'(G)>M時(shí)，G稱為M邊連通圖。下面給出連通圖G的兩個(gè)特征:1.K(G)≤K'(G)≤G的頂點(diǎn)度數(shù)的最小值2.頂點(diǎn)數(shù)大于2的2連通圖的充分必要條件是任兩個(gè)頂點(diǎn)在一個(gè)圈上。4.2深度優(yōu)先搜索(dfs)深度優(yōu)先搜索過程:先任取一個(gè)頂點(diǎn)為根，記為U，作為深搜的起始出發(fā)點(diǎn)，設(shè)置U頂點(diǎn)為已訪問。再?gòu)腢的鄰接頂點(diǎn)中，任選W頂點(diǎn)，對(duì)應(yīng)關(guān)聯(lián)邊(U,W)，將該邊定方向?yàn)閁到W。此時(shí)邊(U,W)稱為“已檢查”，且作為樹枝邊且加入樹枝邊集合中，U稱為W的父親點(diǎn)，記為U=father(W)。再以W頂點(diǎn)作為新的出發(fā)點(diǎn)，重復(fù)上面步驟4.2深度優(yōu)先搜索(dfs)一般情況下當(dāng)訪問某頂點(diǎn)X時(shí)，有兩種可能