算法合集之平面嵌入

算法合集之平面嵌入第一頁，共三十一頁，編輯于2023年，星期三應(yīng)用算法在實(shí)際中的重要應(yīng)用是電路板設(shè)計(jì).第二頁，共三十一頁，編輯于2023年，星期三２４５３１平面嵌入的目的不過是讓所有的邊都不相交!目的２3４５１第三頁，共三十一頁，編輯于2023年，星期三相關(guān)定義:平面嵌入:在平面內(nèi)將一張圖轉(zhuǎn)化為所有邊都不相交(除開段點(diǎn)處相交)的圖的過程.平面圖:能夠進(jìn)行平面嵌入的圖.對于一張n個(gè)節(jié)點(diǎn)的圖算法的目的：算法可以用O(n)的時(shí)間判斷一張圖是不是平面圖并且實(shí)現(xiàn)平面嵌入,但由于時(shí)間的關(guān)系,我這里只介紹O(n2)的算法.定義第四頁，共三十一頁，編輯于2023年，星期三深度優(yōu)先遍歷首先對圖進(jìn)行一次深度優(yōu)先遍歷.然后每個(gè)點(diǎn)將擁有屬于它的邊.將這些邊做這樣的定義:樹邊:在深度優(yōu)先搜索樹中,節(jié)點(diǎn)與它兒子相連的邊.回落邊:節(jié)點(diǎn)與它非兒子后裔相連的邊.平面圖的邊不會超過3n-5條.[定理]第五頁，共三十一頁，編輯于2023年，星期三簡略流程建立一張空圖GP,然后進(jìn)行深度優(yōu)先遍歷,完成后按照逆向深度優(yōu)先搜索序處理所有節(jié)點(diǎn):把節(jié)點(diǎn)的樹邊加入圖GP中.向下遍歷,同時(shí)將節(jié)點(diǎn)的回落邊加入到圖GP中—walkdown.第六頁，共三十一頁，編輯于2023年，星期三v2加入樹邊當(dāng)處理節(jié)點(diǎn)v的時(shí)候,會首先加入節(jié)點(diǎn)v的樹邊,不過在加入樹邊的時(shí)候得做一個(gè)分離操作:v1c1c2v將v1和v2稱做它們所在的連通分量的根.將v1和v2所在的分量稱作v的子塊.第七頁，共三十一頁，編輯于2023年，星期三Walkdown—向下遍歷(1)向下遍歷—回落邊的加入過程在處理節(jié)點(diǎn)v的時(shí)候,會進(jìn)入它的每個(gè)子塊進(jìn)行順時(shí)針和逆時(shí)針兩次遍歷,當(dāng)回到連通分量的根節(jié)點(diǎn)或者遭遇終止節(jié)點(diǎn)時(shí)就會停止遍歷.終止節(jié)點(diǎn):是外部活躍節(jié)點(diǎn)但不是相關(guān)節(jié)點(diǎn)的節(jié)點(diǎn).第八頁，共三十一頁，編輯于2023年，星期三外部活躍與相關(guān)設(shè)當(dāng)前處理節(jié)點(diǎn)為v,對于原有節(jié)點(diǎn),定義如下:外部活躍節(jié)點(diǎn):與v的祖先有連接的節(jié)點(diǎn)子塊中有外部活躍節(jié)點(diǎn)的節(jié)點(diǎn)相關(guān)節(jié)點(diǎn):與v有連接的節(jié)點(diǎn)子塊中有相關(guān)節(jié)點(diǎn)的節(jié)點(diǎn)第九頁，共三十一頁，編輯于2023年，星期三外部活躍與相關(guān)uvv’sws’w’ke在這張圖中,當(dāng)前處理節(jié)點(diǎn)為v,k,s為外部活躍節(jié)點(diǎn),e,w為相關(guān)節(jié)點(diǎn).第十頁，共三十一頁，編輯于2023年，星期三Walkdown—向下遍歷(2)由于終止節(jié)點(diǎn)的存在,隨機(jī)的遍歷會很快遭遇終止節(jié)點(diǎn)而終止遍歷,這將導(dǎo)致需要加入的邊沒有加入到圖GP中.所以在遍歷的時(shí)候有一個(gè)原則.盡量晚的終止遍歷.有兩個(gè)法則來約束遍歷,從而維護(hù)這個(gè)原則.第十一頁，共三十一頁，編輯于2023年，星期三Walkdown—向下遍歷(2)法則1:當(dāng)節(jié)點(diǎn)有多個(gè)子塊需要遍歷的時(shí)候,總是先進(jìn)入沒有外部活躍節(jié)點(diǎn)的子塊進(jìn)行遍歷.法則2:每次進(jìn)入子塊進(jìn)行遍歷都優(yōu)先選擇是走向只具有相關(guān)性節(jié)點(diǎn)方向,否則選擇走向具有相關(guān)性的節(jié)點(diǎn)的方向.第十二頁，共三十一頁，編輯于2023年，星期三Walkdown—向下遍歷(2)節(jié)點(diǎn)是相關(guān)節(jié)點(diǎn),那么加入回落邊.在滿足兩個(gè)法則的情況下,向下遍歷時(shí),會依次處理下面幾種情況:遇到終止節(jié)點(diǎn)或者塊的根時(shí),終止遍歷.節(jié)點(diǎn)有包含相關(guān)節(jié)點(diǎn)的子塊,到它子塊中繼續(xù)遍歷.節(jié)點(diǎn)不是外部活躍節(jié)點(diǎn),走向下一節(jié)點(diǎn).第十三頁，共三十一頁，編輯于2023年，星期三當(dāng)加入回落邊的以后,會將該邊所連接的兩個(gè)塊和它們之間的塊全部合并.它和分離是對應(yīng)的.節(jié)點(diǎn)所在塊與子塊合并后也不再擁有該子塊.分離是在加入樹邊的時(shí)候.Walkdown—向下遍歷(2)合并是在加入回落邊以后.第十四頁，共三十一頁，編輯于2023年，星期三翻轉(zhuǎn)操作為了將所有的回落邊都順利的加入圖GP中,圖GP必須始終滿足一個(gè)性質(zhì).這個(gè)性質(zhì)就是:外部活躍節(jié)點(diǎn)都必須留在外部面上.第十五頁，共三十一頁，編輯于2023年，星期三翻轉(zhuǎn)操作我們把接觸最外層空間的面,叫做外部面.(圖中黃線標(biāo)出的面)第十六頁，共三十一頁，編輯于2023年，星期三翻轉(zhuǎn)操作為了將所有的回落邊都順利的加入圖GP中,圖GP必須始終滿足一個(gè)性質(zhì).這個(gè)性質(zhì)就是:外部活躍節(jié)點(diǎn)都必須留在外部面上.加入回落邊的時(shí)候會覆蓋向下遍歷時(shí)經(jīng)過的面,這可能導(dǎo)致外部活躍節(jié)點(diǎn)被覆蓋,為了保證圖GP的性質(zhì).定義一個(gè)翻轉(zhuǎn)操作.第十七頁，共三十一頁，編輯于2023年，星期三翻轉(zhuǎn)操作uvwev’wewewewewewewewewewewewewewewewewewewewewewewewewewewe第十八頁，共三十一頁，編輯于2023年，星期三s1Walkdown—向下遍歷(3)uvwkv’w

