集訓(xùn)隊作業(yè)平面嵌入

1、平面嵌入四川省綿陽南山中學(xué) 古楠應(yīng)用算法在實際中的重要應(yīng)用是電路板設(shè)計.平面嵌入的目的不過是讓所有的邊都不相交!目的3相關(guān)定義:平面嵌入: 在平面內(nèi)將一張圖轉(zhuǎn)化為所有邊都不相交(除開段點處相交)的圖的過程.平面圖: 能夠進(jìn)行平面嵌入的圖.對于一張n個節(jié)點的圖算法的目的：算法可以用O(n)的時間判斷一張圖是不是平面圖并且實現(xiàn)平面嵌入,但由于時間的關(guān)系,我這里只介紹O(n2)的算法.定義深度優(yōu)先遍歷首先對圖進(jìn)行一次深度優(yōu)先遍歷. 然后每個點將擁有屬于它的邊.將這些邊做這樣的定義:樹邊:在深度優(yōu)先搜索樹中,節(jié)點與它兒子相連的邊.回落邊:節(jié)點與它非兒子后裔相連的邊.平面圖的邊不會超過3n-5條.定理簡

2、略流程建立一張空圖GP,然后進(jìn)行深度優(yōu)先遍歷,完成后按照逆向深度優(yōu)先搜索序處理所有節(jié)點:把節(jié)點的樹邊加入圖GP中.向下遍歷, 同時將節(jié)點的回落邊加入到圖GP中 walkdown.v2加入樹邊當(dāng)處理節(jié)點v的時候,會首先加入節(jié)點v的樹邊,不過在加入樹邊的時候得做一個分離操作:v1c1c2v將v1和v2稱做它們所在的連通分量的根.將v1和v2所在的分量稱作v的子塊.Walkdown 向下遍歷(1)向下遍歷 回落邊的加入過程在處理節(jié)點v的時候,會進(jìn)入它的每個子塊進(jìn)行順時針和逆時針兩次遍歷,當(dāng)回到連通分量的根節(jié)點或者遭遇終止節(jié)點時就會停止遍歷.終止節(jié)點:是外部活躍節(jié)點但不是相關(guān)節(jié)點的節(jié)點.外部活躍與相關(guān)

3、設(shè)當(dāng)前處理節(jié)點為v, 對于原有節(jié)點,定義如下:外部活躍節(jié)點:與v的祖先有連接的節(jié)點子塊中有外部活躍節(jié)點的節(jié)點相關(guān)節(jié)點:與v有連接的節(jié)點子塊中有相關(guān)節(jié)點的節(jié)點外部活躍與相關(guān)uvvswswke在這張圖中,當(dāng)前處理節(jié)點為v,k,s為外部活躍節(jié)點,e,w為相關(guān)節(jié)點.Walkdown 向下遍歷(2)由于終止節(jié)點的存在,隨機的遍歷會很快遭遇終止節(jié)點而終止遍歷,這將導(dǎo)致需要加入的邊沒有加入到圖GP中.所以在遍歷的時候有一個原則.盡量晚的終止遍歷.有兩個法則來約束遍歷,從而維護(hù)這個原則.Walkdown 向下遍歷(2)法則1:當(dāng)節(jié)點有多個子塊需要遍歷的時候,總是先進(jìn)入沒有外部活躍節(jié)點的子塊進(jìn)行遍歷.法則2:每

4、次進(jìn)入子塊進(jìn)行遍歷都優(yōu)先選擇是走向只具有相關(guān)性節(jié)點方向,否則選擇走向具有相關(guān)性的節(jié)點的方向.Walkdown 向下遍歷(2)節(jié)點是相關(guān)節(jié)點,那么加入回落邊.在滿足兩個法則的情況下,向下遍歷時,會依次處理下面幾種情況:遇到終止節(jié)點或者塊的根時,終止遍歷.節(jié)點有包含相關(guān)節(jié)點的子塊,到它子塊中繼續(xù)遍歷.節(jié)點不是外部活躍節(jié)點,走向下一節(jié)點.當(dāng)加入回落邊的以后,會將該邊所連接的兩個塊和它們之間的塊全部合并.它和分離是對應(yīng)的.節(jié)點所在塊與子塊合并后也不再擁有該子塊.分離是在加入樹邊的時候.Walkdown 向下遍歷(2)合并是在加入回落邊以后.翻轉(zhuǎn)操作為了將所有的回落邊都順利的加入圖GP 中,圖GP 必須

