5.6.1平面圖及其性質

5.6.1平面圖及其性質基本內容平面圖的相關概念歐拉公式Kuratowski(庫拉托夫斯基)定理基本內容平面圖的相關概念2平面圖的定義先從一個簡單的例子談起。一個工廠有3個車間和3個倉庫。為了工作需要，車間與倉庫之間將設專用的車道。為避免發生車禍，應盡量減少車道的交叉點，最好是沒有交叉點，這是否可能？平面圖的定義先從一個簡單的例子談起。一個工廠有33

如圖5.6.1（a）所示，A，B，Ｃ是3個車間，M，Ｎ，P是3座倉庫。經過努力表明，要想建造不相交的道路是不可能的，但可以使交叉點最少（如圖5.6.1（b））。1圖5.6.1如圖5.6.1（a）所示，A，B，Ｃ是3個車間，M，4引入

這些實際問題涉及到平面圖的研究。近年來，由于大規模集成電路的發展，也促進了平面圖的研究。

例如在電路設計中常常要考慮布線是否可以避免交叉以減少元件間的互感影響。如果必然交叉，那么怎樣才能使交叉處盡可能少？或者如何進行分層設計，才使每層都無交叉？引入這些實際問題涉及到平面圖的研究。近年來，由于大規5平面圖的定義定義5.30

若簡單圖G=<V,E>的圖形在平面上能畫成如下形式：（1）沒有兩個結點重合；（2）除結點外每條邊不相交，則稱G是具有平面性的圖，或簡稱為平面圖（PlanarGraph）。平面圖的定義定義5.306示例例如

下圖（1）~（4）是平面圖，（5）不是平面圖。對于平面圖G的定義，通俗的來說，就是能夠把G的所有結點和邊畫在平面上，且使得任何兩條邊除了端點外沒有其他的交點。示例例如對于平面圖G的定義，通俗的來說，就是7

應當注意，有些圖從表面上看，它的某些邊是相交的，但是不能就此肯定它不是平面圖。如圖5.6.2(a)表面上看有幾條邊相交，但是把它畫成圖5.6.2(b)，則可以看出它是一個平面圖。圖5.6.2平面圖示例應當注意，有些圖從表面上看，它的某些邊是相交的，但是8平面圖的特點定義5.31

設G是一個平面圖.若G的圖形中由邊圍成的封閉區域不能再分割成兩個或兩個以上的包含更少邊數的子區域，則稱這個區域為G的面（Face），包圍這個區域的邊稱為面的邊界(Bound)，其中有一個面的區域為這個平面圖的外部邊界組成，這個面稱為外部面或無限面(ExteriorFace)。面的邊界中的邊數稱為面的度（Degree）（割邊在計算時算作兩條邊！），面R的度數記為deg(R)。平面圖的特點定義5.319面

面的概念也可以用下面形象的說法加以描述：假設把一個平面圖畫在平面上，然后用一把小刀，沿著圖的邊切開，那么平面就被切成許多塊，每一塊就是圖的一個面。

更確切地說，平面圖的一個面就是平面的一塊，它用邊作邊界線，且不能再分成更小的塊。面面的概念也可以用下面形象的說法加以描述：假設把一10割邊及與割邊相關的概念對邊割集和割邊通俗的理解：

邊割集：無向圖G去掉幾條邊以后，這個圖的連通分支增加了（即之前一個圖變為現在兩個圖），而這些邊所構成的集合稱為邊割集。

割邊：邊割集中只有一條邊，這條邊就稱為割邊。割邊只能是一個面的邊界！若一條邊不是割邊，它必是兩個面的公共邊界；兩個以一條邊為公共邊界的面稱為相鄰的面。割邊及與割邊相關的概念對邊割集和割邊通俗的理解：11示例解析

如圖5.6.3的圖有7個結點、8條邊，它把平面分成三個面：R1，R2，R3。其中：R1由回路v1v2v3v4v5v6v5v4v1所圍，R2由回路v1v4v7v1

所圍，而R3在圖形之外，稱為無限面（外部面），它由回路v1v2v3v4v7v1所圍，所以

deg(R1)=8，deg(R2)=3，deg(R3)=5。

圖5.6.3有限面和無限面（外部面）示例示例解析如圖5.6.3的圖有7個結點、8條邊，它把12其中，r是G的面數，e為邊數。定理5.20

一個有限平面圖，其面的度之和等于其邊數的兩倍，即定理5.20其中，r是G的面數，e為邊數。定理5.20定理5.2013定理5.20證明例如在圖5.6.3中,

這正好是邊數８的兩倍。

因任何一條邊，或者是兩個面的公共邊，或者是在一個面中作為邊界被重復計算兩次。故面的次數之和等于其邊數的兩倍。定理5.20證明例如在圖5.6.3中,這正好是邊數８的兩14歐拉公式定理5.19設連通平面圖G=<V,E>的頂點數，邊數和面數分別為v,e和r則有歐拉公式

v－e＋r＝2歐拉公式

1750年歐拉發現，任何一個凸多面體的頂點數v、邊數e和面數r之間滿足關系式

