1、圖論及其算法吳聞第一章 基本概念 1.1 引言 1.2 圖的定義 1.3 道路和回路 1.4 樹1.1 引言 圖論是一個應用十分廣泛而又極其有趣的數學分支。物理、化學、生物、科學管理、計算機等各個領域都可找到圖論的足跡。 介紹幾個圖論有關的簡單例子1.1 引言 例1 下圖是一個公路網，V1 ,V2,.,V10是一些城鎮，每條線旁邊的數字代表這一段公路的長度。現在問，要從V1把貨物運到V10，走哪條路最近?1.1 引言 例1實際上，就是圖論中的求最短路徑問題。在現實中有很多此類問題，所以圖論中求最短路徑算法是一個非常經典和重要的算法。1.1 引言 例2 下圖是一個公路網，V1 ,V2,.,V10

2、看成公路網的一個站點，若這個公路網目前被敵方占領。請分析一下，最少需要破壞其公路網的幾個站點，就可摧毀敵方整個運輸線1.1 引言 例2屬于圖的連通性問題。找出圖中的割頂集，就是問題的解。軍事指揮中很多此類問題。1.1 引言 例3 飛行大隊有若干個來自各地的駕駛員，專門駕駛一種型號的飛機，這種飛機每架有兩個駕駛員。由于種種原因，例如相互配合的間題，有些駕駛員不能在同一架飛機上飛行，問如何搭配駕駛員，才能使出航的飛機最多。1.1 引言 例3 用V1 ,V2,.,V10代表這10個駕駛員。如果兩個人可以同機飛行，就在代表他們兩個之間連一條線;兩個人不能同機飛行，就不連。例如V1和V2可以同機飛行，而

3、V1和V 3就不行。1.1 引言 例3此類問題屬于圖的最大匹配問題 將實際生活中的事物分析轉化為圖論問題的實例還很多.1.2 圖的定義 圖：由若干個不同頂點與連接其中某些頂點的邊所組成的圖形。 圖的表示：通常用一個大寫字母G來表示圖，用V來表示所有頂點的集合，E表示所有邊的集合，并且記成G=(V,E)。1.2 圖的定義 子圖：如果對圖G=(V,E)與G=(V,E),G的頂點集是G的頂點集的一個子集(VV),G的邊集是G的邊集的一個子集(EE)，我們說G是G的子圖1.2 圖的定義 環：如果一條邊，它的起點和終點相同，這樣的邊稱為環。 平行邊：若連接兩個頂點的邊有多條，則這些邊稱之為平行邊。 孤立

4、點：不與任何邊關聯的頂點稱為孤立點。1.2 圖的定義 簡單圖：如果一個圖沒有環，并且每兩個頂點之間最多只有一條邊，這樣的圖稱之為簡單圖。在簡單圖中，連接Vi與Vj的邊可以記成(Vi,Vj) 完全圖：如果G是一個簡單圖，并且每兩個頂點之間都有一條邊，我們就稱G為完全圖。通常將具有n個頂點的完全圖記為Kn。 二分圖：如果G是一個簡單圖，它的頂點集合V是由兩個沒有公共元素的子集X= X1,X2,.,Xn與Y= Yl ,Y2, .,Ym組成的，并且Xi與Xj (1i , jn ) ,Ys與Yt(1s,tm)之間沒有邊連接，則G叫做二分圖。1.2 圖的定義 簡單圖、完全圖、二分圖1.2 圖的定義 完全二

5、分圖：如果在二分圖G中，IXI=N, IYI=M，每一個XiX與每一個YjY有一條邊相連，則G叫做完全二分圖1.2 圖的定義 如果G是一個N個頂點的簡單圖，從完全圖Kn中把屬于G的邊全部去掉后，得到的圖稱為G的補圖，通常記為G。 一個圖的補圖的補圖就是自身。1.2 圖的定義 相鄰：如果圖G的兩個頂點Vi與Vj之間有邊相連，我們就說Vi與Vj是相鄰的，否則就說Vi與Vj是不相鄰的。如果頂點V是邊e的一個端點，就說頂點V與邊e是相鄰的，e是從V引出的邊。 度數：從一個頂點V引出的邊的條數，稱為V的度數，記作d(V)。1.2 圖的定義 下圖中，d(V1)=d(V2)=d(V3)=d(V4)=d(V5

6、)=5-1=4,d(Y3)=2等等。1.2 圖的定義 K度正則圖：把每個頂點的度數為常數K的圖叫做K度正則圖。 經常使用下面兩個符號:1.2 圖的定義 從頂點度數問題的討論中，引出一些有趣的結論: 1. 2.對于任意的圖G，奇次頂點的個數一定是偶數。1.2 圖的定義 例1、空間是否有這樣的多面體存在，它們有奇數個面，而每個面又有奇數條邊?分析:根據題意，可以構造一個圖，以面為頂點，當且僅當兩個面有公共棱時，則在G的相應兩頂點間連一條邊，得到圖G。依題意，圖的頂點個數是奇數，而且每個頂點的度數d(V)是奇數，從而 也是奇數，與結論1相違，故這種多面體不存在。1.2 圖的定義 例2、晚會上大家握手

