國家集訓(xùn)隊(duì)2005論文集 任愷

《國家集訓(xùn)隊(duì)2005論文集 任愷》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、圖論的基本思想及方法湖南省長郡中學(xué)任愷由一道題目淺談——概述信息學(xué)中的圖論問題層出不窮，變化多端，惟有掌握其基本思想和方法，才能以不變應(yīng)萬變！下面通過實(shí)例主要從兩方面論述圖論的基本思想：一、合理選擇圖論模型二、充分挖掘和利用圖的性質(zhì)雪山上有一個(gè)滑雪場?；﹫鲇善脚_和滑道組成。每個(gè)平臺有不同的高度，有一個(gè)最高點(diǎn)和一個(gè)最低點(diǎn)?；肋B接著兩個(gè)不同的平臺，方向是從較高點(diǎn)到較低點(diǎn)。一些工人要檢查滑道。每個(gè)工人從最高點(diǎn)滑到最低點(diǎn)，滑行路徑上的滑道便都被檢查了。每個(gè)工人只能滑行一次。不同工人的滑行路徑可以有相同的滑道。例題：滑雪者(POI2002)問題：最少要多少個(gè)

2、工人才能檢查完所有的滑道呢？Nar.in622323424516246Nar.out4頂點(diǎn)個(gè)數(shù)n(1≤n≤5000)從左到右描述第i個(gè)頂點(diǎn)發(fā)出邊的另一個(gè)端點(diǎn)例題：滑雪者(POI2002)123456選擇模型(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)：很容易想到建立一個(gè)網(wǎng)絡(luò)流模型：最高點(diǎn)最低點(diǎn)st1,∞1,∞1,∞1,∞1,∞1,∞1,∞1,∞1,∞確定所求目標(biāo)建立模型后，可以確定要求的目標(biāo)：求圖G中一個(gè)最小可行流，滿足：

3、st213122111a)每條邊的流量大于等于下界b)從源點(diǎn)流出的總流量最小求最小流的方法如何求圖G的最小流呢求最小流可以分成兩步：1）求出圖G上的可行流f2）將可行流f轉(zhuǎn)化成最小流對于有上下界的網(wǎng)絡(luò)，通常用構(gòu)造附加網(wǎng)絡(luò)的方法求可行流。但是觀察圖G可以發(fā)現(xiàn)，邊的上界都是無窮大，也就是說沒有流量上限。jistui,j=∞因此可以利用這個(gè)性質(zhì)構(gòu)造可行流求可行流的方法jist求可行流的方法枚舉每條流量為0的邊，設(shè)為(i,j)任意找到一條從s到i的路徑和一條從j到t的路徑那么s–i–j–t便是一條可行的流，將這條路徑上的邊流量加1，便滿足了邊(i,j)的容量下

4、界fi,j=0fi,j=1+1+1f可行jist求最小流設(shè)用上法求出的可行流的總流量為F，這個(gè)可行流可能“過?！薄Ｒ虼艘獙⒍嘤嗟牧鲝膮R點(diǎn)“退回”到源點(diǎn)。f最小求最小流sjit在新圖中，原圖G的邊(i,j)拆成兩條邊：邊(i,j),u'i,j=fi,j–li,j，l'i,j=0邊(j,i),u'j,i=ui,j–fi,j，l'j,i=0fi,jfi,j–li,jui,j–fi,j回退“過剩”流量可以用如下方法：求最小流在新圖中，從t到s求出一個(gè)最大流，令這個(gè)最大流的總流量為F'。sjitfi,j–li,jui,j–fi,j可得圖G的最小流的流量為F–F'

5、。算法一的復(fù)雜度易知構(gòu)造可行流的時(shí)間復(fù)雜度為O(nm)修改可行流所用的最大流算法時(shí)間復(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ò)大時(shí)，算法一便無能為力了。偏序集的定義偏序集是一個(gè)集合P和一個(gè)偏序關(guān)系≤，滿足下列性質(zhì)：自反性：所有x∈P，都有x≤x。反對稱性：所有x,y∈P，若x≤y且y≤x，則x=y。

6、傳遞性：所有x,y,z∈P，若x≤y且y≤z，則x≤z。鏈：鏈?zhǔn)荘的一個(gè)子集C，在偏序關(guān)系≤下，它的每一對元素都是可比的。偏序集的相關(guān)概念反鏈：反鏈?zhǔn)荘的一個(gè)子集A，在偏序關(guān)系≤下，它的每一對元素都是不可比的。對于屬于P的兩個(gè)元素x、y，若有x≤y或y≤x，則x和y被稱作是可比的，否則被稱為不可比的。E中的偏序關(guān)系：對于邊u,v∈E,u≤v當(dāng)且僅當(dāng)u=v或圖G中存在v到u的一條路徑。問題的偏序集模型圖G可以定義成一個(gè)偏序集E：E中的元素是圖G中的邊；uvu≤v問題的偏序集模型因此，原問題可以重新用偏序集語言表述為：將偏序集（E,≤）劃分成最少的鏈，使得

7、這些鏈的并集包含所有E中的元素?？梢园l(fā)現(xiàn)，圖G中從最高點(diǎn)到最低點(diǎn)的路徑對應(yīng)了E的一個(gè)鏈。目標(biāo)的轉(zhuǎn)化直接計(jì)算鏈的最少個(gè)數(shù)——與網(wǎng)絡(luò)流沒有差別唯有——繼續(xù)轉(zhuǎn)化目標(biāo)目標(biāo)的轉(zhuǎn)化鏈和反鏈的計(jì)數(shù)滿足下列關(guān)系：Dilworth定理令(E,≤)是一個(gè)有限偏序集，并令LA是E中最大反鏈的大小，SC是將E劃分成最少的鏈的個(gè)數(shù)。在E中，有LA=SC。求E中最長反鏈的大小目標(biāo)最終轉(zhuǎn)化為：求最長的反鏈由偏序集E的定義可以知道：偏序集E中的反鏈對應(yīng)著圖G中的一些邊，其中任意兩條邊之間都不能互達(dá)。右圖橙色線段便是樣例的最長反鏈如果用一條線將最長反鏈所對應(yīng)的邊從左到右連起來那么這條線

8、不會與平面圖中的其它邊相交！這些線段滿足如下性質(zhì)：求最長的反鏈換句話說，將最長反鏈所對應(yīng)的邊從