算法合集之平面圖在信息學(xué)中的應(yīng)用

1、海南省海南中學(xué) 劉才良l平面圖是圖論中一類(lèi)重要的圖，在實(shí)際平面圖是圖論中一類(lèi)重要的圖，在實(shí)際生產(chǎn)中應(yīng)用非常廣泛。比如集成電路的生產(chǎn)中應(yīng)用非常廣泛。比如集成電路的設(shè)計(jì)就用到平面圖理論。在信息學(xué)中，設(shè)計(jì)就用到平面圖理論。在信息學(xué)中，雖然有關(guān)平面圖的題目并不多見(jiàn)，但對(duì)雖然有關(guān)平面圖的題目并不多見(jiàn)，但對(duì)于某些題目，如果通過(guò)建模轉(zhuǎn)化，應(yīng)用于某些題目，如果通過(guò)建模轉(zhuǎn)化，應(yīng)用平面圖的性質(zhì)，將大大提高算法的效率。平面圖的性質(zhì)，將大大提高算法的效率。因此，掌握一些平面圖理論會(huì)對(duì)我們有因此，掌握一些平面圖理論會(huì)對(duì)我們有很大的幫助。很大的幫助。l平面圖平面圖 一個(gè)無(wú)向圖一個(gè)無(wú)向圖g=，如果能把它畫(huà)在平面上，如果能把

2、它畫(huà)在平面上，且除且除v中的節(jié)點(diǎn)外，任意兩條邊均不相交，則稱(chēng)該中的節(jié)點(diǎn)外，任意兩條邊均不相交，則稱(chēng)該圖圖g為平面圖。為平面圖。例如：圖例如：圖(a)經(jīng)變動(dòng)后成為經(jīng)變動(dòng)后成為(b)，故圖，故圖(a)為平面圖。而圖為平面圖。而圖(c)無(wú)論無(wú)論如何變動(dòng)，總出現(xiàn)邊相交，圖如何變動(dòng)，總出現(xiàn)邊相交，圖(c)為非平面圖。為非平面圖。(a)(b)(c)l面面 設(shè)設(shè)g為一平面圖，若由為一平面圖，若由g的一條或多條邊所界定的的一條或多條邊所界定的區(qū)域內(nèi)不含圖區(qū)域內(nèi)不含圖g的節(jié)點(diǎn)和邊，這樣的區(qū)域稱(chēng)為的節(jié)點(diǎn)和邊，這樣的區(qū)域稱(chēng)為g的的一個(gè)面，記為一個(gè)面，記為f。包圍這個(gè)區(qū)域的各條邊所構(gòu)成的圈，。包圍這個(gè)區(qū)域的各條邊所構(gòu)

3、成的圈，稱(chēng)為該面稱(chēng)為該面f的邊界，其圈的長(zhǎng)度，稱(chēng)為該面的邊界，其圈的長(zhǎng)度，稱(chēng)為該面f的度，的度，記為記為d(f)。為強(qiáng)調(diào)平面圖。為強(qiáng)調(diào)平面圖g中含有面這個(gè)元素，把平中含有面這個(gè)元素，把平面圖表示為面圖表示為g=，其中，其中f是是g中所有面的中所有面的集合。集合。l定理定理1：若：若g=是連通平面圖，則是連通平面圖，則ffd(f)=2|e|.l定理定理2：若：若g=是連通平面圖，則是連通平面圖，則|v|-|e|+|f|=2.證明：首先假定g是樹(shù)，則|e|=|v|-1，g只有一個(gè)無(wú)限面，因此|v|-|e|+|f|=|v|-(|v|-1)+1=2.現(xiàn)在假設(shè)g不是樹(shù)，由于g是連通的，故g中至少存在一個(gè)

