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

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

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

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

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

5、窮大，也就是說(shuō)沒(méi)有流量上限。是無(wú)窮大，也就是說(shuō)沒(méi)有流量上限。jistui,j = 因此可以利用這個(gè)性質(zhì)構(gòu)造可行流因此可以利用這個(gè)性質(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，這個(gè)可行流能夠，這個(gè)可行流能夠“過(guò)剩過(guò)剩。因此要將多余的流從匯點(diǎn)因此要將多余的流從匯點(diǎn)“退回退回到源點(diǎn)。到源點(diǎn)。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回退回退“過(guò)剩流量可以用如下方法：過(guò)剩流量可以用如下方法：求最小流求最小流在新圖中，從在新圖中，從 t 到到 s 求出一個(gè)最大求出一

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

8、擇模型(2)另辟蹊徑的偏序集另辟蹊徑的偏序集 能否存在效率更高的算法？能否存在效率更高的算法？下面引見(jiàn)的偏序集模型將更好的下面引見(jiàn)的偏序集模型將更好的處理此問(wèn)題。處理此問(wèn)題。 算法一可以很迅速的處理原題數(shù)據(jù)。算法一可以很迅速的處理原題數(shù)據(jù)。 但當(dāng)?shù)?dāng)n的范圍擴(kuò)展時(shí)，算法一便無(wú)能的范圍擴(kuò)展時(shí)，算法一便無(wú)能為力了。為力了。偏序集的定義偏序集的定義偏序集是一個(gè)集合偏序集是一個(gè)集合P和一個(gè)偏序關(guān)和一個(gè)偏序關(guān)系系 ，滿足以下性質(zhì)：，滿足以下性質(zhì)：自反性：自反性： 一切一切xP，都有，都有x x。反對(duì)稱性：反對(duì)稱性：一切一切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)概念 鏈：鏈?zhǔn)擎湥烘準(zhǔn)荘的一個(gè)子集的一個(gè)子集C，在偏序，在偏序關(guān)系關(guān)系下，它的每一對(duì)元素都是可下，它的每一對(duì)元素都是可比的。比的。 反鏈：反鏈?zhǔn)欠存湥悍存準(zhǔn)荘的一個(gè)子集的一個(gè)子集A，在偏，在偏序關(guān)系序關(guān)系下，它的每一對(duì)元素都是下，它的每一對(duì)元素都是不可比的。不可比的。 對(duì)于屬于對(duì)于屬于P的兩個(gè)元素的兩個(gè)元素x、y，假設(shè)有，假設(shè)有x y 或或 y x，那么，那么x和和y被稱作是可比的被稱作是可比的，否那么被稱為不可比的。，否那么被稱為不可比的。問(wèn)題的偏序集模型問(wèn)題的偏序集模型 E中的偏序關(guān)系：中的偏序關(guān)系

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

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

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

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

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

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

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

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

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

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

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