《圖論的基本思想及方法》ppt課件

1、圖論的根本思想及方法由一道標題淺談概述概述 信息學(xué)中的圖論問題層出不窮，信息學(xué)中的圖論問題層出不窮，變化多端，惟有掌握其根本思想變化多端，惟有掌握其根本思想和方法，才干以不變應(yīng)萬變！和方法，才干以不變應(yīng)萬變！ 下面經(jīng)過實例主要從兩方面論述下面經(jīng)過實例主要從兩方面論述圖論的根本思想：圖論的根本思想： 一、合理選擇圖論模型一、合理選擇圖論模型 二、充分發(fā)掘和利用圖的性質(zhì)二、充分發(fā)掘和利用圖的性質(zhì)雪山上有一個滑雪場?；┭┥缴嫌幸粋€滑雪場?；﹫鲇善脚_和滑道組成。每個平場由平臺和滑道組成。每個平臺有不同的高度，有一個最高臺有不同的高度，有一個最高點和一個最低點?；楞暯又c和一個最低點?；楞暯又鴥?/p>

2、個不同的平臺，方向是從較兩個不同的平臺，方向是從較高點到較低點。高點到較低點。一些工人要檢查滑道。每個工一些工人要檢查滑道。每個工人從最高點滑到最低點，滑行人從最高點滑到最低點，滑行途徑上的滑道便都被檢查了。途徑上的滑道便都被檢查了。每個工人只能滑行一次。不同每個工人只能滑行一次。不同工人的滑行途徑可以有一樣的工人的滑行途徑可以有一樣的滑道。滑道。 例題：滑雪者例題：滑雪者(POI 2002)問題：最少要多少個工人問題：最少要多少個工人才干檢查完一切的滑道呢？才干檢查完一切的滑道呢？Nar.in6 2 2 32 3 42 4 51 62 4 6Nar.out4頂點個數(shù)頂點個數(shù)n (1n5000

3、)從左到右描畫第從左到右描畫第i i個頂點發(fā)出個頂點發(fā)出邊的另一個端點邊的另一個端點 例題：滑雪者例題：滑雪者(POI 2002)123456選擇模型選擇模型(1)網(wǎng)絡(luò)流模型網(wǎng)絡(luò)流模型 最高點最高點 最低點最低點 每條滑道可以多次經(jīng)過每條滑道可以多次經(jīng)過 每條滑道必需被檢查每條滑道必需被檢查 有向無環(huán)圖有向無環(huán)圖網(wǎng)絡(luò)的源點 s網(wǎng)絡(luò)的匯點 t邊下界 l 為1邊上界 u 為分析樣例，發(fā)現(xiàn)問題中有如下關(guān)鍵點：分析樣例，發(fā)現(xiàn)問題中有如下關(guān)鍵點：很容易想到建立一個網(wǎng)絡(luò)流模型：很容易想到建立一個網(wǎng)絡(luò)流模型：最高點最低點st1,1,1,1,1,1,1,1,1,確定所求目的確定所求目的建立模型后，可以確定要求

4、的目的：建立模型后，可以確定要求的目的：求圖求圖G中一個最小可行流，滿足：中一個最小可行流，滿足：st213122111a) 每條邊的流量大于等于下界每條邊的流量大于等于下界b) 從源點流出的總流量最小從源點流出的總流量最小求最小流的方法求最小流的方法如何求圖如何求圖G的最小流呢的最小流呢求最小流可以分成兩步：求最小流可以分成兩步：1求出圖求出圖G上的可行流上的可行流 f2將可行流將可行流 f 轉(zhuǎn)化成最小流轉(zhuǎn)化成最小流 對于有上下界的網(wǎng)絡(luò)，通常用構(gòu)造附對于有上下界的網(wǎng)絡(luò)，通常用構(gòu)造附加網(wǎng)絡(luò)的方法求可行流。加網(wǎng)絡(luò)的方法求可行流。 但是察看圖但是察看圖G可以發(fā)現(xiàn)，邊的上界都可以發(fā)現(xiàn)，邊的上界都是無

