平面图 (图论)

在圖論中，平面圖是可以画在平面上并且使得不同的邊可以互不交疊的圖[1]。而如果一个图无论怎样都无法画在平面上，并使得不同的边互不交叠，那么这样的图不是平面图，或者称为非平面图。完全图K₅和完全二分图K_3,3（湯瑪森圖）是最“小”的非平面图。

几个例子
平面图	非平面图
蝶形图，平面图的一种	K₅不是平面图
一个平面图	K_3,3（湯瑪森圖）不是平面图
K₄ 似乎不是平面圖，但實際上只要把 K₄ 的一條對角線移出去就可以了

一個將平面圖畫在平面上的方法稱為平版圖，又稱為圖的平面嵌入，更精確地說，平版圖包含一個平面圖與一個映射，此映射將平面圖的頂點對應到平面上的一點，邊對應到一條平面曲线段，滿足邊兩端點對應到線段的兩端點，並且線段之間除了在端點之外都不相交。

藉由球极投影可知一個圖可以被嵌入平面若且唯若可以被嵌入球面。圖的球面嵌入在拓樸等價關係中的等價類稱為平面映射。注意到一個平版圖會有外圍面，又稱無界面，但因為平面映射定義是在球面上的等價類，不會有任何一個面有這個特殊的地位。

平面圖可以被視為一個組合映射。

平面圖的條件

库拉托夫斯基定理

1930年，波蘭數學家卡齐米日·库拉托夫斯基提出的一類禁用準則（指滿足某種條件的圖就一定無法具有某個性質）中，包括了平面圖的情況。這個定理現在被稱作库拉托夫斯基定理：

一個简单图是平面圖若且唯若它並不包含一個是 K₅ 或 K_3,3 的分割的子圖[2]。

其中， K₅ 代表有 5 個點的完全圖，K_3,3 代表兩部分各 3 個點的完全二分圖，分割的定義如下。考慮一個作用，將一個邊中間插入一個頂點，如下圖

可以將圖 B 做有限次的上述操作可以得到圖 A，則稱 A 是 B 的細分圖[4]。

用圖的同胚理論來說，就是一個有限圖是平面圖若且唯若這個圖不包含任何同胚於 $K_{5}$ 或 $K_{3,3}$ 的子圖。

這個定理的一般化是羅伯森－西摩定理。

華格納定理

在隨後的1937年，德國數學家克勞斯·華格納提出了類似的禁用定理，華格納定理：

一個简单图是平面圖若且唯若它不是 K₅ 或 K_3,3 的次圖。

其中，一個圖的次圖是將它做有限多次的取子圖(刪除部分頂點和邊)和做邊收縮(將某邊縮成一個頂點)所得到的圖。

平面圖和球面嵌入

說一個圖是平面圖，其實等價於說存在一個從空間到平面的連續的單射，能夠將這個圖投射到平面上。從這樣的角度看來，平面圖是空間的一部份在二維平面上的一個嵌入。然而，圖在二維平面的嵌入和在球面的嵌入是等價的：

能夠畫在平面上的圖，必然也能畫在球面上，使得不同的邊互不交疊，反之亦然。

證明是顯而易見的：首先，如果一個圖是平面圖，那麼將它畫在一張紙上，並在“墨跡未乾”之時將這張紙“拓印”在一個足夠大的球面上（這樣紙基本不會皺）。於是，就得到了一個畫在球面上的同樣的圖。反過來，如果能把一個圖畫在球面上而沒有交互重疊的邊，那麼，把球放在一個無限大平面上，并將球稍作滾動，使得球的最高點不在圖的邊或頂點上。然後，以最高點為中心，把球面（出了最高點）投影在平面上，那麼，得到的平面圖形和原來的圖是一樣的，而且沒有交互重疊的邊，所以原來的圖也是平面圖。

依此準則，空間中的各種凸多面體對應的圖都是平面圖，因為只要在多面體的內部找一個合適的球，然後將多面體的頂點和邊都投影在這個球面上，就完成了相應的圖在球面的嵌入（由於多面體是凸的，投影得到的圖形的邊之間不會交疊）。比如說，所有的正多面體對應的圖都是平面圖[2]。

其他平面性的判別法

實務上，用庫拉托夫斯基定理來判別一個圖的平面性是很費時的。然而，給一個 n 個頂點的圖，目前已經能用 O(n) 的時間(線性時間)來判別該圖是否是平面圖，參見英文維基條目 planarity testing。以下列出了常見的平面性判別法。

