查看“︁平面图 (图论)”︁的源代码

{|class="wikitable" align="right"
!colspan="2"|几个例子
|-
! 平面图
! 非平面图
|-
| align="center" | [[Image:Butterfly graph.svg|100px]] <br> [[蝶形图]]，平面图的一种
| align="center" | [[Image:Complete graph K5.svg|100px]] <br>''K''<sub>5</sub>不是平面图
|-
| align="center" | [[File:6n-graf.svg|100px]] <br>一个平面图
| align="center" | [[Image:Complete bipartite graph K3,3.svg|100px]] <br> K<sub>3,3</sub>（[[湯瑪森圖]]）不是平面图
|-
|colspan="2"|<center>[[File:Graf K4 v rovině.svg|200px]]</center> <br> K<sub>4</sub> 似乎不是平面圖，但實際上只要把 K<sub>4</sub> 的一條<br><center>對角線移出去就可以了</center>
|}
在[[圖論]]中，'''平面圖'''是可以画在[[平面 (数学)|平面]]上并且使得不同的邊可以互不交疊的[[圖]]<ref>{{cite book|last=Trudeau|first=Richard J.|title=Introduction to Graph Theory|year=1993|publisher=Dover Pub.|location=New York|isbn=978-0-486-67870-2|pages=64|url=http://store.doverpublications.com/0486678709.html|edition=Corrected, enlarged republication.|accessdate=8 August 2012|quote=Thus a planar graph, when drawn on a flat surface, either has no edge-crossings or can be redrawn without them.|archive-date=2019-05-05|archive-url=https://web.archive.org/web/20190505192352/http://store.doverpublications.com/0486678709.html|dead-url=yes}}</ref>。而如果一个图无论怎样都无法画在平面上，并使得不同的边互不交叠，那么这样的图不是平面图，或者称为非平面图。完全图 K<sub>5</sub>和完全[[二分图]] K<sub>3,3</sub>（[[湯瑪森圖]]）是最“小”的非平面图。

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

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

平面圖可以被視為一個{{Tsl|en|combinatorial map|組合映射}}。

==平面圖的條件==
===库拉托夫斯基定理===
1930年，[[波蘭]][[數學家]][[卡齐米日·库拉托夫斯基]]提出的一類禁用準則（指滿足某種條件的圖就一定無法具有某個性質）中，包括了平面圖的情況。這個定理現在被稱作[[库拉托夫斯基定理]]：<blockquote>一個[[图 (数学)#简单图|简单图]]是平面圖[[若且唯若]]它並不包含一個是 K<sub>5</sub> 或 K<sub>3,3</sub> 的[[分割_(圖論)|分割]]的子圖<ref name="wsh">{{cite book | title =《圖論》| author = 王樹禾 | publisher = 科技出版社 | year =2004 |isbn = 9787030124234 }}</ref>。</blockquote>其中， K<sub>5</sub> 代表有 5 個點的[[完全圖]]，K<sub>3,3</sub> 代表兩部分各 3 個點的[[完全二分圖]]，[[分割_(圖論)|分割]]的定義如下。考慮一個作用，將一個邊中間插入一個頂點，如下圖
{| class="wikitable"
|[[Image:Graph subdivision step1.svg|150px]]
|[[File:Arrow green.svg]]
|[[Image:Graph subdivision step2.svg|150px]]
|}
可以將圖 '''B''' 做有限次的上述操作可以得到圖 '''A'''，則稱 '''A''' 是 '''B''' 的'''細分圖'''{{#tag:ref|演算法觀點的圖論, 2017<ref name="book2017演算法觀點的圖論">{{Cite book
  |title=演算法觀點的圖論
  |isbn=9789863502586
  |series=教科書
  |url=https://books.google.com.tw/books?id=HOlCDwAAQBAJ
  |year=2017
  |publisher=國立臺灣大學出版中心出版
  |page=142
  |access-date=2019-05-10
  |archive-date=2021-04-13
  |archive-url=https://web.archive.org/web/20210413052741/https://books.google.com.tw/books?id=HOlCDwAAQBAJ
  |dead-url=no
  }}</ref>, p.142|name="book2017演算法觀點的圖論p142"}}。

用圖的同胚理論來說，就是一個有限圖是平面圖若且唯若這個圖不包含任何[[同胚 (圖論)|同胚]]於<math>K_5</math>或<math>K_{3,3}</math>的子圖。

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

=== 華格納定理 ===
在隨後的1937年，[[德國]][[數學家]]{{Tsl|en|Klaus Wagner|克勞斯·華格納}}提出了類似的禁用定理，[[瓦格纳定理|華格納定理]]：<blockquote>一個简单图是平面圖若且唯若它不是 K<sub>5</sub> 或 K<sub>3,3</sub> 的[[次圖]]。</blockquote>其中，一個圖的次圖是將它做有限多次的取子圖(刪除部分頂點和邊)和做[[邊收縮]](將某邊縮成一個頂點)所得到的圖。

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

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

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

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

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

* {{Translink|en|Whitney's planarity criterion|惠特尼平面性判別法}}根據代數對偶的存在性給出了平面性的一個刻劃。
* {{Translink|en|Mac Lane planarity criterion|麥克蘭恩平面性判別法}}根據平面圖的{{Translink|en|cycle space|循環空間}}給出有限平面圖的代數刻劃。
* {{Translink|en|Left-right planarity test|左右平面性判別法}}根據[[深度优先搜索]]樹的 cotree 邊的二部性給出平面圖的一個刻劃，此判別法是'''左右平面性測試演算法'''的核心理論。
* {{Translink|en|Schnyder's theorem|施尼德定理}}用{{Translink|en|order dimension|偏序集維度}}表達出一個平面性的刻畫。
* {{Translink|en|Colin de Verdière graph invariant|科蘭·德·韋迪耶爾平面性測試}}用圖的[[哈密頓算符]]的第二個特徵值的最大重數刻劃平面性。
* {{Translink|en|Hanani–Tutte theorem|哈納尼-塔特定理}}：一個圖是平面圖若且唯若他可以被畫在平面上，使得任兩相異邊交叉偶數次。因此有時可以藉由模 2 簡化平面性系統的研究。

==歐拉公式==
{{main|欧拉示性数}}
[[File:Frucht graph.dot.svg|thumb|right|200px|一個有八個面的平面圖]]
一個平面圖將平面分成若干個互不相通的封閉區域，以及圖的外部的區域。其中，圖的外面的區域稱為圖的外部面，而圖裏面每個被頂點和邊分割出來的封閉并連通的區域稱為圖的內部面。圍成每個面圖的每個面至少對應著三條邊。

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

: <math>V - E + F = C+ 1</math>

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

: <math>V - E + F = 2</math>

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

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

: <math>E\leq 3V-6</math>
若<math>G</math>同时不包含任何[[三角形]]，则<math>\deg(f_i)\geq 4</math>，代入上式可得
: <math>E\leq 2V-4</math>

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

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

==平均度数==

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

=== 硬幣圖 ===
[[File:Circle_packing_theorem_K5_minus_edge_example.svg|缩略图|圓填裝定理的例子──平面圖 K<sup>−</sup><sub>5</sub> (K<sup>−</sup><sub>5</sub>是的五[[顶点_(图论)|顶点]]的完全图减去一條边)]]
一個'''硬幣圖'''的頂點是由許多圓的圓心組合而成，這些圓兩兩[[外切]]或[[外離]]，兩頂點之間連邊若且唯若以兩頂點唯圓心的兩圓外切。1936 年，{{Translink|en|Paul Koebe|保羅·克伯}}首次證明{{Translink|en|circle packing theorem|填裝球定理}}：一個圖是平面圖若且唯若它是一個硬幣圖。

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

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

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

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

所有{{Translink|en|peripheral cycle|末梢環}}都是三角形的圖稱為{{Translink|en|Strangulated graph|絞窄圖}}。因為平面圖的[[導出環]]是一個面，所以末梢環也是。於是推得極大平面圖是絞窄圖。

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

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

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

=== 哈林圖 ===
哈林圖是一個平面圖，是將一個不包含[[度數]]為 2 的頂點的樹的葉子由一個環連結起來所得到的圖。等價的，哈林圖是一個[[多面體圖]]滿足有一個面與其他所有的面都相鄰。如同外圍平面圖，哈林圖的{{Translink|en|treewidth|樹寬值}}也很低，因此哈林圖相關的演算法問題會比一般的平面圖來的好處理許多<ref>{{citation|last1=Sysło|first1=Maciej M.|last2=Proskurowski|first2=Andrzej|contribution=On Halin graphs|doi=10.1007/BFb0071635|pages=248–256|publisher=Springer-Verlag|series=Lecture Notes in Mathematics|title=Graph Theory: Proceedings of a Conference held in Lagów, Poland, February 10–13, 1981|volume=1018|year=1983}}.</ref>。

=== 其他相關的圖 ===
一個圖是{{Translink|en|apex graph|尖點圖}}如果它可以刪去某一個頂點之後變成平面圖，一個圖是 k-尖點圖如果如果它可以刪去某 k 個頂點之後變成平面圖。

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

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

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

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

== 平面圖的數量估計 ==
若將頂點標號，有 n 個頂點的平面圖的數量的漸近式由<math>g\cdot n^{-7/2}\cdot \gamma^n\cdot n!</math>給出，其中常數<math>{\displaystyle \gamma \approx 27.22687}</math>、<math>{\displaystyle g\approx 0.43\times 10^{-5}}</math><ref>{{cite journal|title=Asymptotic enumeration and limit laws of planar graphs|url=|first1=Omer|last2=Noy|first2=Marc|journal=Journal of the American Mathematical Society|issue=|doi=10.1090/s0894-0347-08-00624-3|year=2009|volume=22|pages=309–329|arxiv=math/0501269|bibcode=2009JAMS...22..309G|last1=Giménez}}</ref>；若不將頂點標號，有 n 個頂點的平面圖的數量則界在 <math>2.72^n</math>和 <math>30.06^n</math>之間。 

幾乎所有的平面圖的[[自同構]]數量隨著頂點數的增加呈現指數增長<ref>{{cite journal|title=Random planar graphs|url=|first1=Colin|last2=Steger|first2=Angelika|author2-link=Angelika Steger|journal=Journal of Combinatorial Theory, Series B|issue=2|doi=10.1016/j.jctb.2004.09.007|year=|volume=93|pages=187–205|last3=Welsh|first3=Dominic J.A.|last1=McDiarmid|citeseerx=10.1.1.572.857}}</ref>。

== 其他性質與定義 ==
[[四色定理]]敘述說任何平面圖都可以被 4-[[圖著色問題|著色]]。

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

一個平面圖被稱作是''凸'' 的如果他可以被畫在平面上，使得各個面，包括外圍面，都是[[凸多邊形]]。一個圖是凸平面圖若且唯若它是一個{{Translink|en|k-vertex-connected graph|3-連通}}平面圖的分割。

{{Translink|en|Scheinerman's conjecture|謝納曼猜想}} (現在是定理) 說所有平面圖都可以表示成平面上一些[[線段]]的{{Translink|en|intersection graph|交集圖}}。

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

存在複雜度為 O(n) 演算法來判斷兩個 n 點的平面圖是否[[圖同構|同構]]，參見[[圖同構#图同构问题|圖同構問題]]<ref>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&ndash;243. 1980.</ref>。

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

{{Translink|en|Meshedness coefficient|网格化系数}}定义为一个平面图的面个数除以 2n-5 (平面图最大的面数）。所以网格化系数最小是0（树），最大是1。

{{Translink|en|Word-representable graph|单词可表}}平面图包含了一个没有三角形的平面图，更一般的说，是可3着色的平面图。

==對偶圖==
[[Image:dual graphs.svg|thumb|100px|平版圖和它的對偶圖]]
設 G 是一個平版圖，G 不見得是簡單圖，定義 G 的對偶圖 G* 如下述。在 G 中的每個面 (包括外圍面) 取一個點，作為 G* 的頂點，對於 G 中的每個邊 e，畫一條 G* 中的邊 e* 連接與 e 相鄰的兩個面中的頂點，而且 e* 要穿過 e。如果與 e 相鄰的兩面是同一個，則對該面中的點畫一個穿過 e 的[[圖論術語#基本术语|自環]]，如果 G 中兩相鄰面的交界包含多個邊，則 G* 中的兩點之間要連多條邊，如右圖。

此時對偶圖 G* 也是平版圖，而且如果 G 是連通的，則 G** 與 G 在球面上是拓樸等價的，換句話說，他們是相同的平面映射。如果 G 是多面體 Γ 對應到的多面體圖，則 G* 是 Γ* 對應到的多面體圖，其中 Γ* 是 Γ 的對偶多面體。

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

==參考來源==
<references/>
==外部連結==
* [http://www.planarity.net/ Planarity] {{Wayback|url=http://www.planarity.net/ |date=20050731231914 }}：通過改變頂點的位置，令圖的邊互不重疊的遊戲

{{图论}}

[[Category:图]]