5、窮大，也就是說沒有流量上限。是無窮大，也就是說沒有流量上限。jistui,j = 因此可以利用這個性質(zhì)構(gòu)造可行流因此可以利用這個性質(zhì)構(gòu)造可行流求可行流的方法求可行流的方法jist求可行流的方法求可行流的方法枚舉每條流量為枚舉每條流量為0的邊，設(shè)為的邊，設(shè)為(i, j)恣意找到一條從恣意找到一條從 s 到到 i 的途徑的途徑和一條從和一條從 j 到到 t 的途徑的途徑那么那么s i j t 便是一條可行的流，便是一條可行的流，將這條途徑上的邊流量加將這條途徑上的邊流量加1， 便滿足便滿足了邊了邊(i, j)的容量下界的容量下界fi,j = 0fi,j = 1+1+1f 可行jist求最小流求最小

6、流設(shè)用上法求出的可行流的總流量設(shè)用上法求出的可行流的總流量為為F，這個可行流能夠，這個可行流能夠“過剩過剩。因此要將多余的流從匯點因此要將多余的流從匯點“退回退回到源點。到源點。f 最小求最小流求最小流sjit在新圖中，原圖在新圖中，原圖G的邊的邊(i, j)拆成兩條邊：拆成兩條邊：邊邊(i, j), ui,j = fi,j li,j，li,j = 0邊邊(j, i), uj,i = ui,j fi,j，lj,i = 0fi,jfi,j li,jui,j fi,j回退回退“過剩流量可以用如下方法：過剩流量可以用如下方法：求最小流求最小流在新圖中，從在新圖中，從 t 到到 s 求出一個最大求出一

7、個最大流，令這個最大流的總流量為流，令這個最大流的總流量為F。sjitfi,j li,jui,j fi,j可得圖可得圖G的最小流的流量為的最小流的流量為F F。算法一的復(fù)雜度算法一的復(fù)雜度 易知構(gòu)造可行流的時間復(fù)雜度為易知構(gòu)造可行流的時間復(fù)雜度為O(nm) 修正可行流所用的最大流算法時間復(fù)修正可行流所用的最大流算法時間復(fù)雜度為雜度為O(mC)，其中，其中C為增廣的次數(shù)。為增廣的次數(shù)。 由于圖由于圖G是平面圖，所以邊數(shù)是是平面圖，所以邊數(shù)是O(n)級級別。而由可行流構(gòu)造方法可知，增廣次別。而由可行流構(gòu)造方法可知，增廣次數(shù)數(shù)C也是也是O(n)級別。級別。總的復(fù)雜度為總的復(fù)雜度為O(n2)選擇模型選

8、擇模型(2)另辟蹊徑的偏序集另辟蹊徑的偏序集 能否存在效率更高的算法？能否存在效率更高的算法？下面引見的偏序集模型將更好的下面引見的偏序集模型將更好的處理此問題。處理此問題。 算法一可以很迅速的處理原題數(shù)據(jù)。算法一可以很迅速的處理原題數(shù)據(jù)。 但當?shù)攏的范圍擴展時，算法一便無能的范圍擴展時，算法一便無能為力了。為力了。偏序集的定義偏序集的定義偏序集是一個集合偏序集是一個集合P和一個偏序關(guān)和一個偏序關(guān)系系 ，滿足以下性質(zhì)：，滿足以下性質(zhì)：自反性：自反性： 一切一切xP，都有，都有x x。反對稱性：反對稱性：一切一切x,yP，假設(shè)，假設(shè)x y且且y x，那么，那么x = y。傳送性：傳送性：一切一

9、切x,y,z P，假設(shè)，假設(shè)x y且且y z，那么，那么x z。偏序集的相關(guān)概念偏序集的相關(guān)概念 鏈：鏈是鏈：鏈是P的一個子集的一個子集C，在偏序，在偏序關(guān)系關(guān)系下，它的每一對元素都是可下，它的每一對元素都是可比的。比的。 反鏈：反鏈是反鏈：反鏈是P的一個子集的一個子集A，在偏，在偏序關(guān)系序關(guān)系下，它的每一對元素都是下，它的每一對元素都是不可比的。不可比的。 對于屬于對于屬于P的兩個元素的兩個元素x、y，假設(shè)有，假設(shè)有x y 或或 y x，那么，那么x和和y被稱作是可比的被稱作是可比的，否那么被稱為不可比的。，否那么被稱為不可比的。問題的偏序集模型問題的偏序集模型 E中的偏序關(guān)系：中的偏序關(guān)系

