算法合集之《平面圖在信息學(xué)中的應(yīng)用》.ppt_第1頁
算法合集之《平面圖在信息學(xué)中的應(yīng)用》.ppt_第2頁
算法合集之《平面圖在信息學(xué)中的應(yīng)用》.ppt_第3頁
算法合集之《平面圖在信息學(xué)中的應(yīng)用》.ppt_第4頁
算法合集之《平面圖在信息學(xué)中的應(yīng)用》.ppt_第5頁
已閱讀5頁,還剩18頁未讀 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

1、平面圖在信息學(xué)中的應(yīng)用,海南省海南中學(xué) 劉才良,引言,平面圖是圖論中一類重要的圖,在實際生產(chǎn)中應(yīng)用非常廣泛。比如集成電路的設(shè)計就用到平面圖理論。在信息學(xué)中,雖然有關(guān)平面圖的題目并不多見,但對于某些題目,如果通過建模轉(zhuǎn)化,應(yīng)用平面圖的性質(zhì),將大大提高算法的效率。因此,掌握一些平面圖理論會對我們有很大的幫助。,相關(guān)定義、定理及推論,平面圖 一個無向圖G=,如果能把它畫在平面上,且除V中的節(jié)點外,任意兩條邊均不相交,則稱該圖G為平面圖。,例如:圖(a)經(jīng)變動后成為(b),故圖(a)為平面圖。而圖(c)無論如何變動,總出現(xiàn)邊相交,圖(c)為非平面圖。,相關(guān)定義、定理及推論,面 設(shè)G為一平面圖,若由G的

2、一條或多條邊所界定的區(qū)域內(nèi)不含圖G的節(jié)點和邊,這樣的區(qū)域稱為G的一個面,記為f。包圍這個區(qū)域的各條邊所構(gòu)成的圈,稱為該面f的邊界,其圈的長度,稱為該面f的度,記為d(f)。為強調(diào)平面圖G中含有面這個元素,把平面圖表示為G=,其中F是G中所有面的集合。,相關(guān)定義、定理及推論,定理1:若G=是連通平面圖,則fFd(f)=2|E|. 定理2:若G=是連通平面圖,則|V|-|E|+|F|=2.,證明: 首先假定G是樹,則|E|=|V|-1,G只有一個無限面,因此|V|-|E|+|F|=|V|-(|V|-1)+1=2.現(xiàn)在假設(shè)G不是樹,由于G是連通的,故G中至少存在一個基本圈C,于是G必有一個有限面f,

3、而f的邊界是由基本圈C及可能連同計算兩次的一些邊組成.如果從G中刪去基本圈C上的一條邊后得到的平面圖G1=,則|V1|=|V|,|E1|=|E|-1,|F1|=|F|-1,故|V1|-|E1|+|F1|=|V|-|E|+|F|,仿此做下去,最終得到G的一棵生成樹T0=,于是|V|-|E|+|F|=|V0|-|E0|+|F0|=2.,相關(guān)定義、定理及推論,推論1:給定連通簡單平面圖G=,若|V|3,則|E|3|V|-6且|F|2|V|-4. 推論2:設(shè)G=是連通簡單平面圖,若|V|3,則存在vV,使得d(v)5.,鄰接表、散列表結(jié)構(gòu)O(|V|) VS 鄰接矩陣結(jié)構(gòu)O(|V|2),推論1:|E|=

4、O(|V|),應(yīng)用-例1:水平可見線段(CEPC2001),平面上有N(N=8000)條互不相連的豎直線段。如果兩條線段可以被一條不經(jīng)過第三條豎直線段的水平線段連接,則這兩條豎直線段被稱為“水平可見”的。三條兩兩“水平可見”的線段構(gòu)成一個“三元組”。求給定輸入中“三元組”的數(shù)目。(坐標值為0到8000的整數(shù)),應(yīng)用-例1:水平可見線段(CEPC2001),分析 把線段看成點 若兩條線段水平可見,則在對應(yīng)兩點之間連一條邊,建立無向圖G 統(tǒng)計G中的三角形的數(shù)目,應(yīng)用-例1:水平可見線段(CEPC2001),算法一 設(shè)數(shù)組CI(I=0.2Ymax),C2y表示覆蓋y點的最后一條線段,C2y+1表示覆