4、基本圈c，于是g必有一個(gè)有限面f，而f的邊界是由基本圈c及可能連同計(jì)算兩次的一些邊組成.如果從g中刪去基本圈c上的一條邊后得到的平面圖g1=，則|v1|=|v|，|e1|=|e|-1，|f1|=|f|-1，故|v1|-|e1|+|f1|=|v|-|e|+|f|，仿此做下去，最終得到g的一棵生成樹(shù)t0=，于是|v|-|e|+|f|=|v0|-|e0|+|f0|=2.l推論推論1：給定連通簡(jiǎn)單平面圖：給定連通簡(jiǎn)單平面圖g=，若，若|v|3，則則|e|3|v|-6且且|f|2|v|-4.l推論推論2：設(shè)：設(shè)g=是連通簡(jiǎn)單平面圖，若是連通簡(jiǎn)單平面圖，若|v|3，則存在則存在vv，使得，使得d(v)5.

5、鄰接表、散列表結(jié)構(gòu)鄰接表、散列表結(jié)構(gòu)o(|v|)vs鄰接矩陣結(jié)構(gòu)鄰接矩陣結(jié)構(gòu)o(|v|2)平面上有平面上有n(n=8000)條互不相連的豎直線(xiàn)條互不相連的豎直線(xiàn)段。如果兩條線(xiàn)段可以被一條不經(jīng)過(guò)第三條豎段。如果兩條線(xiàn)段可以被一條不經(jīng)過(guò)第三條豎直線(xiàn)段的水平線(xiàn)段連接，則這兩條豎直線(xiàn)段被直線(xiàn)段的水平線(xiàn)段連接，則這兩條豎直線(xiàn)段被稱(chēng)為稱(chēng)為“水平可見(jiàn)水平可見(jiàn)”的。三條兩兩的。三條兩兩“水平可見(jiàn)水平可見(jiàn)”的線(xiàn)段構(gòu)成一個(gè)的線(xiàn)段構(gòu)成一個(gè)“三元組三元組”。求給定輸入中。求給定輸入中“三元組三元組”的數(shù)目。（坐標(biāo)值為的數(shù)目。（坐標(biāo)值為0到到8000的整的整數(shù)）數(shù)）分析分析l把線(xiàn)段看成點(diǎn)l若兩條線(xiàn)段水平可見(jiàn)，則在對(duì)應(yīng)兩

6、點(diǎn)之間連一條邊，建立無(wú)向圖gl統(tǒng)計(jì)g中的三角形的數(shù)目l算法一算法一 設(shè)數(shù)組ci（i=0.2ymax），c2y表示覆蓋y點(diǎn)的最后一條線(xiàn)段，c2y+1表示覆蓋區(qū)間(y,y+1)的最后一條線(xiàn)段 把線(xiàn)段按從左到右的順序排序 依次檢查每一條線(xiàn)段l(l=y，y) 檢查l覆蓋的所有整點(diǎn)和單位區(qū)間（cu，u=2y.2y） 若cu0，則g.addedge(cu，l) culo(nlogn)o(n)o(ymax)總計(jì)總計(jì)：o(nymax)時(shí)間性能分析時(shí)間性能分析如何建立圖如何建立圖g？l算法二算法二 定義線(xiàn)段樹(shù)t： 設(shè)節(jié)點(diǎn)n描述區(qū)間a,b的覆蓋情況0(無(wú)線(xiàn)段覆蓋a,b) 則n.cover= l(線(xiàn)段l完全覆蓋a,

7、b)-1(其他情形) 線(xiàn)段樹(shù)的存儲(chǔ)：使用完全二叉樹(shù)的數(shù)組結(jié)構(gòu)，可以免去復(fù)雜的指針運(yùn)算和不必要的空間浪費(fèi)。如何建立圖如何建立圖g？時(shí)間性能分析時(shí)間性能分析排序：o(nlogn)檢索：o(nlogymax)插入：o(nlogymax)總計(jì)：o(nlogymax)空間性能分析空間性能分析線(xiàn)段：o(n)線(xiàn)段樹(shù)：o(ymax)邊表：o(n)l算法一算法一枚舉所有的三元組，判斷三個(gè)頂點(diǎn)是否兩兩相鄰。由于總共有cn3個(gè)三元組，因此時(shí)間復(fù)雜度為o(n3)l算法二算法二枚舉一條邊，再枚舉第三個(gè)頂點(diǎn)，判斷是否與邊上的兩個(gè)端點(diǎn)相鄰。根據(jù)水平可見(jiàn)的定義可知g為平面圖，g中的邊數(shù)為o(n)，故算法二的復(fù)雜度為o(n2)