10、：對于邊對于邊u,vE, u v當且僅當當且僅當u = v或圖或圖G中存在中存在 v到到 u的一條途徑。的一條途徑。圖圖G可以定義成一個偏序集可以定義成一個偏序集E： E中的元素是圖中的元素是圖G中的邊；中的邊；uvu v問題的偏序集模型問題的偏序集模型因此，原問題可以重新用偏序集言語因此，原問題可以重新用偏序集言語表述為表述為 ：將偏序集將偏序集E, 劃分成最少的鏈，劃分成最少的鏈，使得這些鏈的并集包含一切使得這些鏈的并集包含一切E中的元中的元素。素。 可以發(fā)現(xiàn)，圖可以發(fā)現(xiàn)，圖G中從最高點到最低點中從最高點到最低點的途徑對應(yīng)了的途徑對應(yīng)了E的一個鏈。的一個鏈。目的的轉(zhuǎn)化目的的轉(zhuǎn)化 直接計算鏈

11、的最少個數(shù)直接計算鏈的最少個數(shù)與網(wǎng)絡(luò)流沒有差別與網(wǎng)絡(luò)流沒有差別 唯有唯有繼續(xù)轉(zhuǎn)化目的繼續(xù)轉(zhuǎn)化目的目的的轉(zhuǎn)化目的的轉(zhuǎn)化 鏈和反鏈的計數(shù)滿足以下關(guān)系：鏈和反鏈的計數(shù)滿足以下關(guān)系：Dilworth定理定理 令令(E, )是一個有限偏序是一個有限偏序集，并令集，并令LA是是E中最大反鏈的大小，中最大反鏈的大小，SC是將是將E劃分成最少的鏈的個數(shù)。在劃分成最少的鏈的個數(shù)。在E中，中，有有 LA = SC。求求E中最長反鏈的大小中最長反鏈的大小 目的最終轉(zhuǎn)化為：目的最終轉(zhuǎn)化為：求最長的反鏈求最長的反鏈由偏序集由偏序集E的定義可以知道：的定義可以知道：偏序集偏序集E中的反鏈對應(yīng)著圖中的反鏈對應(yīng)著圖G中的一些

12、邊，中的一些邊，其中恣意兩條邊之間都不能互達。其中恣意兩條邊之間都不能互達。右圖橙色線段便是樣例的最長反鏈右圖橙色線段便是樣例的最長反鏈假設(shè)用一條線將最長反假設(shè)用一條線將最長反鏈所對應(yīng)的邊從左到右鏈所對應(yīng)的邊從左到右連起來連起來 那么這條線不會與平面那么這條線不會與平面圖中的其它邊相交圖中的其它邊相交 ！這些線段滿足如下性質(zhì)：這些線段滿足如下性質(zhì)：求最長的反鏈求最長的反鏈換句話說，將最長反鏈所對換句話說，將最長反鏈所對應(yīng)的邊從左到右陳列好，相應(yīng)的邊從左到右陳列好，相鄰的兩條邊一定是在同一個鄰的兩條邊一定是在同一個域閉曲面中。域閉曲面中。 結(jié)論一結(jié)論一所謂域，是指由從極高點到極低所謂域，是指由從