5、蓋區(qū)間(y,y+1)的最后一條線段 把線段按從左到右的順序排序 依次檢查每一條線段L(L=y,y) 檢查L覆蓋的所有整點和單位區(qū)間(Cu,u=2y.2y) 若Cu0,則G.AddEdge(Cu,L) CuL,O(NlogN) O(N) O(Ymax) 總計:O(NYmax),時間性能分析,如何建立圖G?,應(yīng)用-例1:水平可見線段(CEPC2001),算法二 定義線段樹T: 設(shè)節(jié)點N描述區(qū)間a,b的覆蓋情況 0(無線段覆蓋a,b) 則N.Cover=L(線段L完全覆蓋a,b) -1(其他情形) 線段樹的存儲:使用完全二叉樹的數(shù)組結(jié)構(gòu),可以免去復(fù)雜的指針運算和不必要的空間浪費。,如何建立圖G?,時

6、間性能分析 排序:O(NlogN) 檢索:O(NlogYmax) 插入:O(NlogYmax) 總計:O(NlogYmax) 空間性能分析 線段:O(N) 線段樹:O(Ymax) 邊表:O(N),應(yīng)用-例1:水平可見線段(CEPC2001),算法一枚舉所有的三元組,判斷三個頂點是否兩兩相鄰。由于總共有Cn3個三元組,因此時間復(fù)雜度為O(N3) 算法二枚舉一條邊,再枚舉第三個頂點,判斷是否與邊上的兩個端點相鄰。根據(jù)水平可見的定義可知G為平面圖,G中的邊數(shù)為O(N),故算法二的復(fù)雜度為O(N2) 算法一與算法二的比較算法一只是單純的枚舉,沒有注意到問題的實際情況,而實際上三角形的數(shù)目是很少的,算法

7、一作了許多無用的枚舉,因此效率很低。算法二從邊出發(fā),枚舉第三個頂點,這正好符合了問題的實際情況,避免了許多不必要的枚舉,所以算法二比算法一更加高效。,統(tǒng)計圖G中三角形的數(shù)目,應(yīng)用-例1:水平可見線段(CEPC2001),算法三換個角度,從點出發(fā)每次選取度最小的點v,由推論2知d(v)5,只需花常數(shù)時間就可以計算含點v的三角形的數(shù)目.應(yīng)用二叉堆可以提高尋找和刪除點v的效率,總的時間復(fù)雜度僅為O(NlogN) 算法二與算法三的比較算法二是以邊作為出發(fā)點的,從整體上看,平面圖中三角形的個數(shù)只是O(N)級的,而算法二的復(fù)雜度卻是O(N2),這種浪費是判斷條件過于復(fù)雜造成的。算法三從點出發(fā),則只需要判斷

8、某兩點是否相鄰即可。,有沒有更好的辦法?,應(yīng)用-例2:洞穴(CEOI97),在同一水平面上有N(N=500)個洞穴,洞穴之間有通道相連,且每個洞穴恰好連著三個通道。通道與通道不相交,每個通道都有一個難度值,現(xiàn)從1號洞穴開始遍歷所有的洞穴剛好一次并回到洞穴1,求通過通道難度值之和的最小值。(給定所有通道的信息和在外圈上的洞穴),應(yīng)用-例2:洞穴(CEOI97),分析 本題求的是最優(yōu)路徑,但最優(yōu)路徑具備什么性質(zhì)并不明顯,故考慮深度優(yōu)先搜索。 N最大達到500,考慮剪枝以提高效率。 基本剪枝條件:若當(dāng)前路徑的難度值的總和比當(dāng)前最優(yōu)值大則放棄當(dāng)前路徑。 為了找到強剪枝條件,考慮問題所具有的特性 所有點

