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

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

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

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