平面图 (图论)

维基百科,自由的百科全书
跳转至: 导航搜索
几个例子
平面图 非平面图
Butterfly graph.svg
蝶形图,平面图的一种
Complete graph K5.svg
K5不是平面图
6n-graf.svg
一个平面图
Complete bipartite graph K3,3.svg
K3,3不是平面图
Graf K4 v rovině.svg

K4似乎不是平面圖,但實際上只要把K4的一條
對角線移出去就可以了

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

平面圖的條件[编辑]

库拉托夫斯基定理[编辑]

波蘭數學家卡齐米日·库拉托夫斯基提出的一類禁忌準則(指滿足某種條件的圖就一定無法具有某個性質)中,也包括了平面圖的情況。他提出的一個定理說明:

一個有限圖(頂點數和邊數有限的圖)是平面圖若且唯若它並不包含一個是K_5(有五個頂點的完全圖)或K_{3,3}(三個頂點的二部圖)的分割的子圖[1]

其中,一個圖A是另一個圖B分割是指:A是在B的基礎上,在某些邊的中間加上頂點:

Graph subdivision step1.svg Arrow green.svg Graph subdivision step2.svg

而得到的新的圖。

用圖的同胚理論來說,就是:一個有限圖是平面圖當且僅當這個圖不包含任何同胚K_5K_{3,3}的子圖。

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

平面圖和球面嵌入[编辑]

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

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

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

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

歐拉公式[编辑]

一個有八個面的平面圖

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

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

V - E + F = C+ 1

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

V - E + F = 2

對偶圖[编辑]

參考來源[编辑]

  1. ^ 1.0 1.1 王樹禾. 《圖論》. 科技出版社. 2004. ISBN 9787030124234. 

外部連結[编辑]

  • Planarity:通過改變頂點的位置,令圖的邊互不重疊的遊戲