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

算法合集之平面圖在信息學(xué)中的應(yīng)用第一頁(yè)，共二十三頁(yè)，2022年，8月28日引言平面圖是圖論中一類(lèi)重要的圖，在實(shí)際生產(chǎn)中應(yīng)用非常廣泛。比如集成電路的設(shè)計(jì)就用到平面圖理論。在信息學(xué)中，雖然有關(guān)平面圖的題目并不多見(jiàn)，但對(duì)于某些題目，如果通過(guò)建模轉(zhuǎn)化，應(yīng)用平面圖的性質(zhì)，將大大提高算法的效率。因此，掌握一些平面圖理論會(huì)對(duì)我們有很大的幫助。第二頁(yè)，共二十三頁(yè)，2022年，8月28日相關(guān)定義、定理及推論平面圖一個(gè)無(wú)向圖G=<V，E>，如果能把它畫(huà)在平面上，且除V中的節(jié)點(diǎn)外，任意兩條邊均不相交，則稱(chēng)該圖G為平面圖。例如：圖(a)經(jīng)變動(dòng)后成為(b)，故圖(a)為平面圖。而圖(c)無(wú)論如何變動(dòng)，總出現(xiàn)邊相交，圖(c)為非平面圖。(a)(b)(c)第三頁(yè)，共二十三頁(yè)，2022年，8月28日相關(guān)定義、定理及推論面設(shè)G為一平面圖，若由G的一條或多條邊所界定的區(qū)域內(nèi)不含圖G的節(jié)點(diǎn)和邊，這樣的區(qū)域稱(chēng)為G的一個(gè)面，記為f。包圍這個(gè)區(qū)域的各條邊所構(gòu)成的圈，稱(chēng)為該面f的邊界，其圈的長(zhǎng)度，稱(chēng)為該面f的度，記為d(f)。為強(qiáng)調(diào)平面圖G中含有面這個(gè)元素，把平面圖表示為G=<V，E，F(xiàn)>，其中F是G中所有面的集合。第四頁(yè)，共二十三頁(yè)，2022年，8月28日相關(guān)定義、定理及推論定理1：若G=<V，E，F(xiàn)>是連通平面圖，則∑f∈Fd(f)=2|E|.定理2：若G=<V，E，F(xiàn)>是連通平面圖，則|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è)基本圈C，于是G必有一個(gè)有限面f，而f的邊界是由基本圈C及可能連同計(jì)算兩次的一些邊組成.如果從G中刪去基本圈C上的一條邊后得到的平面圖G1=<V1，E1，F(xiàn)1>，則|V1|=|V|，|E1|=|E|-1，|F1|=|F|-1，故|V1|-|E1|+|F1|=|V|-|E|+|F|，仿此做下去，最終得到G的一棵生成樹(shù)T0=<V0，E0，F(xiàn)0>，于是|V|-|E|+|F|=|V0|-|E0|+|F0|=2.第五頁(yè)，共二十三頁(yè)，2022年，8月28日相關(guān)定義、定理及推論推論1：給定連通簡(jiǎn)單平面圖G=<V，E，F(xiàn)>，若|V|≥3，則|E|≤3|V|-6且|F|≤2|V|-4.推論2：設(shè)G=<V，E，F(xiàn)>是連通簡(jiǎn)單平面圖，若|V|≥3，則存在v∈V，使得d(v)≤5.鄰接表、散列表結(jié)構(gòu)O(|V|)VS鄰接矩陣結(jié)構(gòu)O(|V|2)推論1：|E|=O(|V|)第六頁(yè)，共二十三頁(yè)，2022年，8月28日應(yīng)用-例1:水平可見(jiàn)線段(CEPC2001)平面上有N(N<=8000)條互不相連的豎直線段。如果兩條線段可以被一條不經(jīng)過(guò)第三條豎直線段的水平線段連接，則這兩條豎直線段被稱(chēng)為“水平可見(jiàn)”的。三條兩兩“水平可見(jiàn)”的線段構(gòu)成一個(gè)“三元組”。求給定輸入中“三元組”的數(shù)目。（坐標(biāo)值為0到8000的整數(shù)）第七頁(yè)，共二十三頁(yè)，2022年，8月28日應(yīng)用-例1:水平可見(jiàn)線段(CEPC2001)分析把線段看成點(diǎn)若兩條線段水平可見(jiàn)，則在對(duì)應(yīng)兩點(diǎn)之間連一條邊，建立無(wú)向圖G統(tǒng)計(jì)G中的三角形的數(shù)目第八頁(yè)，共二十三頁(yè)，2022年，8月28日應(yīng)用-例1:水平可見(jiàn)線段(CEPC2001)算法一設(shè)數(shù)組C[I]（I=0..2Ymax），C[2y]表示覆蓋y點(diǎn)的最后一條線段，C[2y+1]表示覆蓋區(qū)間(y,y+1)的最后一條線段把線段按從左到右的順序排序依次檢查每一條線段L(L=[y'，y''])檢查L(zhǎng)覆蓋的所有整點(diǎn)和單位區(qū)間（C[u]，u=2y'..2y''）若C[u]≠0，則G.AddEdge(C[u]，L)C[u]←LO(NlogN)O(N)O(Ymax)總計(jì)：O(NYmax)時(shí)間性能分析如何建立圖G？第九頁(yè)，共二十三頁(yè)，2022年，8月28日應(yīng)用-例1:水平可見(jiàn)線段(CEPC2001)算法二定義線段樹(shù)T：設(shè)節(jié)點(diǎn)N描述區(qū)間[a,b]的覆蓋情況 0 (無(wú)線段覆蓋[a,b])則N.Cover= L (線段L完全覆蓋[a,b]) -1 (其他情形)線段樹(shù)的存儲(chǔ)：

使用完全二叉樹(shù)的數(shù)組結(jié)構(gòu)，可以免去復(fù)雜的指針運(yùn)算和不必要的空間浪費(fèi)。如何建立圖G？時(shí)間性能分析排序：O(NlogN)檢索：O(NlogYmax)插入：O(NlogYmax)總計(jì)：O(NlogYmax)空間性能分析線段：O(N)線段樹(shù)：O(Ymax)邊表：O(N)第十頁(yè)，共二十三頁(yè)，2022年，8月28日應(yīng)用-例1:水平可見(jiàn)線段(CEPC2001)算法一

枚舉所有的三元組，判斷三個(gè)頂點(diǎn)是否兩兩相鄰。由于總共有Cn3個(gè)三元組，因此時(shí)間復(fù)雜度為O(N3)算法二

枚舉一條邊，再枚舉第三個(gè)頂點(diǎn)，判斷是否與邊上的兩個(gè)端點(diǎn)相鄰。根據(jù)水平可見(jiàn)的定義可知G為平面圖，G中的邊數(shù)為O(N)，故算法二的復(fù)雜度為O(N2)算法一與算法二的比較

算法一只是單純的枚舉，沒(méi)有注意到問(wèn)題的實(shí)際情況，而實(shí)際上三角形的數(shù)目是很少的，算法一作了許多無(wú)用的枚舉，因此效率很低。

算法二從邊出發(fā)，枚舉第三個(gè)頂點(diǎn)，這正好符合了問(wèn)題的實(shí)際情況，避免了許多不必要的枚舉，所以算法二比算法一更加高效。統(tǒng)計(jì)圖G中三角形的數(shù)目第十一頁(yè)，共二十三頁(yè)，2022年，8月28日應(yīng)用-例1:水平可見(jiàn)線段(CEPC2001)算法三—換個(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)算法二與算法三的比較

算法二是以邊作為出發(fā)點(diǎn)的，從整體上看，平面圖中三角形的個(gè)數(shù)只是O(N)級(jí)的，而算法二的復(fù)雜度卻是O(N2)，這種浪費(fèi)是判斷條件過(guò)于復(fù)雜造成的。算法三從點(diǎn)出發(fā)，則只需要判斷某兩點(diǎn)是否相鄰即可。有沒(méi)有更好的辦法？第十二頁(yè)，共二十三頁(yè)，2022年，8月28日應(yīng)用-例2:洞穴(CEOI97)在同一水平面上有N(N<=500)個(gè)洞穴，洞穴之間有通道相連，且每個(gè)洞穴恰好連著三個(gè)通道。通道與通道不相交，每個(gè)通道都有一個(gè)難度值，現(xiàn)從1號(hào)洞穴開(kāi)始遍歷所有的洞穴剛好一次并回到洞穴1，求通過(guò)通道難度值之和的最小值。(給定所有通道的信息和在外圈上的洞穴)第十三頁(yè)，共二十三頁(yè)，2022年，8月28日應(yīng)用-例2:洞穴(CEOI97)分析本題求的是最優(yōu)路徑，但最優(yōu)路徑具備什么性質(zhì)并不明顯，故考慮深度優(yōu)先搜索。N最大達(dá)到500，考慮剪枝以提高效率。基本剪枝條件：若當(dāng)前路徑的難度值的總和比當(dāng)前最優(yōu)值大則放棄當(dāng)前路徑。為了找到強(qiáng)剪枝條件，考慮問(wèn)題所具有的特性所有點(diǎn)的度數(shù)為3所給的圖是平面圖外圈上的點(diǎn)已知第十四頁(yè)，共二十三頁(yè)，2022年，8月28日應(yīng)用-例2:洞穴(CEOI97)情形一

考慮路徑1-3-5-6-12-10，由于每個(gè)洞穴必須被訪問(wèn)到，而11號(hào)洞穴只有一條可用通道9-11，訪問(wèn)11后不能再回到1，故該路徑不可能遍歷所有點(diǎn)。剪枝條件一

在所有未訪問(wèn)的洞穴中，與其相鄰的已訪問(wèn)過(guò)的洞穴（第1個(gè)與當(dāng)前訪問(wèn)的最后一個(gè)除外）的個(gè)數(shù)小于等于1。410912117856213第十五頁(yè)，共二十三頁(yè)，2022年，8月28日應(yīng)用-例2:洞穴(CEOI97)情形二

路徑1-3-7-9-10-8-4把圖分成兩部分，而且兩部分中都有未訪問(wèn)過(guò)的點(diǎn)。由于圖是平面圖，其中必有一部分點(diǎn)不能被訪問(wèn)到。剪枝條件二

設(shè)外圈上的點(diǎn)按連接順序?yàn)?,a2,…,ak，則訪問(wèn)的順序只能為：

1,…,a2,…,a3,…,…,…,ak,…,1.109121178564213第十六頁(yè)，共二十三頁(yè)，2022年，8月28日應(yīng)用-例3:地圖著色(ACMShanghai2000)分析：把每個(gè)區(qū)域看成點(diǎn)，相鄰區(qū)域之間連一條邊，則問(wèn)題轉(zhuǎn)化為對(duì)每個(gè)點(diǎn)著色并使得相鄰點(diǎn)顏色不同。根據(jù)地圖的平面性可知：轉(zhuǎn)化后的圖是平面圖。給定一地圖，要求用不超過(guò)5種顏色涂每一個(gè)區(qū)域，使得相鄰區(qū)域的顏色不同。（區(qū)域數(shù)<=500）對(duì)于任意平面圖G，是否都能用不超過(guò)5種顏色著色？第十七頁(yè)，共二十三頁(yè)，2022年，8月28日應(yīng)用-例3:地圖著色(ACMShanghai2000)定理：對(duì)于任意平面圖G，都能用不超過(guò)5種顏色著色.證明：只需考慮G是連通簡(jiǎn)單平面圖的情形.若|V|≤5，則命題顯然成立.假設(shè)對(duì)所有的平面圖G=<V，E>，當(dāng)|V|≤k時(shí)命題成立.現(xiàn)在考慮圖G1=<V1，E>，|V1|=k+1的情形.由推論2可知：存在v0∈V1，使得d(v0)≤5.在圖G1中刪去v0，得圖G1-v0.由歸納，圖G1-v0可用5種顏色著色.若鄰接結(jié)點(diǎn)使用顏色數(shù)不超過(guò)4，則可對(duì)v0著色，得到一個(gè)最多是五色的圖G1.第十八頁(yè)，共二十三頁(yè)，2022年，8月28日應(yīng)用-例3:地圖著色(ACMShanghai2000)若d(v0)=5且各鄰接點(diǎn)分別著不同的顏色，則設(shè)與之相鄰的點(diǎn)的按順時(shí)針排列為v1,v2,v3,v4,v5.它們分別著不同的顏色c1,c2,c3,c4,c5.考慮點(diǎn)集Vc1,c3={v|v∈V(G1-v0)∧a(v)=c1或c3}所誘導(dǎo)的G1-v0的子圖<Vc1,c3>.若v1,v3屬于<Vc1,c3>的不同的分圖，則在v1所在的分圖中，調(diào)換顏色c1與c3后，v1,v2,v3,v4,v5五個(gè)點(diǎn)是四著色的，再令v0著c1色，得到G1的一種五著色.v1v5v4v3v2v0v1v5v4v3v2v0第十九頁(yè)，共二十三頁(yè)，2022年，8月28日應(yīng)用-例3:地圖著色(ACMShanghai2000)若v1,v3屬于<Vc1,c3>的同一的分圖，則點(diǎn)集Vc1,c3∪{v0}所誘導(dǎo)的G1的子圖中含有一個(gè)圈C，而v2,v4不能同時(shí)在圈的內(nèi)部或外部，即v2,v4不是鄰接點(diǎn)，于是考慮Vc2,c4={v|v∈V(G1-v0)∧a(v)=c2或c4}所誘導(dǎo)的子圖<Vc2,c4>，v2,v4必屬于<Vc2,c4>的不同的分圖.做與上面類(lèi)似的調(diào)整，又可得到G1的一種五著色.故對(duì)任何連通簡(jiǎn)單平面圖G，G是五著色的.v1v5v4v3v2v0v1v5v4v3v2v0v1v5v4v3v2v0第二十頁(yè)，共二十三頁(yè)，2022年，8月28日應(yīng)用-例3:地圖著色(ACMShanghai2000)算法：procedurePaint(G:Graph);找出度最小的點(diǎn)v0Paint(G-v0)考慮圖G，若無(wú)法對(duì)v0著色，則對(duì)v0的相鄰點(diǎn)，枚舉所有點(diǎn)對(duì),直到找到屬于不同分圖的點(diǎn)對(duì)，對(duì)其進(jìn)行調(diào)整.任選剩下的一種顏色，對(duì)v0著色時(shí)間復(fù)