基本介紹
![平面性算法](/img/2/c09/wZwpmL2cDOxUjNwITM0YTN1UTM1QDN5MjM5ADMwAjMwUzLyEzLzAzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
![平面性算法](/img/b/142/wZwpmL2QTOxUDMwczNzYTN1UTM1QDN5MjM5ADMwAjMwUzL3czL1czLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
![平面性算法](/img/e/858/wZwpmL4EzM1QzM0IzNzYTN1UTM1QDN5MjM5ADMwAjMwUzLyczL1MzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
![平面性算法](/img/2/c09/wZwpmL2cDOxUjNwITM0YTN1UTM1QDN5MjM5ADMwAjMwUzLyEzLzAzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
平面性算法(planarity algorithm)是一種求 平面嵌入的算法,指判斷一個給定的圖是否是可平面圖,並且如果它是可平面圖,則要找出它的平面嵌入來。設H是圖G的一個可平面子圖, 是H在這個平面中的一個嵌入,若G是可平面圖,且存在G的一個平面嵌入 ,使得 ,則稱 是G 容許的。例如,圖1表示G的一個平面子圖的兩個嵌人;一個是G容許的,而另一個則不是。
![圖1(a) G](/img/4/e66/wZwpmL0AzN0AzM0UTM0YTN1UTM1QDN5MjM5ADMwAjMwUzL1EzLyYzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
![圖1(b) G容許的嵌入](/img/e/050/wZwpmL4ETM4IDM4YDOzYTN1UTM1QDN5MjM5ADMwAjMwUzL2gzL4EzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
![圖1(c) G不容許的嵌入](/img/5/2d4/wZwpmLxQDO1EzNwQDOzYTN1UTM1QDN5MjM5ADMwAjMwUzL0gzL1YzLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
![平面性算法](/img/2/c09/wZwpmL2cDOxUjNwITM0YTN1UTM1QDN5MjM5ADMwAjMwUzLyEzLzAzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
![平面性算法](/img/8/778/wZwpmL2MzN5UzM2MzNwIDN0UTMyITNykTO0EDMwAjMwUzLzczL4MzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
![平面性算法](/img/2/c09/wZwpmL2cDOxUjNwITM0YTN1UTM1QDN5MjM5ADMwAjMwUzLyEzLzAzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
![平面性算法](/img/8/778/wZwpmL2MzN5UzM2MzNwIDN0UTMyITNykTO0EDMwAjMwUzLzczL4MzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
![平面性算法](/img/9/308/wZwpmLyITO5YTN5EDM0YTN1UTM1QDN5MjM5ADMwAjMwUzLxAzLxUzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
![平面性算法](/img/2/c09/wZwpmL2cDOxUjNwITM0YTN1UTM1QDN5MjM5ADMwAjMwUzLyEzLzAzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
若B是H(在G中)的任意一座橋,且B對於H的接觸點都包含在 的面 的周界上,則稱B在 的面 內是 可畫的。用 表示在 中橋B是可畫出的那些面的集。
相關定理
平面性算法是基於如下定理:
![平面性算法](/img/2/c09/wZwpmL2cDOxUjNwITM0YTN1UTM1QDN5MjM5ADMwAjMwUzLyEzLzAzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
![平面性算法](/img/d/922/wZwpmL2gDO5MTMyEzNzYTN1UTM1QDN5MjM5ADMwAjMwUzLxczL3gzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
若 是容許的,則對於H的每座橋B, 。
![平面性算法](/img/2/c09/wZwpmL2cDOxUjNwITM0YTN1UTM1QDN5MjM5ADMwAjMwUzLyEzLzAzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
![平面性算法](/img/b/142/wZwpmL2QTOxUDMwczNzYTN1UTM1QDN5MjM5ADMwAjMwUzL3czL1czLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
![平面性算法](/img/e/858/wZwpmL4EzM1QzM0IzNzYTN1UTM1QDN5MjM5ADMwAjMwUzLyczL1MzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
![平面性算法](/img/b/142/wZwpmL2QTOxUDMwczNzYTN1UTM1QDN5MjM5ADMwAjMwUzL3czL1czLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
![平面性算法](/img/2/c09/wZwpmL2cDOxUjNwITM0YTN1UTM1QDN5MjM5ADMwAjMwUzLyEzLzAzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
![平面性算法](/img/d/922/wZwpmL2gDO5MTMyEzNzYTN1UTM1QDN5MjM5ADMwAjMwUzLxczL3gzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
證明:若 是G容許的,則根據定義,存在G的一個平面嵌入 ,使得 。顯然,H的橋B所對應的 的子圖必然限制在 的一個面中,因此 。
![平面性算法](/img/6/48e/wZwpmL3cTM0IjNyczM3QTN1UTM1QDN5MjM5ADMwAjMwUzL3MzLzczLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
![平面性算法](/img/7/acd/wZwpmL0cDOwgjN4kTOzYTN1UTM1QDN5MjM5ADMwAjMwUzL5kzL3czLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
由於一個圖是平面圖若且唯若它的基礎簡單圖的每個塊都是平面圖,所以只要考察簡單塊就夠了。給定這樣的一個圖G後。算法就確定了G的一個平面子圖的遞增序列 ,以及對應的平面嵌入 ,終止於G的一個平面嵌入。對每一步,都套用定理的必要條件,來判斷G的非平面性 。
具體過程
步驟如下:
![平面性算法](/img/7/19c/wZwpmLxQjNycDN4YTO2UzM1UTM1QDN5MjM5ADMwAjMwUzL2kzL1QzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
![平面性算法](/img/7/19c/wZwpmLxQjNycDN4YTO2UzM1UTM1QDN5MjM5ADMwAjMwUzL2kzL1QzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
![平面性算法](/img/6/fba/wZwpmL4cTMyADM3UjNxUTN1UTM1QDN5MjM5ADMwAjMwUzL1YzLzAzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
![平面性算法](/img/1/d63/wZwpmL1EjN5EzNwAzNzYTN1UTM1QDN5MjM5ADMwAjMwUzLwczLxgzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
1.設 是G的一個圈,找出 的一個平面嵌入 ,置 ;
![平面性算法](/img/5/77c/wZwpmL2QDNxYTN4QDM0YTN1UTM1QDN5MjM5ADMwAjMwUzL0AzLzYzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
![平面性算法](/img/b/20b/wZwpmLxETMwAzMzgzNxMzM1UTM1QDN5MjM5ADMwAjMwUzL4czL1QzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
![平面性算法](/img/2/be6/wZwpmL3QDOzkDO4ITM0YTN1UTM1QDN5MjM5ADMwAjMwUzLyEzL1YzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
2.若 ,則停止;否則,確定G中 的所有橋;對於每座這樣的橋B,找出集 ;
![平面性算法](/img/b/564/wZwpmL2IjM1czNykDOzYTN1UTM1QDN5MjM5ADMwAjMwUzL5gzL4gzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
![平面性算法](/img/f/340/wZwpmL0ITN1gzN1YDOzYTN1UTM1QDN5MjM5ADMwAjMwUzL2gzLyYzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
![平面性算法](/img/c/287/wZwpmLyYjM0gTNzIDOxUTN1UTM1QDN5MjM5ADMwAjMwUzLygzLwUzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
![平面性算法](/img/8/778/wZwpmL2MzN5UzM2MzNwIDN0UTMyITNykTO0EDMwAjMwUzLzczL4MzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
![平面性算法](/img/5/298/wZwpmL3QTMwITO5QDNxUTN1UTM1QDN5MjM5ADMwAjMwUzL0QzLzMzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
3.若存在一座橋B,使得 ,則停止,根據定理,G是非平面圖,若存在一座橋B,使得 ,則令 ,否則令B是任一座橋,且 是任一使得 的面;
![平面性算法](/img/b/20b/wZwpmLxETMwAzMzgzNxMzM1UTM1QDN5MjM5ADMwAjMwUzL4czL1QzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
![平面性算法](/img/5/620/wZwpmL1EzN1QDNzITOzYTN1UTM1QDN5MjM5ADMwAjMwUzLykzLwQzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
![平面性算法](/img/0/c64/wZwpmLwADOxkDN1gjMxUTN1UTM1QDN5MjM5ADMwAjMwUzL4IzLzMzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
![平面性算法](/img/b/1f1/wZwpmLyMTN0QDM3AzNwMzM1UTM1QDN5MjM5ADMwAjMwUzLwczL2EzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
![平面性算法](/img/a/da5/wZwpmL2cTM5kzMwkTOzYTN1UTM1QDN5MjM5ADMwAjMwUzL5kzL4MzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
![平面性算法](/img/8/778/wZwpmL2MzN5UzM2MzNwIDN0UTMyITNykTO0EDMwAjMwUzLzczL4MzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
![平面性算法](/img/d/fa9/wZwpmL4QjN4IzMyczNzYTN1UTM1QDN5MjM5ADMwAjMwUzL3czL1gzLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
![平面性算法](/img/a/f17/wZwpmL1MzM0gjMwkDM0YTN1UTM1QDN5MjM5ADMwAjMwUzL5AzL4YzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
![平面性算法](/img/2/1db/wZwpmLyEjM3kDNyEDOzYTN1UTM1QDN5MjM5ADMwAjMwUzLxgzL0UzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
4.選擇一條連結B對於 的兩個接觸頂點的路 ,置 ,並把 畫在 的面 內,得到 的一個平面嵌 ,令 ,轉入步驟2。
這個算法是一個有效算法,它的主要運算包括:
![平面性算法](/img/7/19c/wZwpmLxQjNycDN4YTO2UzM1UTM1QDN5MjM5ADMwAjMwUzL2kzL1QzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
(i) 找出圖G中的一個圈 ;
![平面性算法](/img/b/20b/wZwpmLxETMwAzMzgzNxMzM1UTM1QDN5MjM5ADMwAjMwUzL4czL1QzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
![平面性算法](/img/b/20b/wZwpmLxETMwAzMzgzNxMzM1UTM1QDN5MjM5ADMwAjMwUzL4czL1QzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
(ii) 確定G中 的橋以及它們對於 的接觸頂點;
![平面性算法](/img/a/da5/wZwpmL2cTM5kzMwkTOzYTN1UTM1QDN5MjM5ADMwAjMwUzL5kzL4MzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
![平面性算法](/img/8/778/wZwpmL2MzN5UzM2MzNwIDN0UTMyITNykTO0EDMwAjMwUzLzczL4MzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
![平面性算法](/img/9/789/wZwpmLwgDN1QjN4IDOzYTN1UTM1QDN5MjM5ADMwAjMwUzLygzL0czLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
(iii) 對於 的每個面 確定 ;
![平面性算法](/img/a/da5/wZwpmL2cTM5kzMwkTOzYTN1UTM1QDN5MjM5ADMwAjMwUzL5kzL4MzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
![平面性算法](/img/2/be6/wZwpmL3QDOzkDO4ITM0YTN1UTM1QDN5MjM5ADMwAjMwUzLyEzL1YzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
(iv) 對於 的每座橋B,確定 ;
![平面性算法](/img/b/362/wZwpmL4YzM5gjMzgjNzYTN1UTM1QDN5MjM5ADMwAjMwUzL4YzLzgzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
(v) 在G的某座橋B中求 的兩個頂點之間的一條路P;
上述每一個運算都存在有效算法,因此,這個算法是一個有效算法。繼這個方法之後,許多研究者都致力於這種平面性算法的研究並提出了一些算法。
套用舉例
![圖2 G](/img/b/962/wZwpmL3EDM1cDO3IDM0YTN1UTM1QDN5MjM5ADMwAjMwUzLyAzLyYzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
![平面性算法](/img/8/cbd/wZwpmL2YzN3MDN2MzNxUTN1UTM1QDN5MjM5ADMwAjMwUzLzczLxUzLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
![平面性算法](/img/f/340/wZwpmL0ITN1gzN1YDOzYTN1UTM1QDN5MjM5ADMwAjMwUzL2gzLyYzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
![平面性算法](/img/1/297/wZwpmLyIjM4cTOxczNzYTN1UTM1QDN5MjM5ADMwAjMwUzL3czLxgzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
為了說明這個算法,考察圖2中的圖G,從圈 和G的一張橋的表開始(為了簡潔起見,橋用其邊集來表示);在每一步中。對於 的橋B以粗體字標出。這個例子中,算法終止於G的一個平面嵌入 ,所以G是平面圖。
![]() ![]() | ![]() ![]() | ![]() ![]() |
![]() ![]() | ![]() ![]() | ![]() ![]() |
![]() ![]() | ![]() ![]() | ![]() ![]() |