v－e＋r=2這就是著名的歐拉公式。這個結論也可以推廣到平面圖上來。歐拉公式定理5.19歐拉公式15數學歸納法第一數學歸納法一般地，證明一個與自然數n有關的命題P(n），有如下步驟：

（1）證明當n取第一個值n0

時命題成立。n0對于一般數列取值為0或1，但也有特殊情況；（2）假設當n=k（k≥n0

，k為自然數）時命題成立，證明當n=k+1時命題也成立。綜合（1）（2），對一切自然數n（n≥n0），命題P(n）都成立。數學歸納法第一數學歸納法16證明

對G的邊數e進行歸納。

若e=0，由于G是連通圖，故必有v＝1。這時只有一個無限面，即r＝1。所以有v－e＋r＝2。

若e=1，這時有兩種情況：

1)該邊是自回路，則有v＝1,r＝2。

所以v－e＋r＝1－1＋2＝2。

2)該邊不是自回路，則有n＝2，r＝1。所以v－e＋r＝2－1＋1＝2。

證明17

假設對小于e條邊的所有圖，歐拉公式成立。現考慮e條邊的圖G，設它有v個結點。增加一條邊，為使圖連通，這時只有如下兩種情況：(1)該邊的一端是懸掛點(以該點為端點的邊數為1的點)，這時增加了一個頂點和一條邊，面數不變，滿足歐拉公式，即（v+1）-（e+1）+r=v-e+r=2;(2)該邊的兩端為原圖的兩個頂點，這時頂點數不增加，但增加了一條邊和一個面，所以也滿足歐拉公式，即v-(e+1)+(r+1)=v-e+r=2;

綜合以上，歐拉公式得證。假設對小于e條邊的所有圖，歐拉公式成立。現考慮e條邊18定理5.19的推論推論

設平面圖G=<V,E>有k個連通分支，它的頂點數，邊數和面數分別為v,e和r，則有v-e+r=k+1.定理5.19的推論推論19定理5.21定理5.21

設G是一個階數（結點數）大于2的簡單連通平面圖，頂點數和邊數分別為v，e，則有

e≤3v－6

設G有r個面，因為每個面至少由3條邊圍成，所以G的各面的度之和為由定理5.20可知代入歐拉公式v－e＋r=2消去r，可得定理5.21定理5.21設G是一個階數（結點數）大于220若全部結點的度均大于5，則有即3v≤e，再由定理5.21的公式e≤3v－6可得3v≤3v－6，矛盾。定理5.21推論推論

在任何簡單連通平面圖中，至少存在一個其度不超過5的結點。若全部結點的度均大于5，則有即3v≤e，再由定理5.21的公21定理5.22定理5.22

K5和K3，3都是非平面圖圖5.6.4圖K5K5如圖5.6.4，這里v＝5，e＝10，而3v－6=3×5－6＝9≤10，所以K5不是平面圖。定理5.22定理5.22圖5.6.4圖K522證明若K3,3是平面圖，則每個面的度為4，因而有4r=2e，即2r=e，代入歐拉公式v－e＋r=2，則應有2v-e=4,但2×6－9＝3，矛盾。

故K3,3不是平面圖。證明若K3,3是平面圖，則每個面的度為4，因而有4r23

雖然歐拉公式可用來判別某個圖是非平面圖，但是當結點數和邊數較多時，應用歐拉公式進行判別就會相當困難。

一個圖是否有平面的圖形表示是判別平面圖的最具說服力的方法，但是又因為工作量太大而不實用。要找到一個好的方法去判斷任何一個圖是否是平面圖，就得對平面圖的本質有所了解。

Kuratowski建立了一個定理，定性地說明了平面圖的本質。雖然歐拉公式可用來判別某個圖是非平面圖，但是當結點24細分圖

首先，在圖G的邊(u,v)上新增加一個2度結點w，稱為圖G的細分。

嚴格的說，細分是從G中先刪去邊(u,v),再增加一個新結點w及邊(u,w)和邊(v,w)。一條邊上也可以同時增加有限個2度結點，所得的新圖稱為原圖的細分圖。細分圖首先，在圖G的邊(u,v)上新增加一個2度結點25細分圖示例

例如，在圖5.23中(b)是(a)的一種細分圖，(d)是(c)的一種細分圖。容易知道，若G1是G的細分圖，則G1與G同為平面圖或非平面圖細分圖示例例如，在圖5.23中(b)是(a)的一種細26Kuratowski定理定理5.23（Kuratowski定理）一個圖是平面圖當且僅當它不包含與K3,3或K5的細分圖同構的子圖。Kuratowski定理定理5.23（Kuratowski27例5.7例5.7證明圖（a）（Petersen圖）不是平面圖。證明：刪去Petersen圖（a）中的結點b,得其細分圖(b)H.而圖（b）H的細分圖（去掉2度結點a，c，g）與K3.3同構，由庫拉托夫斯基定理可得Petersen圖不是平面圖.例5.7例5.7證明圖（a）（Petersen圖）不是平面28例題v1v2v3v4v5v6R1R2R0此平面圖，共有3個面：R0,R1,R2

；R1

的邊界：v1v3v4v1，deg(R1)=3；R2的邊界：v1v2v3v1

，deg(R2)=3；R0

的邊界為