9、的度數(shù)為3 所給的圖是平面圖 外圈上的點已知,應(yīng)用-例2:洞穴(CEOI97),情形一考慮路徑1-3-5-6-12-10,由于每個洞穴必須被訪問到,而11號洞穴只有一條可用通道9-11,訪問11后不能再回到1,故該路徑不可能遍歷所有點。 剪枝條件一在所有未訪問的洞穴中,與其相鄰的已訪問過的洞穴(第1個與當(dāng)前訪問的最后一個除外)的個數(shù)小于等于1。,應(yīng)用-例2:洞穴(CEOI97),情形二路徑1-3-7-9-10-8-4把圖分成兩部分,而且兩部分中都有未訪問過的點。由于圖是平面圖,其中必有一部分點不能被訪問到。 剪枝條件二設(shè)外圈上的點按連接順序為1,a2,ak,則訪問的順序只能為:1,a2,a3,

10、ak,1.,應(yīng)用-例3:地圖著色(ACM Shanghai 2000),分析: 把每個區(qū)域看成點,相鄰區(qū)域之間連一條邊,則問題轉(zhuǎn)化為對每個點著色并使得相鄰點顏色不同。 根據(jù)地圖的平面性可知:轉(zhuǎn)化后的圖是平面圖。,給定一地圖,要求用不超過5種顏色涂每一個區(qū)域,使得相鄰區(qū)域的顏色不同。(區(qū)域數(shù)=500),對于任意平面圖G,是否都能用不超過5種顏色著色?,應(yīng)用-例3:地圖著色(ACM Shanghai 2000),定理:對于任意平面圖G,都能用不超過5種顏色著色. 證明:只需考慮G是連通簡單平面圖的情形. 若|V|5,則命題顯然成立. 假設(shè)對所有的平面圖G=,當(dāng)|V|k時命題成立.現(xiàn)在考慮圖G1=,

11、|V1|=k+1的情形.由推論2可知:存在v0V1,使得d(v0)5.在圖G1中刪去v0,得圖G1-v0.由歸納,圖G1-v0可用5種顏色著色. 若鄰接結(jié)點使用顏色數(shù)不超過4,則可對v0著色,得到一個最多是五色的圖G1.,應(yīng)用-例3:地圖著色(ACM Shanghai 2000),若d(v0)=5且各鄰接點分別著不同的顏色,則設(shè)與之相鄰的點的按順時針排列為v1,v2,v3,v4,v5.它們分別著不同的顏色c1,c2,c3,c4,c5. 考慮點集Vc1,c3=v|vV(G1-v0)a(v)=c1或c3所誘導(dǎo)的G1-v0的子圖.若v1,v3屬于的不同的分圖,則在v1所在的分圖中,調(diào)換顏色c1與c3

12、后,v1,v2,v3,v4,v5五個點是四著色的,再令v0著c1色,得到G1的一種五著色.,應(yīng)用-例3:地圖著色(ACM Shanghai 2000),若v1,v3屬于的同一的分圖,則點集Vc1,c3v0所誘導(dǎo)的G1的子圖中含有一個圈C,而v2,v4不能同時在圈的內(nèi)部或外部,即v2,v4不是鄰接點,于是考慮Vc2,c4=v|vV(G1-v0)a(v)=c2或c4所誘導(dǎo)的子圖,v2,v4必屬于的不同的分圖.做與上面類似的調(diào)整,又可得到G1的一種五著色. 故對任何連通簡單平面圖G,G是五著色的.,應(yīng)用-例3:地圖著色(ACM Shanghai 2000),算法: procedure Paint(G:Graph); 找出度最小的點v0 Paint(G-v0) 考慮圖G,若無法對v0著色,則對v0的相鄰點,枚舉所有點對,直到找到屬于不同分圖的點對,對其進行調(diào)整. 任選剩下的一種顏色,對v0著色 時間復(fù)雜

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論