5、始終滿足一個性質(zhì). 這個性質(zhì)就是:外部活躍節(jié)點都必須留在外部面上.翻轉(zhuǎn)操作我們把接觸最外層空間的面,叫做外部面.(圖中黃線標(biāo)出的面)翻轉(zhuǎn)操作為了將所有的回落邊都順利的加入圖GP 中,圖GP 必須始終滿足一個性質(zhì). 這個性質(zhì)就是:外部活躍節(jié)點都必須留在外部面上.加入回落邊的時候會覆蓋向下遍歷時經(jīng)過的面,這可能導(dǎo)致外部活躍節(jié)點被覆蓋,為了保證圖GP的性質(zhì).定義一個翻轉(zhuǎn)操作.翻轉(zhuǎn)操作uvwevwewewewewewewewewewewewewewewewewewewewewewewewewewewes1Walkdown 向下遍歷(3)uvwkvw ks2ees信息取得算法需要有快速取得外部活躍信息和

6、相關(guān)信息的方法.對于外部活躍信息可以通過預(yù)處理和以后的維護(hù)來快速取得.對于相關(guān)節(jié)點,可以在向下遍歷時查找取得.O(n)的算法有另一種取得方式(請參考論文).接下來我們具體介紹外部活躍信息的取得.外部活躍信息的取得快速的取得外部活躍信息外部活躍信息.給每個節(jié)點配備一個lowpoint,表示它能直接或者間接到達(dá)的最早祖先,間接是指通過它的子孫到達(dá).可以通過開始的深度優(yōu)先搜索取得所有節(jié)點的lowpoint.外部活躍信息的取得給每個節(jié)點配備一個SDlist,其中記錄它的所有兒子,并且是按照他們的lowpoint從小到大排序的.維護(hù)SDlist:在節(jié)點所在塊與其子塊合并后,將該兒子在該節(jié)點的SDlist

7、中的值刪除.外部活躍信息的取得快速的得到外部活躍信息:節(jié)點連接的最早祖先或者SDlist中的第一個值小于v,該節(jié)點就是外部活躍節(jié)點.虛邊在上面的圖中,s到w部分以后都是不會用到的.加入邊(v,w)覆蓋它.vsw總覽總體流程:取得相關(guān)信息.按照反向深度優(yōu)先搜索序依次處理每個節(jié)點.將節(jié)點所有的樹邊加入圖GP中.進(jìn)入v的每個子塊向下遍歷.分離操作合并操作翻轉(zhuǎn)操作總結(jié) 復(fù)雜的問題總是能夠簡化的.只要我們不畏困難,勇敢攀登,它們一定都能解決. 我們也不可能學(xué)完所有的算法,但是只有不斷的汲取,才能提高和完善自己.謝謝!歡迎提問!快速翻轉(zhuǎn)當(dāng)進(jìn)入子塊進(jìn)行遍歷會從新選擇方向,當(dāng)選擇方向與原有方向不同時,就需要進(jìn)

8、行翻轉(zhuǎn)操作.對外部面O(1)的翻轉(zhuǎn):只需要交換塊根節(jié)點的兩個方向的指示.在以后的遍歷中,只需要知道由哪一個節(jié)點到達(dá),并且走向下一節(jié)點.快速翻轉(zhuǎn)對鄰接表的翻轉(zhuǎn):對于節(jié)點的子塊,如果翻轉(zhuǎn),將該節(jié)點與子塊中唯一的兒子相連的樹邊標(biāo)記為-1.最后對圖只經(jīng)過樹邊進(jìn)行一次深搜,當(dāng)?shù)竭_(dá)節(jié)點經(jīng)過了奇數(shù)個-1,就將節(jié)點的鄰接表前后顛倒.相關(guān)信息的取得walkup 向上遍歷:存在回落邊(v,w),從w開始沿著外部面向上遍歷到v.并且給每個節(jié)點配備一個proots,表示它有哪些塊包含相關(guān)節(jié)點.從外部面的兩個方向同時遍歷.遇到遍歷過的點就停止遍歷.在從節(jié)點的子塊上升到該節(jié)點時,將該子塊加入到節(jié)點的proots中.相關(guān)信息的取得在向proots中加入子塊的時候.為了保證法