圖的平面性判定算法研究與實(shí)現(xiàn).pdf

1、圖是一個(gè)抽象數(shù)據(jù)結(jié)構(gòu),常用于為信息結(jié)構(gòu)建模。圖能夠?yàn)楝F(xiàn)實(shí)世界中對(duì)象的任意信息建模,表示對(duì)象和對(duì)象之間的關(guān)聯(lián)關(guān)系。
　　 平面圖在圖論和圖形繪制中擔(dān)任著重要的角色。長(zhǎng)期以來(lái),平面圖理論在印制電路板的設(shè)計(jì)和大規(guī)模集成電路的布線方面有著重要應(yīng)用。目前,數(shù)據(jù)可視化的應(yīng)用日益廣泛,如可視化數(shù)據(jù)挖掘,網(wǎng)絡(luò)的可視化等,平面圖也有非常大的作用。
　　 平面圖是所有邊都不交叉的圖。平面圖問(wèn)題包括兩部分:圖的平面性判定和平面圖繪制。圖的平面

2、性判定判斷一個(gè)圖是否能以平面形式繪制。平面圖繪制是如何以平面形式繪制一個(gè)圖,即理論上是平面的圖在實(shí)際繪制時(shí)能否以平面方式畫(huà)出。本文不討論平面圖繪制的問(wèn)題。
　　 如果一個(gè)圖能夠畫(huà)在一個(gè)平面上,除了邊的端點(diǎn)以外,沒(méi)有邊交叉,這個(gè)圖就是平面的。Kurtowski指出一個(gè)圖G是平面的,充分必要條件是圖G中不包含任何子圖為K5型圖和K3,3型圖。這就是著名的Kurtowski定理。Kurtowski定理的理論意義很強(qiáng),但是在計(jì)算機(jī)上用K

3、urtowski定理進(jìn)行平面性判定,算法復(fù)雜性很高,也不易于實(shí)現(xiàn)。一般不使用。
　　 本文研究了計(jì)算平面圖節(jié)點(diǎn)st-編號(hào)的算法,并研究了st-編號(hào)的叢形式。在此基礎(chǔ)上,研究了PQ樹(shù)構(gòu)造算法,實(shí)現(xiàn)了用PQ樹(shù)構(gòu)造算法進(jìn)行了圖的平面性判定。
　　 圖的平面性判定算法都是一些很復(fù)雜的算法,實(shí)現(xiàn)起來(lái)比較困難。本人對(duì)算法進(jìn)行了認(rèn)真的分析,耐心的調(diào)試,不但從理論上闡述了這些算法,并實(shí)現(xiàn)了這些算法。
　　 在本課題中,本人還參與