8、l算法一算法一與算法二算法二的比較算法一只是單純的枚舉，沒(méi)有注意到問(wèn)題的實(shí)際情況，而實(shí)際上三角形的數(shù)目是很少的，算法一作了許多無(wú)用的枚舉，因此效率很低。算法二從邊出發(fā)，枚舉第三個(gè)頂點(diǎn)，這正好符合了問(wèn)題的實(shí)際情況，避免了許多不必要的枚舉，所以算法二比算法一更加高效。統(tǒng)計(jì)圖統(tǒng)計(jì)圖g中三角形的數(shù)目中三角形的數(shù)目l算法三算法三換個(gè)角度，從點(diǎn)出發(fā)每次選取度最小的點(diǎn)v，由推論2知d(v)5，只需花常數(shù)時(shí)間就可以計(jì)算含點(diǎn)v的三角形的數(shù)目.應(yīng)用二叉堆可以提高尋找和刪除點(diǎn)v的效率，總的時(shí)間復(fù)雜度僅為o(nlogn)l算法二與算法三的比較算法二與算法三的比較算法二是以邊作為出發(fā)點(diǎn)的，從整體上看，平面圖中三角形的個(gè)

9、數(shù)只是o(n)級(jí)的，而算法二的復(fù)雜度卻是o(n2)，這種浪費(fèi)是判斷條件過(guò)于復(fù)雜造成的。算法三從點(diǎn)出發(fā)，則只需要判斷某兩點(diǎn)是否相鄰即可。有沒(méi)有更好的辦法？有沒(méi)有更好的辦法？在同一水平面上有在同一水平面上有n(n=500)個(gè)洞穴，洞個(gè)洞穴，洞穴之間有通道相連，且每個(gè)洞穴恰好連著三個(gè)穴之間有通道相連，且每個(gè)洞穴恰好連著三個(gè)通道。通道與通道不相交，每個(gè)通道都有一個(gè)通道。通道與通道不相交，每個(gè)通道都有一個(gè)難度值，現(xiàn)從難度值，現(xiàn)從1號(hào)洞穴開(kāi)始遍歷所有的洞穴剛號(hào)洞穴開(kāi)始遍歷所有的洞穴剛好一次并回到洞穴好一次并回到洞穴1，求通過(guò)通道難度值之和，求通過(guò)通道難度值之和的最小值。的最小值。(給定所有通道的信息和在外

10、圈上給定所有通道的信息和在外圈上的洞穴的洞穴)分析分析l本題求的是最優(yōu)路徑，但最優(yōu)路徑具備什么性質(zhì)并不明顯，故考慮深度優(yōu)先搜索。ln最大達(dá)到500，考慮剪枝以提高效率。l基本剪枝條件：若當(dāng)前路徑的難度值的總和比當(dāng)前最優(yōu)值大則放棄當(dāng)前路徑。l為了找到強(qiáng)剪枝條件，考慮問(wèn)題所具有的特性 所有點(diǎn)的度數(shù)為3 所給的圖是平面圖 外圈上的點(diǎn)已知l情形一情形一考慮路徑1-3-5-6-12-10，由于每個(gè)洞穴必須被訪問(wèn)到，而11號(hào)洞穴只有一條可用通道9-11，訪問(wèn)11后不能再回到1，故該路徑不可能遍歷所有點(diǎn)。l剪枝條件一剪枝條件一在所有未訪問(wèn)的洞穴中，與其相鄰的已訪問(wèn)過(guò)的洞穴（第1個(gè)與當(dāng)前訪問(wèn)的最后一個(gè)除外）的