7、聯歡，問是否會出現握過奇次手的人是奇數的情況? 分析:一個圖，以人為頂點，兩人握手時，則相應的兩個頂點之間連一條邊，于是每人握手的次數即相應頂點的度數。由結論2，奇次頂點的個數總是偶數，所以握過奇次手的人數是奇數的情況不可能出現。1.3 道路與回路 道路：在圖G中，一個由不同的邊組成的序列e1,e2.,eg，如果ei是連接Vi-1與Vi(i=1,2,.,g)的，我們就稱這個序列為從V0到Vg的一條道路，數g稱為路長，V0與Vg稱為這條道路的兩個端點，Vi(1=i=g-1)叫做道路的內點。如果G是簡單圖，這條道路也可以記作(V0,V1,.,Vg)1.3 道路與回路 下圖中e1,e2,e3,e4,

8、e5,e6組成一條道路1.3 道路與回路 軌道：在道路的定義中，并不要求V0至Vg，互不相同。如果V0至Vg互不相同，這樣的道路稱為軌道，記成P(V0,Vg) 。 回路：V0=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的道路，那么該條道路上的每一個內點Vi(1=

9、i0。這時對于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加上去，每次加的時候，要保持“沒有圈”的性質，在加了N-1條邊(N是頂點個數)后，G1便成

10、為所要求的最小生成樹了。3. 1求無向圖的最小生成樹二、最小生成樹的計算 算法步驟如下：第四章 圖的連通性 4.1 連通性的基本概念和定義 4.2 深度優先搜索(dfs) 4.3 求割頂和塊 4.4 求極大強連通子圖 4.5 求最小點基 4.6 可靠通訊網的構作4.1 連通性的基本概念和定義 在無向圖G中，如果從頂點V到頂點V有路徑，則稱V和V是連通的。 如果對于圖中任意兩個頂點Vi,VjV,Vi和Vj都是連通的，則稱該圖為連通圖。 所謂連通分量指的是無向圖中的極大連通子圖4.1 連通性的基本概念和定義 在有向圖G中，如果對于每一對Vi,VjV,ViVj,從Vi到Vj，和從Vi到Vj都存在路徑

11、，則稱G是強連通圖。 有向圖中的極大強連通子圖稱作有向圖的強連通分量。4.1 連通性的基本概念和定義 一個連通圖的生成樹是一個極小連通子圖，它含圖的全部頂點，但只有足以構成一棵樹的N-1條邊超過N-1條邊必有回路，就不再是樹了。4.1 連通性的基本概念和定義 為更精確的描述圖的連通性，還需引入兩個概念： 頂連通度K(G) 邊連通度K(G)4.1 連通性的基本概念和定義頂連通度： V是連通圖G的一個頂點子集。在G中刪去V及與V相關聯的邊后圖不連通，則稱V是G的割頂集。 最小割頂集中頂點的個數，記成K(G)，稱為G的連通度。規定K(完全圖)=頂點數-1;K(不連通圖)=K(平凡圖)=0。 K(G)

12、=1時，割頂集中的那個頂點叫做割頂。 沒有割頂的圖叫做塊，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|M,G叫做M連通圖;K (G) M時，G稱為M邊連通圖。 下面給出連通圖G的兩個特征: 1.K(G)K(G)G的頂點度數的最小值 2.頂點數大于2的2連通圖的充分必要條件是任兩個頂點在一個圈上。4.2 深度優先搜索(dfs

13、 )深度優先搜索過程: 先任取一個頂點為根，記為U，作為深搜的起始出發點，設置U頂點為已訪問。再從U的鄰接頂點中，任選W頂點，對應關聯邊(U,W)，將該邊定方向為U到W。此時邊(U,W)稱為“已檢查”，且作為樹枝邊且加入樹枝邊集合中，U稱為W的父親點，記為U=father(W)。 再以W頂點作為新的出發點，重復上面步驟4.2 深度優先搜索(dfs )一般情況下當訪問某頂點X時，有兩種可能: 1、如果X頂點的所有關聯邊被檢查過了，則回溯至X的父親頂點，從father(X)再繼續搜索，此時X頂點已無未用過的關聯邊; 2、如存在X頂點未用過的關聯邊，則任選其中一邊(X,Y)，對其定向為從X到Y,此時

14、說邊(X,Y)正等待檢查。4.2 深度優先搜索(dfs )檢查結果有兩種情況: 1.如Y頂點從未被訪問過，則順著(X,Y)邊訪問Y，下一步從Y開始繼續搜索。此時(X,Y)是前向邊，且頂點X=father(Y)，圖上用實線表出; 2.如Y頂點已被訪問過，則再選一X頂點未用過的關聯邊。此時(X ,Y)是后向邊，用虛線表出。4.2 深度優先搜索(dfs ) 此時，(X,Y)的歸屬已明確，(X,Y)就檢查完畢。在dfs搜索期間，將頂點X被首次訪問的序號作為頂點的dfn值，記為dfn(X)，如dfn(X)=i，則X是深搜過程中第i個被訪問的頂點，dfn(X)稱為X的深度優先搜索序數，當搜索返回根時，連通

15、圖的所有頂點都訪問完畢。現在圖中的邊都定了方向，且分成前向邊以及后向邊(虛線)，前向邊(實線)組成的有向樹，稱為dfs樹。4.2 深度優先搜索(dfs ) 對左圖進行dfs搜索得到右圖的dfs樹。每個頂點旁數字為頂點dfn值。4.2 深度優先搜索(dfs ) 無向圖G的dfs算法分析。4.2 深度優先搜索(dfs ) dfs樹由前向邊組成，若非連通圖，則對每一個連通分量進行一次dfs搜索，結果產生一個由若干dfs樹組成的森林。 如果從U到W有樹邊組成的有向路，則稱U和W有直系關系，U稱為W的祖先點，W稱為U的后代點。如(U,W)是樹中一條邊，U又確切地稱為W的父親點，W也可稱為U的兒子點。一個

16、頂點可有多個兒子點，頂點U和它的所有后代點組成關于樹中以U為根的子樹。4.2 深度優先搜索(dfs ) 有向圖的dfs本質上近似無向圖，區別在于搜索只能順邊的方向去進行(有向邊，簡稱弧)。有向圖中的弧根據被檢查情況可有4種，一條未檢查的弧(U,W)可按如下4種情況，分類歸劃成(其中2,3,4所述的三種情況中，設W已訪問過)：4.2 深度優先搜索(dfs ) 1. W是未訪問過的點，(U,W)歸入樹枝弧 2. W是U的已形成的dfs森林中直系后代點，則(U,W)稱為前向弧。無論(U,W)是樹枝弧還是前向弧，dfn(W)dfn(U)。 3. W是U的已形成的dfs森林中直系祖先點，則(U,W)稱為

17、后向弧。 4. U和W在已形成的dfs森林中沒有直系上下關系，并且有dfn(W)dfn(U)這種類型的橫叉弧。4.2 深度優先搜索(dfs )4.2 深度優先搜索(dfs ) 下圖為有向圖的dfs示例： , ,是樹枝弧，組成dfs森林(用粗線表示); 是后向弧;是前向弧; ,是橫叉弧。4.2 深度優先搜索(dfs ) 有向圖和無向圖的dfs算法基本相似4.3 求割頂和塊 割頂：如果一個連通圖，刪除某一頂點，不在連通，這個頂點就稱為割頂。 塊：一個連通圖，如果刪除任一頂點不會破壞連通性，即沒有割頂，這個連通圖稱為塊。4.3 求割頂和塊 分析一個由無向圖表示的通訊網，頂點看作是通訊站，無向邊代表兩

18、個通訊站之間可以互相通訊。問: 1.若其中一個站點出現故障，是否會影響系統正常工作;(求割頂) 2.這個通訊網可以分成哪幾個含站點盡可能多的子網，這些子網內的任一站點出現故障，都不會影響子網工作。(求塊，即沒有割頂的連通子圖)4.3 求割頂和塊給定dfs樹，割頂的判斷： 1.如U不是根，U成為割頂當且僅當存在U的某一個兒子頂點S，從S或S的后代點到U的祖先點之間不存在后向邊。 2.如被選為根，則成為割頂當且僅當它有不止一個兒子點4.3 求割頂和塊給定dfs樹，割頂的判斷：4.3 求割頂和塊 割頂的判斷法則是構思算法的精華，為此引入一種頂點U的標號函數LOW (U)=min(dfn(U) ,LOW(S),dfn(W) 其中:S是U的兒子，(U,W)是后向邊。 顯然LOW (U)值恰是U或U的后代所能追溯到的最早(序號小)的祖先點序號。一般約定，頂點自身也認為自己是祖先點。所以有可能LOW (U) =dfn(U)或LOW(U)=dfn(W)。4.3 求割頂和塊 利用標號函數LOW，我們可以將割頂判定1重新描述成: 頂點U作為G的割頂當且僅當U有一個兒子S，使得LOW (S)dfn (U)，即S和S的后代不會追溯到比U更早的祖先點。4.3 求割頂和塊 LOW(U)值的計算步驟如下: 在