惠特尼平面性判別法根據代數對偶的存在性給出了平面性的一個刻劃。
麥克蘭恩平面性判別法根據平面圖的循環空間給出有限平面圖的代數刻劃。
左右平面性判別法根據深度优先搜索樹的 cotree 邊的二部性給出平面圖的一個刻劃，此判別法是左右平面性測試演算法的核心理論。
施尼德定理用偏序集維度表達出一個平面性的刻畫。
科蘭·德·韋迪耶爾平面性測試用圖的哈密頓算符的第二個特徵值的最大重數刻劃平面性。
哈納尼-塔特定理：一個圖是平面圖若且唯若他可以被畫在平面上，使得任兩相異邊交叉偶數次。因此有時可以藉由模 2 簡化平面性系統的研究。

歐拉公式

一個有八個面的平面圖

一個平面圖將平面分成若干個互不相通的封閉區域，以及圖的外部的區域。其中，圖的外面的區域稱為圖的外部面，而圖裏面每個被頂點和邊分割出來的封閉并連通的區域稱為圖的內部面。圍成每個面圖的每個面至少對應著三條邊。

平面圖的頂點個數、邊數和面的個數之間有一個以大數學家萊昂哈德·歐拉命名的公式：

V-E+F=C+1

其中，V是頂點的数目，E是邊的數目，F是面的數目，C是组成圖形的連通部分的數目。當圖是單連通圖的時候，公式簡化為：

V-E+F=2

以前面表格提及的蝶形圖為例，有 V = 5，E = 6，且 F = 3。

若 $G$ 是連通的简单平面圖，則每個面都由至少 3 個邊圍成，且每個邊僅觸及 2 個面，因此有 $3F\leq 2E$ ，代入上式可得

E\leq 3V-6

由此可知，平面圖的邊是很稀疏的。通過討論 $G$ 的各連通部分可知上式對一般的简单平面圖 $G$ 都成立。

事實上，歐拉公式對於空間中的凸多面體也適用，而這並不是巧合。因為凸多面體可以藉由施萊格爾圖的投影方式投影至平面形成一個連通的簡單平面圖，而施萊格爾投影是透視投影，他的透視中心可以選在凸多面體的任一一個面上的點。但並不是所有的連通簡單平面圖都是凸多面體的投影，例如樹即為反例。斯坦尼茨定理表明一個圖是個凸多面體的施萊格爾圖若且唯若它是 3-連通的簡單平面圖。

平均度数

一个多于一条边的连通平面图满足不等式 $2e\geq 3f$ ，因为每个面至少有三条有效边且每条边都肯定分割两个面。结合欧拉公式 $v-e+f=2$ 我们可以得到平面图的平均度数是严格小于6的。如果一个图的度数大于等于6，那么一定不是平面图。

其他相關類型的圖

硬幣圖

圓填裝定理的例子──平面圖 K⁻₅ (K⁻₅是的五顶点的完全图减去一條边)

一個硬幣圖的頂點是由許多圓的圓心組合而成，這些圓兩兩外切或外離，兩頂點之間連邊若且唯若以兩頂點唯圓心的兩圓外切。1936 年，保羅·克伯首次證明填裝球定理：一個圖是平面圖若且唯若它是一個硬幣圖。

法里定理是填裝球定理的一個直接推論，敘述是每個平面圖都可以被畫在平面上，使得各邊對應到不相交的線段。事實上，只要考慮平面圖對應到的硬幣圖，以圓心為頂點，以兩相切的圓的圓心連線段為邊，則所以得邊是不會相交的。

極大平面图

一個簡單圖被稱作是極大平面圖如果他是平面圖而且任加一條邊再不相鄰的頂點上都會得到非平面圖。所以，極大平面圖所有的面，包括外圍面在內，都恰好被三條邊包圍，因此，極大平面圖又被稱為平面三角分割。所有極大平面圖都是3-連通的。

一個包含 v 點的極大平面圖 (v>2) 恰有 3v-6 條邊和 2v-4 個面。

在原本一個大三角形的內部加一個點並與三點連上邊，也就是將大三角形分割成三個小三角形。不斷的重複上述步驟，所得到的圖稱為阿波羅尼奧斯網絡，是極大平面圖的其中一類。事實上，阿波羅尼奧斯網絡是一個平面的3-樹。

所有末梢環都是三角形的圖稱為絞窄圖。因為平面圖的導出環是一個面，所以末梢環也是。於是推得極大平面圖是絞窄圖。

外圍平面圖

