算法合集之平面圖在信息學中的應用第1頁，課件共23頁，創作于2023年2月引言平面圖是圖論中一類重要的圖，在實際生產中應用非常廣泛。比如集成電路的設計就用到平面圖理論。在信息學中，雖然有關平面圖的題目并不多見，但對于某些題目，如果通過建模轉化，應用平面圖的性質，將大大提高算法的效率。因此，掌握一些平面圖理論會對我們有很大的幫助。第2頁，課件共23頁，創作于2023年2月相關定義、定理及推論平面圖一個無向圖G=<V，E>，如果能把它畫在平面上，且除V中的節點外，任意兩條邊均不相交，則稱該圖G為平面圖。例如：圖(a)經變動后成為(b)，故圖(a)為平面圖。而圖(c)無論如何變動，總出現邊相交，圖(c)為非平面圖。(a)(b)(c)第3頁，課件共23頁，創作于2023年2月相關定義、定理及推論面設G為一平面圖，若由G的一條或多條邊所界定的區域內不含圖G的節點和邊，這樣的區域稱為G的一個面，記為f。包圍這個區域的各條邊所構成的圈，稱為該面f的邊界，其圈的長度，稱為該面f的度，記為d(f)。為強調平面圖G中含有面這個元素，把平面圖表示為G=<V，E，F>，其中F是G中所有面的集合。第4頁，課件共23頁，創作于2023年2月相關定義、定理及推論定理1：若G=<V，E，F>是連通平面圖，則∑f∈Fd(f)=2|E|.定理2：若G=<V，E，F>是連通平面圖，則|V|-|E|+|F|=2.證明：首先假定G是樹，則|E|=|V|-1，G只有一個無限面，

因此|V|-|E|+|F|=|V|-(|V|-1)+1=2.

現在假設G不是樹，由于G是連通的，故G中至少存在一個基本圈C，于是G必有一個有限面f，而f的邊界是由基本圈C及可能連同計算兩次的一些邊組成.如果從G中刪去基本圈C上的一條邊后得到的平面圖G1=<V1，E1，F1>，則|V1|=|V|，|E1|=|E|-1，|F1|=|F|-1，故|V1|-|E1|+|F1|=|V|-|E|+|F|，仿此做下去，最終得到G的一棵生成樹T0=<V0，E0，F0>，于是|V|-|E|+|F|=|V0|-|E0|+|F0|=2.第5頁，課件共23頁，創作于2023年2月相關定義、定理及推論推論1：給定連通簡單平面圖G=<V，E，F>，若|V|≥3，則|E|≤3|V|-6且|F|≤2|V|-4.推論2：設G=<V，E，F>是連通簡單平面圖，若|V|≥3，則存在v∈V，使得d(v)≤5.鄰接表、散列表結構O(|V|)VS鄰接矩陣結構O(|V|2)推論1：|E|=O(|V|)第6頁，課件共23頁，創作于2023年2月應用-例1:水平可見線段(CEPC2001)平面上有N(N<=8000)條互不相連的豎直線段。如果兩條線段可以被一條不經過第三條豎直線段的水平線段連接，則這兩條豎直線段被稱為“水平可見”的。三條兩兩“水平可見”的線段構成一個“三元組”。求給定輸入中“三元組”的數目。（坐標值為0到8000的整數）第7頁，課件共23頁，創作于2023年2月應用-例1:水平可見線段(CEPC2001)分析把線段看成點若兩條線段水平可見，則在對應兩點之間連一條邊，建立無向圖G統計G中的三角形的數目第8頁，課件共23頁，創作于2023年2月應用-例1:水平可見線段(CEPC2001)算法一設數組C[I]（I=0..2Ymax），C[2y]表示覆蓋y點的最后一條線段，C[2y+1]表示覆蓋區間(y,y+1)的最后一條線段把線段按從左到右的順序排序依次檢查每一條線段L(L=[y'，y''])檢查L覆蓋的所有整點和單位區間（C[u]，u=2y'..2y''）若C[u]≠0，則G.AddEdge(C[u]，L)C[u]←LO(NlogN)O(N)O(Ymax)總計：O(NYmax)時間性能分析如何建立圖G？第9頁，課件共23頁，創作于2023年2月應用-例1:水平可見線段(CEPC2001)算法二定義線段樹T：設節點N描述區間[a,b]的覆蓋情況 0 (無線段覆蓋[a,b])則N.Cover= L (線段L完全覆蓋[a,b]) -1 (其他情形)線段樹的存儲：

使用完全二叉樹的數組結構，可以免去復雜的指針運算和不必要的空間浪費。如何建立圖G？時間性能分析排序：O(NlogN)檢索：O(NlogYmax)插入：O(NlogYmax)總計：O(NlogYmax)空間性能分析線段：O(N)線段樹：O(Ymax)邊表：O(N)第10頁，課件共23頁，創作于2023年2月應用-例1:水平可見線段(CEPC2001)算法一

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

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

算法一只是單純的枚舉，沒有注意到問題的實際情況，而實際上三角形的數目是很少的，算法一作了許多無用的枚舉，因此效率很低。

算法二從邊出發，枚舉第三個頂點，這正好符合了問題的實際情況，避免了許多不必要的枚舉，所以算法二比算法一更加高效。統計圖G中三角形的數目第11頁，課件共23頁，創作于2023年2月應用-例1:水平可見線段(CEPC2001)算法三—換個角度，從點出發

每次選取度最小的點v，由推論2知d(v)≤5，只需花常數時間就可以計算含點v的三角形的數目.

應用二叉堆可以提高尋找和刪除點v的效率，總的時間復雜度僅為O(NlogN)算法二與算法三的比較

算法二是以邊作為出發點的，從整體上看，平面圖中三角形的個數只是O(N)級的，而算法二的復雜度卻是O(N2)，這種浪費是判斷條件過于復雜造成的。算法三從點出發，則只需要判斷某兩點是否相鄰即可。有沒有更好的辦法？第12頁，課件共23頁，創作于2023年2月應用-例2:洞穴(CEOI97)在同一水平面上有N(N<=500)個洞穴，洞穴之間有通道相連，且每個洞穴恰好連著三個通道。通道與通道不相交，每個通道都有一個難度值，現從1號洞穴開始遍歷所有的洞穴剛好一次并回到洞穴1，求通過通道難度值之和的最小值。(給定所有通道的信息和在外圈上的洞穴)第13頁，課件共23頁，創作于2023年2月應用-例2:洞穴(CEOI97)分析本題求的是最優路徑，但最優路徑具備什么性質并不明顯，故考慮深度優先搜索。N最大達到500，考慮剪枝以提高效率。基本剪枝條件：若當前路徑的難度值的總和比當前最優值大則放棄當前路徑。為了找到強剪枝條件，考慮問題所具有的特性所有點的度數為3所給的圖是平面圖外圈上的點已知第14頁，課件共23頁，創作于2023年2月應用-例2:洞穴(CEOI97)情形一

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

在所有未訪問的洞穴中，與其相鄰的已訪問過的洞穴（第1個與當前訪問的最后一個除外）的個數小于等于1。410912117856213第15頁，課件共23頁，創作于2023年2月應用-例2:洞穴(CEOI97)情形二

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

設外圈上的點按連接順序為1,a2,…,ak，則訪問的順序只能為：

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