11、個(gè)數(shù)小于等于1。410912117856213l情形二情形二路徑1-3-7-9-10-8-4把圖分成兩部分，而且兩部分中都有未訪問(wèn)過(guò)的點(diǎn)。由于圖是平面圖，其中必有一部分點(diǎn)不能被訪問(wèn)到。l剪枝條件二剪枝條件二設(shè)外圈上的點(diǎn)按連接順序?yàn)?,a2,ak，則訪問(wèn)的順序只能為：1,a2,a3,ak,1.109121178564213分析：把每個(gè)區(qū)域看成點(diǎn)，相鄰區(qū)域之間連一條邊，則問(wèn)題轉(zhuǎn)化為對(duì)每個(gè)點(diǎn)著色并使得相鄰點(diǎn)顏色不同。根據(jù)地圖的平面性可知：轉(zhuǎn)化后的圖是平面圖。給定一地圖，要求用不超過(guò)給定一地圖，要求用不超過(guò)5種顏色涂每種顏色涂每一個(gè)區(qū)域，使得相鄰區(qū)域的顏色不同。（區(qū)域一個(gè)區(qū)域，使得相鄰區(qū)域的顏色不同。

12、（區(qū)域數(shù)數(shù)=500）對(duì)于任意平面圖對(duì)于任意平面圖g，是否都能用不超過(guò)，是否都能用不超過(guò)5種顏色著色？種顏色著色？定理：對(duì)于任意平面圖定理：對(duì)于任意平面圖g，都能用不超過(guò)，都能用不超過(guò)5種顏色著色種顏色著色.證明：只需考慮g是連通簡(jiǎn)單平面圖的情形.若|v|5，則命題顯然成立.假設(shè)對(duì)所有的平面圖g=，當(dāng)|v|k時(shí)命題成立.現(xiàn)在考慮圖g1=，|v1|=k+1的情形.由推論2可知：存在v0v1，使得d(v0)5.在圖g1中刪去v0，得圖g1-v0.由歸納，圖g1-v0可用5種顏色著色.若鄰接結(jié)點(diǎn)使用顏色數(shù)不超過(guò)4，則可對(duì)v0著色，得到一個(gè)最多是五色的圖g1.若d(v0)=5且各鄰接點(diǎn)分別著不同的顏色，

13、則設(shè)與之相鄰的點(diǎn)的按順時(shí)針排列為v1,v2,v3,v4,v5.它們分別著不同的顏色c1,c2,c3,c4,c5.考慮點(diǎn)集vc1,c3=v|vv(g1-v0)a(v)=c1或c3所誘導(dǎo)的g1-v0的子圖.若v1,v3屬于的不同的分圖，則在v1所在的分圖中，調(diào)換顏色c1與c3后，v1,v2,v3,v4,v5五個(gè)點(diǎn)是四著色的，再令v0著c1色，得到g1的一種五著色.v1v5v4v3v2v0v1v5v4v3v2v0若v1,v3屬于的同一的分圖，則點(diǎn)集vc1,c3v0所誘導(dǎo)的g1的子圖中含有一個(gè)圈c，而v2,v4不能同時(shí)在圈的內(nèi)部或外部，即v2,v4不是鄰接點(diǎn)，于是考慮vc2,c4=v|vv(g1-v0

14、)a(v)=c2或c4所誘導(dǎo)的子圖，v2,v4必屬于的不同的分圖.做與上面類(lèi)似的調(diào)整，又可得到g1的一種五著色.故對(duì)任何連通簡(jiǎn)單平面圖g，g是五著色的.v1v5v4v3v2v0v1v5v4v3v2v0v1v5v4v3v2v0算法：算法：procedure paint(g:graph);l找出度最小的點(diǎn)v0lpaint(g-v0)l考慮圖g，若無(wú)法對(duì)v0著色，則對(duì)v0的相鄰點(diǎn)，枚舉所有點(diǎn)對(duì),直到找到屬于不同分圖的點(diǎn)對(duì)，對(duì)其進(jìn)行調(diào)整.l任選剩下的一種顏色，對(duì)v0著色時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：o(n2)空間復(fù)雜度：空間復(fù)雜度：o(n)以上例子分別論述了平面圖理論在幾類(lèi)信以上例子分別論述了平面圖理論在幾類(lèi)信息學(xué)問(wèn)題中的應(yīng)用。我們研究平面圖就是為了息學(xué)問(wèn)題中的應(yīng)用。我們研究平面圖就是為了更深刻地認(rèn)識(shí)平面圖，提高算法效率，但有時(shí)更深刻地認(rèn)識(shí)平面圖，提高算法效率，但