外圍平面圖是一個平面圖滿足存在一個畫在平面上的方法使得外圍面的邊界包含所有頂點，該畫法被稱為該圖一個外圍平面嵌入。外圍平面圖一定是平面圖但反過來不一定成立，例如完全圖 K₄ 是平面圖但並非外圍平面圖。庫拉托夫斯基定理友在外圍平面圖上的版本：一個圖是外圍平面圖若且唯若它並不包含一個是 K₄或 K_2,3 的分割的子圖。事實上，該版本是下述事實的直接推論：圖 $G$ 是外圍平面圖若且唯若在 $G$ 外面加一個頂點，連邊到 $G$ 的所有頂點，所得到的圖是平面圖[5]。

圖的 1-外圍平面嵌入是一般的外圍平面嵌入。對所有 k>1，一個圖的平面嵌入是 k-外圍平面嵌入若且唯若將他刪掉外圍面邊界上的所有頂點會形成一個 (k-1)-外圍平面嵌入。一個圖如果有一個 k-外圍平面嵌入則被稱為是一個 k-外圍平面圖。

不環繞嵌入圖

所有圖都可以被嵌入三維空間中使得各邊不交叉，特別的，如果該圖存在一個嵌入額外滿足圖中的兩個互斥環對應到三維空間中的兩個互不環繞的封閉曲線(環繞數為0)，則該圖被稱為是一個不環繞嵌入圖。不環繞嵌入圖可以被看做是平面圖的三維空間版本，所以也有類似華格納定理的禁用結果：一個簡單圖是平面圖若且唯若它不是佩特森圖族中所有的 7 個圖之一的次圖。類似的，平面圖和外圍平面圖分別對應到科蘭·德·韋迪耶爾不變量小於等於 2 和 3 的圖，而環繞嵌入圖對應到科蘭·德·韋迪耶爾不變量小於等於 4 的圖。

哈林圖

哈林圖是一個平面圖，是將一個不包含度數為 2 的頂點的樹的葉子由一個環連結起來所得到的圖。等價的，哈林圖是一個多面體圖滿足有一個面與其他所有的面都相鄰。如同外圍平面圖，哈林圖的樹寬值也很低，因此哈林圖相關的演算法問題會比一般的平面圖來的好處理許多[6]。

其他相關的圖

一個圖是尖點圖如果它可以刪去某一個頂點之後變成平面圖，一個圖是 k-尖點圖如果如果它可以刪去某 k 個頂點之後變成平面圖。

一個圖是1-平面圖如果它可以畫在平面上使得每條邊至多和所有其他邊交叉一次，一個圖是 k-平面圖如果它可以畫在平面上使得每條邊至多和所有其他邊交叉 k 次。

給定一個地圖，滿足上面的各個區域都是單連通且兩兩只在邊界上有交集。將各個區域視為頂點，兩區域的邊界若有交集則連邊，所獲得的圖稱為地圖圖。如果在原地圖上，至多三個區域有共同交集，則定義出來的地圖圖是平面圖，但若存在四個以上的區域相交在同一個點上，在定義出來的地圖圖可能是非平面圖。

一個圖被稱為環面圖如果它可以被嵌入环面使得各邊不交叉。更廣義的來說，一個圖的虧格被定義為所有該圖可以嵌入而邊不交叉的曲面中虧格的最小值。因此，平面圖的虧格為 0 而非平面的環面圖的虧格為 1。

一個向上平面圖是可以被畫在平面上的有向無環圖，使得各個有向邊都是斜向上的。並不是所有平面有向無環圖都是向上平面圖，事實上，決定任意給定有向圖是否為向上平面圖的難度是 NP完全的。

平面圖的數量估計

若將頂點標號，有 n 個頂點的平面圖的數量的漸近式由 $g\cdot n^{-7/2}\cdot \gamma ^{n}\cdot n!$ 給出，其中常數 ${\displaystyle \gamma \approx 27.22687}$ 、 ${\displaystyle g\approx 0.43\times 10^{-5}}$ [7]；若不將頂點標號，有 n 個頂點的平面圖的數量則界在 $2.72^{n}$ 和 $30.06^{n}$ 之間。

幾乎所有的平面圖的自同構數量隨著頂點數的增加呈現指數增長[8]。

其他性質與定義

四色定理敘述說任何平面圖都可以被 4-著色。

法里定理說所有簡單平面圖都從在一種平面嵌入法使得各邊對應到互相不相交的線段，在平面上一個有 n 點地集合被稱為泛頂點集如果所有 n 點的平面圖都可將頂點對應到它們，而且邊是互不相的直線。例如 4 個頂點的泛頂點集是所有滿足其中一個點在另外三個點圍成的三角形的內部。任何外圍平面圖可以被畫在平面上滿足所有頂點在給定的圓上面，所有邊是互不相的直線且都落在圓裡面。

