可平面圖(planar graph)是一類特殊的圖，指同構於某一平面圖的圖。如果一個圖能夠畫在平面上，使得頂點集合及邊集合分別是相同的，而如果邊相交僅在邊的端點處，則稱這個圖是可嵌入平面的，或稱作可平面圖(planar graph)；否則稱作不可平面圖，可平面圖G的這樣一種畫法稱為G 的一個平面嵌入(planar embedding)。庫拉托夫斯基定理給出了可平面圖的特徵，其內容為：圖G是可平面圖若且唯若G沒有同胚於完全圖K5和完全二部圖K3,3的子圖，同胚於K5和K3,3的圖稱為庫拉托夫斯基圖。這一定理是由庫拉托夫斯基(Kuratowski，K.)於1930年證明的，若可平面圖G不是任何同階其他可平面圖的子圖，則稱G為極大可平面圖，極大可平面圖所對應的平面圖的每個面都必為三角形；同構於外平面圖的圖稱為外可平面圖；3正則的可平面圖稱為3正則平面圖；G是外可平面的若且唯若G沒有與完全圖K4同胚的子圖。
基本介紹
- 中文名：可平面圖
- 外文名：planar graph
- 所屬學科：離散數學
- 別名：可嵌入平面的
- 相關概念：平面圖、歐拉公式等
- 相關定理：庫拉托夫斯基Kuratowski定理
- 定義：如果一個可平面圖重新畫在平面上，使得沒有兩條邊相交
定義,相關性質定理,平面圖的度定理,平面圖的歐拉公式及其套用,可平面圖的判定,細分,庫拉托夫斯基Kuratowski定理,
定義
如果一個圖能夠畫在平面上，使得頂點集合及邊集合分別是相同的，而如果邊相交僅在邊的端點處，則稱這個圖是可嵌入平面的，或稱作可平面圖(planar graph)；否則稱作不可平面圖，可平面圖G的這樣一種畫法稱為G 的一個平面嵌入(planar embedding)。
如果一個可平面圖重新畫在平面上，使得沒有兩條邊相交，除非在頂點處，則稱這個圖是平面圖(plane graph)。
相關性質定理
平面圖的度定理
設G是平面圖，記m是G的邊數，則
證明:圖中的一條割邊是關聯一個面的，對該面的度貢獻為2；一條非割邊是關聯兩個不同的面的，並分別對這兩個面的度貢獻為1，因此，將所有面的度求和時，每條邊用了兩次。
平面圖的歐拉公式及其套用
不難發現，在連通平面圖中有一個關於頂點、邊及面的數目的簡單公式，因為歐拉(Euler)首先對多面體的頂點和邊所定義的平面圖建立了這個公式，所以該公式以歐拉命名。
平面圖的歐拉公式： 設G是無向連通平面圖，具有n 個頂點，m條邊和r個面，則 n-m+r=2。
推論1如果G是平面圖，則n-m+r=w+1，其中，w是G的連通分支數。
推論2 一個連通可平面圖的所有平面嵌人都有相同的面數。
證明：這是因為一個連通可平面圖的所有平面嵌人都是彼此同構的，因此在頂點數、邊數都分別相同的情況下，利用平面圖的歐拉公式，直接證得。
推論3如果G是頂點數大於等於3的簡單可平面圖，則m≤3n－6。
推論4 K5是不可平面圖。
證明：因為K5是頂點數為5的簡單圖，其m=10，n=5，3n－6 =9，有m>3n- 6，由推論3，得證K5是不可平面圖。
推論5K3,3是不可平面圖。
證明：利用K3,3是一個簡單的二部圖，其任一個迴路的長度至少是4，如果它是可平面圖，其邊數應小於等於2n-4，但是，K3,3的n=6，m=9，2n-4=8，m>2n-4，所以K3,3是不可平面圖。
推論6
如果G是簡單的可平面圖，則
其中
表示圖G的最小度。
可平面圖的判定
雖然歐拉公式可用來判別某個圖是不可平面圖，但是當頂點數和邊數較多時，套用歐拉公式進行判別就會相當困難。一個圖是否有平面的圖形表示是判別可平面圖的最具說服力的方法，但是又因為工作量太大而不實用，要找到一個好的方法來判斷任意一個圖是否是可平面圖，就得對平面圖的本質有所了解，已經分別證明了K5和K3,3是不可平面圖，而它們的任何真子圖卻是可平面圖，波蘭數學家庫拉托夫斯基(Kuratowski，1930)給出了平面圖的一個異常簡單的特性。
細分
設G是一個無自環邊的無向圖，去掉它的一條邊{u，v}，並且用兩條新的邊{u,w}和{w,v}替換它，其中，頂點w不是圖G 的頂點，通過添加每個度為2的一個或多個新的頂點，按照這樣的方法得到的新圖，稱作G 的細分(subdivision)。
顯然，如果一個圖G是可平面圖，那么G的每個細分也是可平面圖；並且如果圖G是不可平面圖，則G的每個細分也是不可平面圖。
庫拉托夫斯基Kuratowski定理
一個圖G是不可平面圖的充分必要條件是G 包含K5或K3,3，或者K5或K3,3的細分作為它的子圖。
由於該定理的證明比較複雜，所以在此省略。