13、極高點到極低點的兩條獨立途徑圍成的一個曲點的兩條獨立途徑圍成的一個曲面，在這個曲面里沒有其他的點面，在這個曲面里沒有其他的點和邊。和邊。極高點極低點左邊境右邊境求最長的反鏈求最長的反鏈令令f(x)表示圖表示圖G中在邊中在邊x左邊的平面區(qū)域左邊的平面區(qū)域中以中以x結(jié)尾的最長反鏈的長度。結(jié)尾的最長反鏈的長度。 由結(jié)論一可以用遞推方法計算最長反鏈：由結(jié)論一可以用遞推方法計算最長反鏈：求最長的反鏈求最長的反鏈設(shè)設(shè)x在某個域在某個域F的右邊境上，的右邊境上，有遞推式：有遞推式：f (x) = max f (y) + 1 (y屬于屬于F的左邊境的左邊境遞推式遞推式(1)f (y)f (x)= f (y)

14、+ 1ABCD因此只需求將一切因此只需求將一切的域求出來，然后的域求出來，然后按照一定的順序，按照一定的順序，在每個域上運用遞在每個域上運用遞推式推式(1)求解每條邊求解每條邊 的的 f 函數(shù)。函數(shù)。一定的順序求最長的反鏈求最長的反鏈遞推的順序遞推的順序一定的順序一定的順序如何確定遞推的順序呢？如何確定遞推的順序呢？一個域可以進展遞推的前提條件一個域可以進展遞推的前提條件它左邊境上的邊的它左邊境上的邊的 f 函數(shù)都曾經(jīng)求出函數(shù)都曾經(jīng)求出以此可以確定遞推順序：假設(shè)域以此可以確定遞推順序：假設(shè)域B左邊境上左邊境上的某條邊在域的某條邊在域A的右邊境上，那么的右邊境上，那么A一定先一定先于于B進展遞推

15、。進展遞推。ABAB先于留意到，標題中的輸入文件格式滿足：留意到，標題中的輸入文件格式滿足：對于恣意頂點，和它相鄰的點曾經(jīng)對于恣意頂點，和它相鄰的點曾經(jīng)從左到右排好序。從左到右排好序。因此很容易想到因此很容易想到一個方法，可以一個方法，可以按照遞推順序找按照遞推順序找到一切的域！到一切的域！DFS深度優(yōu)先深度優(yōu)先遍歷遍歷算法的選擇算法的選擇找到了遞推關(guān)系，接下來只需求選擇適宜找到了遞推關(guān)系，接下來只需求選擇適宜的算法求出圖的算法求出圖G中一切的域來進展遞推。中一切的域來進展遞推。算法設(shè)計算法設(shè)計DFS對圖對圖G進展深度優(yōu)先遍歷，圖進展深度優(yōu)先遍歷，圖G中中的頂點在遍歷中有三種形狀：的頂點在遍歷

16、中有三種形狀：一開場，一切點都處于未一開場，一切點都處于未遍歷的形狀。遍歷的形狀。當遍歷到一個點，但沒有檢當遍歷到一個點，但沒有檢查完它發(fā)出的邊時，標志這查完它發(fā)出的邊時，標志這個點為未擴展完的形狀。個點為未擴展完的形狀。當一個點發(fā)出的邊都被檢當一個點發(fā)出的邊都被檢查完時，這個點標志為擴查完時，這個點標志為擴展終了形狀。展終了形狀。在遍歷中用一個指針在遍歷中用一個指針prev記錄記錄v最新的前驅(qū)結(jié)點。最新的前驅(qū)結(jié)點。當當u1擴展到擴展到v時，時，后來檢查后來檢查u2發(fā)出的邊發(fā)出的邊(u2, v)時，時，指針指針pre的更新方式如下：的更新方式如下：prev = u1。prev = u2。雖然雖

17、然v曾經(jīng)擴展終了，但曾經(jīng)擴展終了，但仍更新仍更新prev ：u1u2v算法設(shè)計算法設(shè)計DFS可知，點可知，點v 一定是邊一定是邊(u, v)所在域的極低點。所在域的極低點。根據(jù)根據(jù)DFS中點的形狀和指針中點的形狀和指針pre就就可以按如下方法確定圖可以按如下方法確定圖G中的域中的域：當檢查點當檢查點u的某條邊時，發(fā)的某條邊時，發(fā)現(xiàn)邊的另一個頂點現(xiàn)邊的另一個頂點v曾經(jīng)被曾經(jīng)被擴展終了。擴展終了。而而prev和和u最近公共祖先最近公共祖先點一定是域的極高點。點一定是域的極高點。vprevuvh極高點極高點極低點極低點算法設(shè)計算法設(shè)計DFS尋覓尋覓prev和和u的最近公的最近公共祖先，只需求利用共祖

18、先，只需求利用pre回溯尋覓回溯尋覓v的祖先，第一的祖先，第一個未被擴展終了的祖先個未被擴展終了的祖先便是域的極高點。便是域的極高點。從從v到到prev再回溯到再回溯到vh的的途徑便是域的左邊境。途徑便是域的左邊境。從極高點到從極高點到u再到再到v的途的途徑便是域的右邊境。徑便是域的右邊境。vprevuvh極高點極低點算法設(shè)計算法設(shè)計DFSvlvh極高點極低點找到域之后，域左邊境找到域之后，域左邊境上的邊都被遍歷過，上的邊都被遍歷過，f函數(shù)都曾經(jīng)求出。函數(shù)都曾經(jīng)求出。Ff (x) = max f (y) + 1可見，可見，DFS尋覓圖尋覓圖G的的域的同時，曾經(jīng)完成域的同時，曾經(jīng)完成 f函數(shù)的求

19、解。函數(shù)的求解。問題處理問題處理算法設(shè)計算法設(shè)計DFSf (y)f (x)算法二的復(fù)雜度算法二的復(fù)雜度對每一個點進展對每一個點進展DFS遍歷，復(fù)雜度為遍歷，復(fù)雜度為O(|E|)；回溯尋覓每個域邊境上的邊，并且進展回溯尋覓每個域邊境上的邊，并且進展遞推求解。由于是平面圖，每條邊最多遞推求解。由于是平面圖，每條邊最多屬于兩個不同域的邊境，因此這一步的屬于兩個不同域的邊境，因此這一步的復(fù)雜度為復(fù)雜度為O(|E|+|F|)。由于原題給出的圖是平面圖，根據(jù)歐拉定由于原題給出的圖是平面圖，根據(jù)歐拉定理，邊數(shù)理，邊數(shù)|E|和域數(shù)和域數(shù)|F|都是都是O(n)級別的。級別的?？偟膹?fù)雜度為總的復(fù)雜度為O(n) 算