一個平面圖被稱作是凸的如果他可以被畫在平面上，使得各個面，包括外圍面，都是凸多邊形。一個圖是凸平面圖若且唯若它是一個3-連通平面圖的分割。

謝納曼猜想 (現在是定理) 說所有平面圖都可以表示成平面上一些線段的交集圖。

平面圖分離定理說給定任何包含 n 個頂點的平面圖，都可以藉由移除至多 $O({\sqrt {n}})$ 個點來將原圖分開成兩個部分，並且各部份的頂點數不超過 ${\frac {2}{3}}n$ 個。由此可推得平面圖的樹寬值和分支寬值至多 $O({\sqrt {n}})$ 。

存在複雜度為 O(n) 演算法來判斷兩個 n 點的平面圖是否同構，參見圖同構問題[9]。

欧式图是一个以平面上的点以及之间用欧几里得距离的边连接的图。

网格化系数定义为一个平面图的面个数除以 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* 是 Γ* 對應到的多面體圖，其中 Γ* 是 Γ 的對偶多面體。

對偶圖的重要性在於，對偶圖和原圖的性質的關係往往是易於刻劃的，因此，有時研究一個平版圖 (或平面圖) 的對偶圖的性質有助於對原圖的了解。注意到，一個平版圖的對偶圖在拓樸等價下是唯一的，但一個平面圖可能有多種平面嵌入的方式，因此可能會對應到多個不同的對偶圖。

參考來源

Trudeau, Richard J. Corrected, enlarged republication. New York: Dover Pub. 1993: 64 [8 August 2012]. ISBN 978-0-486-67870-2. （原始内容存档于2019-05-05）. Thus a planar graph, when drawn on a flat surface, either has no edge-crossings or can be redrawn without them.
王樹禾. . 科技出版社. 2004. ISBN 9787030124234.
. 教科書. 國立臺灣大學出版中心出版. 2017: 142. ISBN 9789863502586.
演算法觀點的圖論, 2017[3], p.142
Felsner (2004).
Sysło, Maciej M.; Proskurowski, Andrzej, , , Lecture Notes in Mathematics 1018, Springer-Verlag: 248–256, 1983, doi:10.1007/BFb0071635.
Giménez, Omer; Noy, Marc. . Journal of the American Mathematical Society. 2009, 22: 309–329. Bibcode:2009JAMS...22..309G. arXiv:math/0501269. doi:10.1090/s0894-0347-08-00624-3.
McDiarmid, Colin; Steger, Angelika; Welsh, Dominic J.A. . Journal of Combinatorial Theory, Series B: 187–205. doi:10.1016/j.jctb.2004.09.007. 已忽略未知参数|citeseerx= (帮助)
I. S. Filotti, Jack N. Mayer. A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus. Proceedings of the 12th Annual ACM Symposium on Theory of Computing, p.236–243. 1980.

外部連結

Planarity 页面存档备份，存于：通過改變頂點的位置，令圖的邊互不重疊的遊戲

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Trudeau, Richard J. Corrected, enlarged republication. New York: Dover Pub. 1993: 64 [8 August 2012]. ISBN 978-0-486-67870-2. （原始内容存档于2019-05-05）. Thus a planar graph, when drawn on a flat surface, either has no edge-crossings or can be redrawn without them.

[wsh-2] 王樹禾. . 科技出版社. 2004. ISBN 9787030124234.

[book2017演算法觀點的圖論-3] . 教科書. 國立臺灣大學出版中心出版. 2017: 142. ISBN 9789863502586.

[book2017演算法觀點的圖論p142-4] 演算法觀點的圖論, 2017[3], p.142

[5] Felsner (2004).

[6] Sysło, Maciej M.; Proskurowski, Andrzej, , , Lecture Notes in Mathematics 1018, Springer-Verlag: 248–256, 1983, doi:10.1007/BFb0071635.

[7] Giménez, Omer; Noy, Marc. . Journal of the American Mathematical Society. 2009, 22: 309–329. Bibcode:2009JAMS...22..309G. arXiv:math/0501269. doi:10.1090/s0894-0347-08-00624-3.

[8] McDiarmid, Colin; Steger, Angelika; Welsh, Dominic J.A. . Journal of Combinatorial Theory, Series B: 187–205. doi:10.1016/j.jctb.2004.09.007. 已忽略未知参数|citeseerx= (帮助)

[9] I. S. Filotti, Jack N. Mayer. A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus. Proceedings of the 12th Annual ACM Symposium on Theory of Computing, p.236–243. 1980.