平面圖的概念與性質

數學與統計學院應用數學系

張欣平面圖的概念與性質

數學與統計學院應用數學系

張欣圖的平面性問題是圖論典型問題之一。生活中許多問題都與該問題有關。(一)、平面圖的概念

例子1：電路板設計問題在電路板設計時，需要考慮的問題之一是連接電路元件間的導線間不能交叉。否則，當絕緣層破損時，會出現短路故障。

顯然，電路板可以模型為一個圖，“要求電路元件間連接導線互不交叉”，對應于“要求圖中的邊不能相互交叉”。圖的平面性問題是圖論典型問題之一。生活中許多問題都與該問

例子2：空調管道的設計某娛樂中心有6個景點，位置分布如下圖。A1A4A5A3A2A6分析者認為：(1)A1與A4,(2)A2與A5,(3)A3與A6間人流較少，無需鋪設空調管道；其它景點之間人流量大，必須投資鋪設空調管道，但要求空調管道間不能交叉。如何設計？例子2：空調管道的設計某娛樂中心有6個景如果把每個景點分別模型為一個點，景點間連線，當且僅當兩景點間要鋪設空調管道。那么，上面問題直接對應的圖為：A6A5A4A3A2A1于是，問題轉化為：能否把上圖畫在平面上，使得邊不會相互交叉？如果把每個景點分別模型為一個點，景點間連線，當且僅當兩景通過嘗試，可以把上圖畫為：于是，鋪設方案為：A6A5A4A3A2A1A1A4A5A3A2A6通過嘗試，可以把上圖畫為：于是，鋪設方案為：A6A5問題：要求把3種公用設施(煤氣，水和電)分別用煤氣管道、水管和電線連接到3間房子里，要求任何一根線或管道不與另外的線或管道相交，能否辦到？

例子3：3間房子和3種設施問題上面問題可以模型為如下圖：H3H2H1EWG問題轉化為，能否把上圖畫在平面上，使得邊與邊之間不會交叉？問題：要求把3種公用設施(煤氣，水和電)分別用煤氣管道、上面的例子都涉及同一個圖論問題：能否把一個圖畫在平面上，使得邊與邊之間沒有交叉？針對這一問題，我們引入如下概念定義1如果能把圖G畫在平面上，使得除頂點外，邊與邊之間沒有交叉，稱G可以嵌入平面，或稱G是可平面圖。可平面圖G的邊不交叉的一種畫法，稱為G的一種平面嵌入，G的平面嵌入表示的圖稱為平面圖。H3H2H1EWG圖GH3H2H1EWG圖G的平面嵌入上面的例子都涉及同一個圖論問題：能否把一個圖畫在平面上，注:

(1)可平面圖概念和平面圖概念有時可以等同看待；

(2)圖的平面性問題主要涉及如下幾個方面：1)平面圖的性質；2)平面圖的判定；3)平面嵌入方法(平面性算法);4）涉及圖的平面性問題的拓撲不變量。由圖的平面性問題研究引申出圖的一般嵌入性問題的研究，形成了拓撲圖論的主要內容。歷史上，波蘭數學家庫拉托斯基、美國數學家惠特尼、生于英國的加拿大數學家托特，我國數學家吳文俊等都在拓撲圖論中有過精湛的研究。注:(2)圖的平面性問題主要涉及如下幾個方面：1)平(二)、平面圖性質定義2

（1）一個平面圖G把平面分成若干連續的部分，這些連續的部分稱為G的區域，或G的一個面。G的面組成的集合用Φ表示。在上圖G中，共有4個面。其中f4是外部面，其余是內部面。Φ=｛f1,f2,f3,f4｝。平面圖Gf1f3f2f4（2）面積有限的區域稱為平面圖G的內部面，否則稱為G的外部面。(二)、平面圖性質定義2（1）一個平面圖G把平面分成若（3）在G中，頂點和邊都與某個給定區域關聯的子圖，稱為該面的邊界。某面f的邊界中含有的邊數(割邊計算2次)稱為該面f的度數,記為deg(f)。平面圖Gf1f3f2f4在上圖中，綠色邊在G中的導出子圖為面f3的邊界。

1、平面圖的度數公式（3）在G中，頂點和邊都與某個給定區域關聯的子圖，稱定理1

設G=(n,m)是平面圖，則：證明：對G的任意一條邊e,如果e是某面割邊，那么由面的次數定義，該邊給G的總次數貢獻2次；如果e不是割邊，那么，它必然是兩個面的公共邊，因此，由面的次數定義，它也給總次數貢獻2次。于是有：

2、平面圖的歐拉公式定理1設G=(n,m)是平面圖，則：證明：對G的任意一定理2(歐拉公式)

設G=(n,m)是連通平面圖，ф是G的面數，則：證明：情形1，如果G是樹，那么m=n-1,ф=1。在這種情況下，容易驗證，定理中的恒等式是成立的。情形2，G不是樹的連通平面圖。假設在這種情形下，歐拉恒等式不成立。則存在一個含有最少邊數的連通平面圖G,使得它不滿足歐拉恒等式。設這個最少邊數連通平面圖G=(n,m),面數為ф，則：定理2(歐拉公式)設G=(n,m)是連通平面圖，ф是G因為G不是樹，所以存在非割邊e。顯然，G-e是連通平面圖，邊數為m-1,頂點數為n,面數為ф-1。由最少性假設，G-e滿足歐拉等式：化簡得：這是一個矛盾。

注：該定理也可以采用對面數ф作數學歸納證明。

3、歐拉公式的幾個有用推論因為G不是樹，所以存在非割邊e。顯然，G-e是連通平面圖推論1

設G是具有ф個面k個連通分支的平面圖，則：證明：對第i個分支來說，設頂點數為ni，邊數為mi，面數為фi,由歐拉公式：所以，推論1設G是具有ф個面k個連通分支的平面圖，則：證明：對而：所以得：推論2

設G是具有n個點m條邊ф個面的連通平面圖，如果對G的每個面f,有：deg(f)≥l≥3,則：而：所以得：推論2設G是具有n個點m條邊證明：一方面，由次數公式得：另一方面，由歐拉公式得：所以有：整理得：證明：一方面，由次數公式得：另一方面，由歐拉公式得注:(1)

上面推論2也可以敘述為：設G=(n,m)是連通圖，如果：則G是非可平面圖。

(2)推論2的條件是G是平面圖的必要條件,不是充分條件。

例1

求證：K3,3是非可平面圖。證明：注意到，K3,3是二分圖，不存在奇圈，所以，每個面的次數至少是4,即l=4注:(1)上面推論2也可以敘述為：設G=(n,m所以，而m=9，這樣有：所以，由推論2，K3,3是非平面圖。推論3設G是具有n個點m條邊ф個面的簡單平面圖，則：所以，而m=9，這樣有：所以，由推論2，K3,證明：情形1，G連通。因為G是簡單圖，所以每個面的次數至少為3，即l=3。于是，由推論2得：情形2，若G不連通。設G1,G2,…,Gk是連通分支。一方面,由推論1：另一方面，由次數公式得：所以得：證明：情形1，G連通。因為G是簡單圖，所以

例2證明：K5是非可平面圖。

證明：K5是簡單圖，m=10,n=5。3n-6=9。得，