-
平面性算法
鎖定
- 中文名
- 平面性算法
- 外文名
- planarity algorithm
- 所屬學科
- 數學(圖論)
- 屬 性
- 圖論中的一種重要算法
- 相關概念
- 可平面圖,平面嵌入等
平面性算法基本介紹
平面性算法(planarity algorithm)是一種求平面嵌入的算法,指判斷一個給定的圖是否是可平面圖,並且如果它是可平面圖,則要找出它的平面嵌入來。設H是圖G的一個可平面子圖,
是H在這個平面中的一個嵌入,若G是可平面圖,且存在G的一個平面嵌入
,使得
,則稱
是G容許的。例如,圖1表示G的一個平面子圖的兩個嵌人;一個是G容許的,而另一個則不是。
若B是H(在G中)的任意一座橋,且B對於H的接觸點都包含在
的面
的周界上,則稱B在
的面
內是可畫的。用
表示在
中橋B是可畫出的那些面的集。
平面性算法相關定理
平面性算法是基於如下定理:
若
是容許的,則對於H的每座橋B,
。
證明:若
是G容許的,則根據定義,存在G的一個平面嵌入
,使得
。顯然,H的橋B所對應的
的子圖必然限制在
的一個面中,因此
。
由於一個圖是平面圖當且僅當它的基礎簡單圖的每個塊都是平面圖,所以只要考察簡單塊就夠了。給定這樣的一個圖G後。算法就確定了G的一個平面子圖的遞增序列
,以及對應的平面嵌入
,終止於G的一個平面嵌入。對每一步,都應用定理的必要條件,來判斷G的非平面性
[2]
。
平面性算法具體過程
步驟如下:
1.設
是G的一個圈,找出
的一個平面嵌入
,置
;
2.若
,則停止;否則,確定G中
的所有橋;對於每座這樣的橋B,找出集
;
3.若存在一座橋B,使得
,則停止,根據定理,G是非平面圖,若存在一座橋B,使得
,則令
,否則令B是任一座橋,且
是任一使得
的面;
4.選擇一條連結B對於
的兩個接觸頂點的路
,置
,並把
畫在
的面
內,得到
的一個平面嵌
,令
,轉入步驟2。
這個算法是一個有效算法,它的主要運算包括:
(i) 找出圖G中的一個圈
;
(ii) 確定G中
的橋以及它們對於
的接觸頂點;
(iii) 對於
的每個面
確定
;
(iv) 對於
的每座橋B,確定
;
(v) 在G的某座橋B中求
的兩個頂點之間的一條路P;
上述每一個運算都存在有效算法,因此,這個算法是一個有效算法。繼這個方法之後,許多研究者都致力於這種平面性算法的研究並提出了一些算法。
平面性算法應用舉例
為了説明這個算法,考察圖2中的圖G,從圈
和G的一張橋的表開始(為了簡潔起見,橋用其邊集來表示);在每一步中。對於
的橋B以粗體字標出。這個例子中,算法終止於G的一個平面嵌入
,所以G是平面圖。