平面圖 (圖論)

在圖論中，平面圖是可以畫在平面上並且使得不同的邊可以互不交疊的圖。而如果一個圖無論怎樣都無法畫在平面上，並使得不同的邊互不交疊，那麼這樣的圖不是平面圖，或者稱為非平面圖。完全圖 K5和完全二分圖 K3,3是最“小”的非平面圖。一個將平面圖畫在平面上的方法稱為平版圖，又稱為圖的平面嵌入，更精確地說，平版圖包含一個平面圖與一個對映，此對映將平面圖的頂點對應到平面上的一點，邊對應到一條平面曲線段，滿足邊兩端點對應到線段的兩端點，並且線段之間除了在端點之外都不相交。藉由球極投影可知一個圖可以被嵌入平面若且唯若可以被嵌入球面。圖的球面嵌入在關係中的等價類稱為平面對映。注意到一個平版圖會有外圍面，又稱無介面，但因為平面對映定義是在球面上的等價類，不會有任何一個面有這個特殊的地位。平面圖可以被視為一個。平面圖的條件.庫拉托夫斯基定理.1930年，波蘭數學家卡齊米日·庫拉托夫斯基提出的一類禁用準則中，包括了平面圖的情況。這個定理現在被稱作庫拉托夫斯基定理：一個簡單圖是平面圖若且唯若它並不包含一個是 K5 或 K3,3 的分割的子圖。其中， K5 代表有 5 個點的完全圖，K3,3 代表兩部分各 3 個點的完全二分圖，分割的定義如下。考慮一個作用，將一個邊中間插入一個頂點，如下圖可以將圖 B 做有限次的上述操作可以得到圖 A，則稱 A 是 B 的細分圖。用圖的同胚理論來說，就是一個有限圖是平面圖若且唯若這個圖不包含任何同胚於formula_1或formula_2的子圖。這個定理的一般化是羅伯森－西摩定理。華格納定理.在隨後的1937年，德國數學家提出了類似的禁用定理，華格納定理：一個簡單圖是平面圖若且唯若它不是 K5 或 K3,3 的次圖。其中，一個圖的次圖是將它做有限多次的取子圖(刪除部分頂點和邊)和做(將某邊縮成一個頂點)所得到的圖。平面圖和球面嵌入.說一個圖是平面圖，其實等價於說存在一個從空間到平面的連續的單射，能夠將這個圖投射到平面上。從這樣的角度看來，平面圖是空間的一部份在二維平面上的一個嵌入。然而，圖在二維平面的嵌入和在球面的嵌入是等價的：能夠畫在平面上的圖，必然也能畫在球面上，使得不同的邊互不交疊，反之亦然。證明是顯而易見的：首先，如果一個圖是平面圖，那麼將它畫在一張紙上，並在“墨跡未乾”之時將這張紙“拓印”在一個足夠大的球面上投影在平面上，那麼，得到的平面圖形和原來的圖是一樣的，而且沒有互動重疊的邊，所以原來的圖也是平面圖。依此準則，空間中的各種凸多面體對應的圖都是平面圖，因為只要在多面體的內部找一個合適的球，然後將多面體的頂點和邊都投影在這個球面上，就完成了相應的圖在球面的嵌入。比如說，所有的正多面體對應的圖都是平面圖。其他平面性的判別法.實務上，用庫拉托夫斯基定理來判別一個圖的平面性是很費時的。然而，給一個 n 個頂點的圖，目前已經能用 O(n) 的時間(線性時間)來判別該圖是否是平面圖，文維基條目 。以下列出了常見的平面性判別法。尤拉公式.一個平面圖將平面分成若干個互不相通的封閉區域，以及圖的外部的區域。其中，圖的外面的區域稱為圖的外部面，而圖裡面每個被頂點和邊分割出來的封閉並連通的區域稱為圖的內部面。圍成每個面圖的每個面至少對應著三條邊。平面圖的頂點個數、邊數和麵的個數之間有一個以大數學家萊昂哈德·尤拉命名的公式：formula_3其中，V是頂點的數目，E是邊的數目，F是面的數目，C是組成圖形的連通部分的數目。當圖是單連通圖的時候，公式簡化為：formula_4以前面表格提及的蝶形圖為例，有 V = 5，E = 6，且 F = 3。若 formula_5是連通的簡單平面圖，則每個面都由至少 3 個邊圍成，且每個邊僅觸及 2 個面，因此有 formula_6，代入上式可得formula_7由此可知，平面圖的邊是很"稀疏" 的。透過討論 formula_5的各連通部分可知上式對一般的簡單平面圖 formula_5都成立。事實上，尤拉公式對於空間中的凸多面體也適用，而這並不是巧合。因為凸多面體可以藉由的投影方式投影至平面形成一個連通的簡單平面圖，而施萊格爾投影是透視投影，他的透視中心可以選在凸多面體的任一一個面上的點。但並不是所有的連通簡單平面圖都是凸多面體的投影，例如樹即為反例。表明一個圖是個凸多面體的施萊格爾圖若且唯若它是 3-連通的簡單平面圖。平均度數.一個多於一條邊的連通平面圖滿足不等式 formula_10，因為每個面至少有三條有效邊且每條邊都肯定分割兩個面。結合尤拉公式 formula_11 我們可以得到平面圖的平均度數是嚴格小於6的。如果一個圖的度數大於等於6，那麼一定不是平面圖。其他相關型別的圖.硬幣圖.一個硬幣圖的頂點是由許多圓的圓心組合而成，這些圓兩兩外切或外離，兩頂點之間連邊若且唯若以兩頂點唯圓心的兩圓外切。1936 年，首次證明：一個圖是平面圖若且唯若它是一個硬幣圖。是的一個直接推論，敘述是每個平面圖都可以被畫在平面上，使得各邊對應到不相交的線段。事實上，只要考慮平面圖對應到的硬幣圖，以圓心為頂點，以兩相切的圓的圓心連線段為邊，則所以得邊是不會相交的。極大平面圖.一個簡單圖被稱作是極大平面圖如果他是平面圖而且任加一條邊再不相鄰的頂點上都會得到非平面圖。所以，極大平面圖所有的面，包括外圍面在內，都恰好被三條邊包圍，因此，極大平面圖又被稱為平面三角分割。所有極大平面圖都是的。一個包含 v 點的極大平面圖 (v&gt;2) 恰有 3v-6 條邊和 2v-4 個面。在原本一個大三角形的內部加一個點並與三點連上邊，也就是將大三角形分割成三個小三角形。不斷的重複上述步驟，所得到的圖稱為，是極大平面圖的其中一類。事實上，阿波羅尼奧斯網路是一個平面的。所有都是三角形的圖稱為。因為平面圖的匯出環是一個面，所以末梢環也是。於是推得極大平面圖是絞窄圖。外圍平面圖.外圍平面圖是一個平面圖滿足存在一個畫在平面上的方法使得外圍面的邊界包含所有頂點，該畫法被稱為該圖一個外圍平面嵌入。外圍平面圖一定是平面圖但反過來不一定成立，例如完全圖 K4 是平面圖但並非外圍平面圖。庫拉托夫斯基定理友在外圍平面圖上的版本：一個圖是外圍平面圖若且唯若它並不包含一個是 K4或 K2,3 的分割的子圖。事實上，該版本是下述事實的直接推論：圖formula_5是外圍平面圖若且唯若在formula_5外面加一個頂點，連邊到formula_5的所有頂點，所得到的圖是平面圖。圖的 1-外圍平面嵌入是一般的外圍平面嵌入。對所有 k&gt;1，一個圖的平面嵌入是 k-外圍平面嵌入若且唯若將他刪掉外圍面邊界上的所有頂點會形成一個 (k-1)-外圍平面嵌入。一個圖如果有一個 k-外圍平面嵌入則被稱為是一個 k-外圍平面圖。不環繞嵌入圖.所有圖都可以被嵌入三維空間中使得各邊不交叉，特別的，如果該圖存在一個嵌入額外滿足圖中的兩個互斥環對應到三維空間中的兩個互不環繞的封閉曲線(環繞數為0)，則該圖被稱為是一個。不環繞嵌入圖可以被看做是平面圖的三維空間版本，所以也有類似華格納定理的禁用結果：一個簡單圖是平面圖若且唯若它不是中所有的 7 個圖之一的次圖。類似的，平面圖和外圍平面圖分別對應到小於等於 2 和 3 的圖，而環繞嵌入圖對應到科蘭·德·韋迪耶爾不變數小於等於 4 的圖。哈林圖.哈林圖是一個平面圖，是將一個不包含度數為 2 的頂點的樹的葉子由一個環連結起來所得到的圖。等價的，哈林圖是一個滿足有一個面與其他所有的面都相鄰。如同外圍平面圖，哈林圖的也很低，因此哈林圖相關的演演算法問題會比一般的平面圖來的好處理許多。其他相關的圖.一個圖是如果它可以刪去某一個頂點之後變成平面圖，一個圖是 k-尖點圖如果如果它可以刪去某 k 個頂點之後變成平面圖。一個圖是如果它可以畫在平面上使得每條邊至多和所有其他邊交叉一次，一個圖是 k-平面圖如果它可以畫在平面上使得每條邊至多和所有其他邊交叉 k 次。給定一個地圖，滿足上面的各個區域都是單連通且兩兩只在邊界上有交集。將各個區域視為頂點，兩區域的邊界若有交集則連邊，所獲得的圖稱為。如果在原地圖上，至多三個區域有共同交集，則定義出來的地圖圖是平面圖，但若存在四個以上的區域相交在同一個點上，在定義出來的地圖圖可能是非平面圖。一個圖被稱為如果它可以被嵌入環面使得各邊不交叉。更廣義的來說，一個圖的虧格被定義為所有該圖可以嵌入而邊不交叉的曲面中虧格的最小值。因此，平面圖的虧格為 0 而非平面的環面圖的虧格為 1。一個是可以被畫在平面上的有向無環圖，使得各個有向邊都是斜向上的。並不是所有平面有向無環圖都是向上平面圖，事實上，決定任意給定有向圖是否為向上平面圖的難度是 NP完全的。平面圖的數量估計.若將頂點標號，有 n 個頂點的平面圖的數量的漸近式由formula_15給出，其中常數formula_16、formula_17；若不將頂點標號，有 n 個頂點的平面圖的數量則界在 formula_18和 formula_19之間。幾乎所有的平面圖的自同構數量隨著頂點數的增加呈現指數增長。其他性質與定義.四色定理敘述說任何平面圖都可以被 4-著色。說所有簡單平面圖都從在一種平面嵌入法使得各邊對應到互相不相交的線段，在平面上一個有 n 點地集合被稱為如果所有 n 點的平面圖都可將頂點對應到它們，而且邊是互不相的直線。例如 4 個頂點的泛頂點集是所有滿足其中一個點在另外三個點圍成的三角形的內部。任何外圍平面圖可以被畫在平面上滿足所有頂點在給定的圓上面，所有邊是互不相的直線且都落在圓裡面。一個平面圖被稱作是"凸" 的如果他可以被畫在平面上，使得各個面，包括外圍面，都是凸多邊形。一個圖是凸平面圖若且唯若它是一個平面圖的分割。(現在是定理) 說所有平面圖都可以表示成平面上一些線段的。說給定任何包含 n 個頂點的平面圖，都可以藉由移除至多 formula_20個點來將原圖分開成兩個部分，並且各部份的頂點數不超過 formula_21個。由此可推得平面圖的和至多 formula_20。存在複雜度為 O(n) 演演算法來判斷兩個 n 點的平面圖是否同構，同構問題。歐式圖是一個以平面上的點以及之間用歐幾里得距離的邊連線的圖。定義為一個平面圖的面個數除以 2n-5 (平面圖最大的面數）。所以網格化係數最小是0，最大是1。平面圖包含了一個沒有三角形的平面圖，更一般的說，是可3著色的平面圖。對偶圖.設 G 是一個平版圖，G 不見得是簡單圖，定義 G 的對偶圖 G* 如下述。在 G 中的每個面 (包括外圍面) 取一個點，作為 G* 的頂點，對於 G 中的每個邊 e，畫一條 G* 中的邊 e* 連線與 e 相鄰的兩個面中的頂點，而且 e* 要穿過 e。如果與 e 相鄰的兩面是同一個，則對該面中的點畫一個穿過 e 的自環，如果 G 中兩相鄰面的交界包含多個邊，則 G* 中的兩點之間要連多條邊，如右圖。此時對偶圖 G* 也是平版圖，而且如果 G 是連通的，則 G** 與 G 在球面上是拓樸等價的，換句話說，他們是相同的平面對映。如果 G 是多面體 Γ 對應到的多面體圖，則 G* 是 Γ* 對應到的多面體圖，其中 Γ* 是 Γ 的對偶多面體。對偶圖的重要性在於，對偶圖和原圖的性質的關係往往是易於刻劃的，因此，有時研究一個平版圖 (或平面圖) 的對偶圖的性質有助於對原圖的瞭解。注意到，一個平版圖的對偶圖在拓樸等價下是唯一的，但一個平面圖可能有多種平面嵌入的方式，因此可能會對應到多個不同的對偶圖。