基本介紹
- 中文名：平面性算法
- 外文名：planarity algorithm
- 所屬學科：數學（圖論）
- 屬性：圖論中的一種重要算法
- 相關概念：可平面圖，平面嵌入等
基本介紹,相關定理,具體過程,套用舉例,
基本介紹
平面性算法(planarity algorithm)是一種求平面嵌入的算法，指判斷一個給定的圖是否是可平面圖，並且如果它是可平面圖，則要找出它的平面嵌入來。設H是圖G的一個可平面子圖，
是H在這個平面中的一個嵌入，若G是可平面圖，且存在G的一個平面嵌入
，使得
，則稱 是G容許的。例如，圖1表示G的一個平面子圖的兩個嵌人；一個是G容許的，而另一個則不是。
圖1(a) G
圖1(b) G容許的嵌入
圖1(c) G不容許的嵌入
若B是H(在G中)的任意一座橋，且B對於H的接觸點都包含在 的面
的周界上，則稱B在 的面 內是可畫的。用
表示在 中橋B是可畫出的那些面的集。
相關定理
平面性算法是基於如下定理：
若 是容許的，則對於H的每座橋B，
。
證明：若 是G容許的，則根據定義，存在G的一個平面嵌入 ，使得 。顯然，H的橋B所對應的 的子圖必然限制在 的一個面中，因此 。
由於一個圖是平面圖若且唯若它的基礎簡單圖的每個塊都是平面圖，所以只要考察簡單塊就夠了。給定這樣的一個圖G後。算法就確定了G的一個平面子圖的遞增序列
，以及對應的平面嵌入
，終止於G的一個平面嵌入。對每一步，都套用定理的必要條件，來判斷G的非平面性。
具體過程
步驟如下：
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
為了說明這個算法，考察圖2中的圖G，從圈
和G的一張橋的表開始(為了簡潔起見，橋用其邊集來表示)；在每一步中。對於 的橋B以粗體字標出。這個例子中，算法終止於G的一個平面嵌入
，所以G是平面圖。
 |   |   |
  |   |   |
  |   |  |
