圖論基礎(信息學奧賽)

圖論及其算法吳聞第一章

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

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

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

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