20、法不斷接根據(jù)標題描畫建立了網(wǎng)絡(luò)流算法不斷接根據(jù)標題描畫建立了網(wǎng)絡(luò)流模型，表達了原題的網(wǎng)絡(luò)有向無環(huán)圖特模型，表達了原題的網(wǎng)絡(luò)有向無環(huán)圖特性。性?？偨Y(jié)總結(jié)沒有利用圖沒有利用圖G平平面圖的性質(zhì)面圖的性質(zhì)解法具有普通性，適解法具有普通性，適用任何有向無環(huán)圖用任何有向無環(huán)圖算法一的效率不算法一的效率不是最優(yōu)是最優(yōu)直接從定義下手的直接從定義下手的思索方式值得自創(chuàng)思索方式值得自創(chuàng)總結(jié)總結(jié)算法二很好的利用偏序集模型實現(xiàn)了問算法二很好的利用偏序集模型實現(xiàn)了問標題的的轉(zhuǎn)變，從原來的網(wǎng)絡(luò)流問題回標題的的轉(zhuǎn)變，從原來的網(wǎng)絡(luò)流問題回歸到問題本身的平面圖上，完好的提示歸到問題本身的平面圖上，完好的提示了問題的本質(zhì)。了問題的本質(zhì)。 兩個算法思索歷程的共同點兩個算法思索歷程的共同點實踐問題實踐問題尋覓適宜的圖論模型尋覓適宜的圖論模型以圖論模型為以圖論模型為平臺發(fā)掘問題平臺發(fā)掘問題的性質(zhì)的性質(zhì)設(shè)計相應(yīng)設(shè)計相應(yīng)的算法的算法處理問題處理問題結(jié)語結(jié)語“模型模型圖論根本思想的精華圖論根本思想的精華處理圖論問題的關(guān)鍵處理圖論問題的關(guān)鍵建立模型建立模型熟練掌握經(jīng)典模型熟練掌握經(jīng)典模型勇于探求，大膽創(chuàng)新勇于探求，大膽創(chuàng)新發(fā)掘利用發(fā)掘利用模型性質(zhì)模型性質(zhì)獨具慧眼獨具慧眼一擊中的一擊中的樣例的模擬下面在樣例上模擬運轉(zhuǎn)算法二，闡明算法二是如何執(zhí)行的：123456從結(jié)點1開場遍歷不斷深搜到結(jié)點6