圖論的基本思想及方法.ppt

圖論的基本思想及方法,湖南省長郡中學(xué) 任愷,由一道題目淺談,概述,信息學(xué)中的圖論問題層出不窮，變化多端，惟有掌握其基本思想和方法，才能以不變應(yīng)萬變！,下面通過實(shí)例主要從兩方面論述圖論的基本思想：,一、合理選擇圖論模型,二、充分挖掘和利用圖的性質(zhì),雪山上有一個滑雪場?；﹫鲇善脚_和滑道組成。每個平臺有不同的高度，有一個最高點(diǎn)和一個最低點(diǎn)?；肋B接著兩個不同的平臺，方向是從較高點(diǎn)到較低點(diǎn)。,一些工人要檢查滑道。每個工人從最高點(diǎn)滑到最低點(diǎn)，滑行路徑上的滑道便都被檢查了。每個工人只能滑行一次。不同工人的滑行路徑可以有相同的滑道。,例題：滑雪者(POI 2002),問題：最少要多少個工人才能檢查完所有的滑道呢？,Nar.in 6 2 2 3 2 3 4 2 4 5 1 6 2 4 6,Nar.out 4,頂點(diǎn)個數(shù)n (1n5000),從左到右描述第i個頂點(diǎn)發(fā)出邊的另一個端點(diǎn),例題：滑雪者(POI 2002),1,2,3,4,5,6,選擇模型(1)網(wǎng)絡(luò)流模型,最高點(diǎn) 最低點(diǎn) 每條滑道可以多次通過 每條滑道必須被檢查 有向無環(huán)圖,網(wǎng)絡(luò)的源點(diǎn) s,網(wǎng)絡(luò)的匯點(diǎn) t,邊下界 l 為1,邊上界 u 為,分析樣例，發(fā)現(xiàn)問題中有如下關(guān)鍵點(diǎn)：,很容易想到建立一個網(wǎng)絡(luò)流模型：,最高點(diǎn),最低點(diǎn),s,t,確定所求目標(biāo),建立模型后，可以確定要求的目標(biāo)：,求圖G中一個最小可行流，滿足：,s,t,2,1,3,1,2,2,1,1,1,a) 每條邊的流量大于等于下界,b) 從源點(diǎn)流出的總流量最小,求最小流的方法,如何求圖G的最小流呢,求最小流可以分成兩步：,1）求出圖G上的可行流 f,2）將可行流 f 轉(zhuǎn)化成最小流,對于有上下界的網(wǎng)絡(luò)，通常用構(gòu)造附加網(wǎng)絡(luò)的方法求可行流。,但是觀察圖G可以發(fā)現(xiàn)，邊的上界都是無窮大，也就是說沒有流量上限。,ui,j = ,因此可以利用這個性質(zhì)構(gòu)造可行流,求可行流的方法,j,i,s,t,求可行流的方法,枚舉每條流量為0的邊，設(shè)為(i, j),任意找到一條從 s 到 i 的路徑和一條從 j 到 t 的路徑,那么s i j t 便是一條可行的流，將這條路徑上的邊流量加1， 便滿足了邊(i, j)的容量下界,fi,j = 0,fi,j = 1,+1,+1,f 可行,求最小流,設(shè)用上法求出的可行流的總流量為F，這個可行流可能“過?！?。,因此要將多余的流從匯點(diǎn)“退回”到源點(diǎn)。,f 最小,求最小流,s,在新圖中，原圖G的邊(i, j)拆成兩條邊：,邊(i, j), ui,j = fi,j li,j，li,j = 0,邊(j, i), uj,i = ui,j fi,j，lj,i = 0,回退“過?！绷髁靠梢杂萌缦路椒ǎ?求最小流,在新圖中，從 t 到 s 求出一個最大流，令這個最大流的總流量為F。,s,可得圖G的最小流的流量為F F。,算法一的復(fù)雜度,易知構(gòu)造可行流的時間復(fù)雜度為O(nm),修改可行流所用的最大流算法時間復(fù)雜度為O(mC)，其中C為增廣的次數(shù)。,由于圖G是平面圖，所以邊數(shù)是O(n)級別。而由可行流構(gòu)造方法可知，增廣次數(shù)C也是O(n)級別。,總的復(fù)雜度為O(n2),是否存在效率更高的算法？,選擇模型(2)另辟蹊徑的偏序集,下面介紹的偏序集模型將更好的解決此問題。,算法一能夠很迅速的解決原題數(shù)據(jù)。,但當(dāng)n的范圍擴(kuò)大時，算法一便無能為力了。,偏序集的定義,偏序集是一個集合P和一個偏序關(guān)系 ，滿足下列性質(zhì)：,自反性： 所有xP，都有x x。,反對稱性： 所有x,yP，若x y且y x，則x = y。,傳遞性： 所有x,y,z P，若x y且y z，則x z。,鏈：鏈?zhǔn)荘的一個子集C，在偏序關(guān)系下，它的每一對元素都是可比的。,偏序集的相關(guān)概念,反鏈：反鏈?zhǔn)荘的一個子集A，在偏序關(guān)系下，它的每一對元素都是不可比的。,對于屬于P的兩個元素x、y，若有x y 或 y x，則x和y被稱作是可比的，否則被稱為不可比的。,E中的偏序關(guān)系： 對于邊u,vE, u v當(dāng)且僅當(dāng)u = v或圖G中存在 v到 u的一條路徑。,問題的偏序集模型,圖G可以定義成一個偏序集E：,E中的元素是圖G中的邊；,u,v,u v,問題的偏序集模型,因此，原問題可以重新用偏序集語言表述為 ：,將偏序集（E, ）劃分成最少的鏈，使得這些鏈的并集包含所有E中的元素。,可以發(fā)現(xiàn)，圖G中從最高點(diǎn)到最低點(diǎn)的路徑對應(yīng)了E的一個鏈。,目標(biāo)的轉(zhuǎn)化,直接計(jì)算鏈的最少個數(shù),與網(wǎng)絡(luò)流沒有差別,唯有,繼續(xù)轉(zhuǎn)化目標(biāo),目標(biāo)的轉(zhuǎn)化,鏈和反鏈的計(jì)數(shù)滿足下列關(guān)系：,Dilworth定理 令(E, )是一個有限偏序集，并令LA是E中最大反鏈的大小，SC是將E劃分成最少的鏈的個數(shù)。在E中，有 LA = SC。,求E中最長反鏈的大小,目標(biāo)最終轉(zhuǎn)化為：,求最長的反鏈,由偏序集E的定義可以知道：,偏序集E中的反鏈對應(yīng)著圖G中的一些邊，其中任意兩條邊之間都不能互達(dá)。,右圖橙色線段便是樣例的最長反鏈,如果用一條線將最長反鏈所對應(yīng)的邊從左到右連起來,那么這條線不會與平面圖中的其它邊相交 ！,這些線段滿足如下性質(zhì)：,求最長的反鏈,換句話說，將最長反鏈所對應(yīng)的邊從左到右排列好，相鄰的兩條邊一定是在同一個域（閉曲面）中。 （結(jié)論一）,所謂域，是指由從極高點(diǎn)到極低點(diǎn)的兩條獨(dú)立路徑圍成的一個曲面，在這個曲面里沒有其他的點(diǎn)和邊。,求最長的反鏈,令f(x)表示圖G中在邊x左邊的平面區(qū)域中以x結(jié)尾的最長反鏈的長度。,由結(jié)論一可以用遞推方法計(jì)算最長反鏈：,求最長的反鏈,設(shè)x在某個域F的右邊界上，有遞推式：,f (x) = max f (y) + 1 (y屬于F的左邊界） 遞推式(1),f (y),f (x),= f (y) + 1,A,B,C,D,因此只需要將所有的域求出來，然后按照一定的順序，在每個域上運(yùn)用遞推式(1)求解每條邊 的 f 函數(shù)。,一定的順序,求最長的反鏈,遞推的順序,一定的順序,如何確定遞推的順序呢？,一個域能夠進(jìn)行遞推的前提條件,它左邊界上的邊的 f 函數(shù)都已經(jīng)求出,以此可以確定遞推順序：若域B左邊界上的某條邊在域A的右邊界上，則A一定先于B進(jìn)行遞推。,注意到，題目中的輸入文件格式滿足：,對于任意頂點(diǎn)，和它相鄰的點(diǎn)已經(jīng)從左到右排好序。,因此很容易想到一個方法，能夠按照遞推順序找到所有的域！,DFS深度優(yōu)先遍歷,算法的選擇,找到了遞推關(guān)系，接下來只需要選擇合適的算法求出圖G中所有的域來進(jìn)行遞推。,算法設(shè)計(jì)DFS,對圖G進(jìn)行深度優(yōu)先遍歷，圖G中的頂點(diǎn)在遍歷中有三種狀態(tài)：,在遍歷中用一個指針prev記錄v最新的前驅(qū)結(jié)點(diǎn)。,當(dāng)u1擴(kuò)展到v時，,后來檢查u2發(fā)出的邊(u2, v)時，,指針pre的更新方式如下：,prev = u1。,prev = u2。,雖然v已經(jīng)擴(kuò)展完畢，但仍更新prev ：,u1,u2,v,算法設(shè)計(jì)DFS,可知，點(diǎn)v 一定是邊(u, v)所在域的極低點(diǎn)。,根據(jù)DFS中點(diǎn)的狀態(tài)和指針pre就可以按如下方法確定圖G中的域：,當(dāng)檢查點(diǎn)u的某條邊時，發(fā)現(xiàn)邊的另一個頂點(diǎn)v已經(jīng)被擴(kuò)展完畢。,而prev和u最近公共祖先點(diǎn)一定是域的極高點(diǎn)。,v,prev,u,vh,算法設(shè)計(jì)DFS,尋找prev和u的最近公共祖先，只需要利用pre回溯尋找v的祖先，第一個未被擴(kuò)展完畢的祖先便是域的極高點(diǎn)。,從v到prev再回溯到vh的路徑便是域的左邊界。,從極高點(diǎn)到u再到v的路徑便是域的右邊界。,v,prev,u,vh,算法設(shè)計(jì)DFS,vl,vh,找到域之后，域左邊界上的邊都被遍歷過，f函數(shù)都已經(jīng)求出。,F,f (x) = max f (y) + 1,可見，DFS尋找圖G的域的同時，已經(jīng)完成 f函數(shù)的求解。,問題解決,算法設(shè)計(jì)DFS,f (y),f (x),算法二的復(fù)雜度,對每一個點(diǎn)進(jìn)行DFS遍歷，復(fù)雜度為O(|E|)；,回溯尋找每個域邊界上的邊，并且進(jìn)行遞推求解。由于是平面圖，每條邊最多屬于兩個不同域的邊界，因此這一步的復(fù)雜度為O(|E|+|F|)。,因?yàn)樵}給出的圖是平面圖，根據(jù)歐拉定理，邊數(shù)|E|和域數(shù)|F|都是O(n)級別的。,總的復(fù)雜度為O(n),算法一直接根據(jù)題目描述建立了網(wǎng)絡(luò)流模型，體現(xiàn)了原題的網(wǎng)絡(luò)有向無環(huán)圖特性。,總結(jié),沒有利用圖G平面圖的性質(zhì),解法具有一般性，適用任何有向無環(huán)圖,算法一的效率不是最優(yōu),直接從定義下手的思考方式值得借鑒,總結(jié),算法二很好的利用偏序集模型實(shí)現(xiàn)了問題目標(biāo)的轉(zhuǎn)變，從原來的網(wǎng)絡(luò)流問題回歸到問題本身的平面圖上，完整的揭示了問題的本質(zhì)。,兩個算法思考?xì)v程的共同點(diǎn),實(shí)際問題,尋找合適的圖論模型,以圖論模型為平臺挖掘問題的性質(zhì),設(shè)計(jì)相應(yīng)的算法,解決問題,結(jié)語,“模型”,圖論基本思想的精華,解決圖論問題的關(guān)鍵,建立模型,熟練掌握經(jīng)典模型,勇于探索，大膽創(chuàng)新,挖掘利用模型性質(zhì),獨(dú)具慧眼,一擊中的,謝謝,樣例的模擬,下面在樣例上模擬運(yùn)行算法二，說明算法二是如何執(zhí)行的：,1,2,3,4,5,6,從結(jié)點(diǎn)1開始遍歷,一直深搜到結(jié)點(diǎn)6,可知(1,2), (2,4)和(4,6)為最靠左的邊，所以 f 值為1,f(1,2)=1,f(2,4)=1,f(4,6)=1,樣例的模擬,1,2,3,4,5,6,回溯到2，擴(kuò)展結(jié)點(diǎn)3,擴(kuò)展結(jié)點(diǎn)4，發(fā)現(xiàn)4已經(jīng)被擴(kuò)展。根據(jù)前驅(qū)指針找到域A。,進(jìn)行遞推： f (2, 3) = f (2, 4) + 1 = 2 f (3, 4) = f (2, 4) + 1 = 2,將4的前驅(qū)指針指向3,f(1,2)=1,f(2,4)=1,f(4,6)=1,f(2,3)=2,f(3,4)=2,樣例的模擬,回溯到3，擴(kuò)展結(jié)點(diǎn)5,擴(kuò)展結(jié)點(diǎn)4，發(fā)現(xiàn)4已經(jīng)被擴(kuò)展。根據(jù)前驅(qū)指針找到域A。,進(jìn)行遞推： f (3, 5) = f (3, 4) + 1 = 3 f (5, 4) = f (3, 4) + 1 = 3,將4的前驅(qū)指針指向5,1,2,3,4,5,6,f(1,2)=1,f(2,4)=1,f(4,6)=1,f(2,3)=2,f(3,4)=2,f(3,5)=3,f(5,4)=3,樣例的模擬,擴(kuò)展結(jié)點(diǎn)6，發(fā)現(xiàn)6已經(jīng)被擴(kuò)展。根據(jù)前驅(qū)指針找到域C。,進(jìn)行遞推： f (5, 6) = maxf (4, 5), f (4,6) + 1 = 4,將6的前驅(qū)指針指向5,1,2,3,4,5,6,f(1,2)=1,f(2,4)=1,f(4,6)=