平面圖及其性質(zhì)課件

5.6.1平面圖及其性質(zhì)

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

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

這些實際問題涉及到平面圖的研究。近年來，由于大規(guī)模集成電路的發(fā)展，也促進(jìn)了平面圖的研究。

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

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

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

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

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

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

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

邊割集：無向圖G去掉幾條邊以后，這個圖的連通分支增加了（即之前一個圖變?yōu)楝F(xiàn)在兩個圖），而這些邊所構(gòu)成的集合稱為邊割集。

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

如圖5.6.3的圖有7個結(jié)點、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個結(jié)點、8條邊，它把12其中，r是G的面數(shù)，e為邊數(shù)。定理5.20

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

這正好是邊數(shù)８的兩倍。

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

v－e＋r＝2歐拉公式

1750年歐拉發(fā)現(xiàn)，任何一個凸多面體的頂點數(shù)v、邊數(shù)e和面數(shù)r之間滿足關(guān)系式

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

（1）證明當(dāng)n取第一個值n0

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

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

對G的邊數(shù)e進(jìn)行歸納。

若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

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

綜合以上，歐拉公式得證。假設(shè)對小于e條邊的所有圖，歐拉公式成立?，F(xiàn)考慮e條邊18定理5.19的推論推論

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

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

e≤3v－6

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

在任何簡單連通平面圖中，至少存在一個其度不超過5的結(jié)點。若全部結(jié)點的度均大于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，則應(yīng)有2v-e=4,但2×6－9＝3，矛盾。

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

雖然歐拉公式可用來判別某個圖是非平面圖，但是當(dāng)結(jié)點數(shù)和邊數(shù)較多時，應(yīng)用歐拉公式進(jìn)行判別就會相當(dāng)困難。

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

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

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

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

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

；R1

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

，deg(R2)=3；R0

的邊界為復(fù)雜回路：v1v2v3v4v5v6v5v4v1，deg(R0)=8。指出下圖所示平面圖的面、面的邊界及面的度數(shù)。例題v1v2v3v4v5v6R1R2R0此平面圖，共有3個29例題R1的邊界:R2的邊界:R3的邊界:R0的邊界:abcefgabcdde,fgdeg(R1)=deg(R2)=deg(R3)=deg(R0)=1328例題R1的邊界:abcefgabcdde,fgdeg(R130

5.6.1平面圖及其性質(zhì)

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

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

這些實際問題涉及到平面圖的研究。近年來，由于大規(guī)模集成電路的發(fā)展，也促進(jìn)了平面圖的研究。

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

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

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

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

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

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

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

邊割集：無向圖G去掉幾條邊以后，這個圖的連通分支增加了（即之前一個圖變?yōu)楝F(xiàn)在兩個圖），而這些邊所構(gòu)成的集合稱為邊割集。

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

如圖5.6.3的圖有7個結(jié)點、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個結(jié)點、8條邊，它把42其中，r是G的面數(shù)，e為邊數(shù)。定理5.20

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

這正好是邊數(shù)８的兩倍。

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

v－e＋r＝2歐拉公式

1750年歐拉發(fā)現(xiàn)，任何一個凸多面體的頂點數(shù)v、邊數(shù)e和面數(shù)r之間滿足關(guān)系式

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

（1）證明當(dāng)n取第一個值n0

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

，k為自然數(shù)）時命題成立，證明當(dāng)n=k+1時命題也成立。綜合（1）（2），對一切自然數(shù)n（n≥n0），命題P(n）都成立。數(shù)學(xué)歸納法第一數(shù)學(xué)歸納法46證明

對G的邊數(shù)e進(jìn)行歸納。

若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。

證明47

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

綜合以上，歐拉公式得證。假設(shè)對小于e條邊的所有圖，歐拉公式成立。現(xiàn)考慮e條邊48定理5.19的推論推論

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

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

e≤3v－6

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

在任何簡單連通平面圖中，至少存在一個其度不超過5的結(jié)點。若全部結(jié)點的度均大于5，則有即3v≤e，再由定理5.21的公51定理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圖K552證明若K3,3是平面圖，則每個面的度為4，因而有4r=2e，即2r=e，代入歐拉公式v－e＋r=2，則應(yīng)有2v-e=4,但2×6－9＝3，矛盾。

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

雖然歐拉公式可用來判別某個圖是非平面圖，但是當(dāng)結(jié)點數(shù)和邊數(shù)較多時，應(yīng)用歐拉公式進(jìn)行判別就會相當(dāng)困難。

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

Kuratowski建立了一個定理，定性地說明了平面圖的本質(zhì)。雖然歐拉公式可用來判別某個圖是非平面圖，