ks2ees第十九頁，共三十一頁，編輯于2023年，星期三信息取得算法需要有快速取得外部活躍信息和相關(guān)信息的方法.對于外部活躍信息可以通過預(yù)處理和以后的維護(hù)來快速取得.對于相關(guān)節(jié)點(diǎn),可以在向下遍歷時(shí)查找取得.O(n)的算法有另一種取得方式(請參考論文).接下來我們具體介紹外部活躍信息的取得.第二十頁，共三十一頁，編輯于2023年，星期三外部活躍信息的取得快速的取得外部活躍信息外部活躍信息.給每個(gè)節(jié)點(diǎn)配備一個(gè)lowpoint,表示它能直接或者間接到達(dá)的最早祖先,間接是指通過它的子孫到達(dá).可以通過開始的深度優(yōu)先搜索取得所有節(jié)點(diǎn)的lowpoint.第二十一頁，共三十一頁，編輯于2023年，星期三外部活躍信息的取得給每個(gè)節(jié)點(diǎn)配備一個(gè)SDlist,其中記錄它的所有兒子,并且是按照他們的lowpoint從小到大排序的.維護(hù)SDlist:在節(jié)點(diǎn)所在塊與其子塊合并后,將該兒子在該節(jié)點(diǎn)的SDlist中的值刪除.第二十二頁，共三十一頁，編輯于2023年，星期三外部活躍信息的取得快速的得到外部活躍信息:節(jié)點(diǎn)連接的最早祖先或者SDlist中的第一個(gè)值小于v,該節(jié)點(diǎn)就是外部活躍節(jié)點(diǎn).第二十三頁，共三十一頁，編輯于2023年，星期三虛邊在上面的圖中,s到w部分以后都是不會用到的.加入邊(v’,w)覆蓋它.v’sw第二十四頁，共三十一頁，編輯于2023年，星期三總覽總體流程:取得相關(guān)信息.按照反向深度優(yōu)先搜索序依次處理每個(gè)節(jié)點(diǎn).將節(jié)點(diǎn)所有的樹邊加入圖GP中.進(jìn)入v的每個(gè)子塊向下遍歷.分離操作合并操作翻轉(zhuǎn)操作第二十五頁，共三十一頁，編輯于2023年，星期三總結(jié)復(fù)雜的問題總是能夠簡化的.只要我們不畏困難,勇敢攀登,它們一定都能解決.我們也不可能學(xué)完所有的算法,但是只有不斷的汲取,才能提高和完善自己.謝謝!第二十六頁，共三十一頁，編輯于2023年，星期三快速翻轉(zhuǎn)當(dāng)進(jìn)入子塊進(jìn)行遍歷會從新選擇方向,當(dāng)選擇方向與原有方向不同時(shí),就需要進(jìn)行翻轉(zhuǎn)操作.對外部面O(1)的翻轉(zhuǎn):只需要交換塊根節(jié)點(diǎn)的兩個(gè)方向的指示.在以后的遍歷中,只需要知道由哪一個(gè)節(jié)點(diǎn)到達(dá),并且走向下一節(jié)點(diǎn).第二十七頁，共三十一頁，編輯于2023年，星期三快速翻轉(zhuǎn)對鄰接表的翻轉(zhuǎn):對于節(jié)點(diǎn)的子塊,如果翻轉(zhuǎn),將該節(jié)點(diǎn)與子塊中唯一的兒子相連的樹邊標(biāo)記為-1.最后對圖只經(jīng)過樹邊進(jìn)行一次深搜,當(dāng)?shù)竭_(dá)節(jié)點(diǎn)經(jīng)過了奇數(shù)個(gè)-1,就將節(jié)點(diǎn)的鄰接表前后顛倒.第二十八頁，共三十一頁，編輯于2023年，星期三相關(guān)信息的取得walkup—向上遍歷:存在回落邊(v,w),從w開始沿著外部面向上遍歷到v.并且給每個(gè)節(jié)點(diǎn)配備一個(gè)proots,表示它有哪些塊包含相關(guān)節(jié)點(diǎn).從外部面的兩個(gè)方向同時(shí)遍歷.遇到遍歷過的點(diǎn)就停止遍歷.在從節(jié)點(diǎn)的子塊上升到該節(jié)點(diǎn)時(shí),將該子塊加入到節(jié)點(diǎn)的proots中.第二十九頁，共三十一頁，編輯于2023年，星期三相關(guān)信息的取得在向proots中加入子塊的時(shí)候.為了保證法則1,進(jìn)行這樣的操作:不