第一節(jié) 平面圖

1、第四章 平面圖第一節(jié) 平面圖定義1 如果圖G能示畫在曲面S上且使得它的邊僅在端點(diǎn)處相交，則稱G可嵌入曲面S。如果G可嵌入平面上，則稱G是可平面圖，已經(jīng)嵌入平面上的圖 稱為G的平面表示。 可平面圖G與G的平面表示 同構(gòu)，都簡稱為(球極投影)1定理1 圖G可嵌入球面圖G可嵌入平面。例1 Q3是否可平面性？2定義2 (平面圖的面,邊界和度數(shù)). 設(shè)G是一個(gè)平面圖，由G中的邊所包圍的區(qū)域，在區(qū)域內(nèi)既不包含G的結(jié)點(diǎn)，也不包含G的邊，這樣的區(qū)域稱為G的一個(gè)面。有界區(qū)域稱為內(nèi)部面，無界區(qū)域稱為外部面。包圍面的長度最短的閉鏈稱為該面的邊界。面的邊界的長度稱為該面的度數(shù)。3例2 指出下圖所示平面圖的面、面的邊界

2、及面的度數(shù)。1234567e6e1e2e3e4e5e7e8e10e9f1f4f3f2f54解:面f1,其邊界1e15e24e43e72e101,d(f1)=5. 面f2,其邊界1e102e87e91,d(f2)=3. 面f3,其邊界2e73e67e82,d(f3)=3. 面f4,其邊界3e44e57e63,d(f4)=3. 外部面f5, 其邊界1e15e24e36e34 e57e91,d(f5)=6.5定理2 對任何平面圖G，面的度數(shù)之和是邊數(shù)的二倍。證明:對內(nèi)部面而言,因?yàn)槠淙魏我粭l非割邊同時(shí)在兩個(gè)面中,故每增加一條邊圖的度數(shù)必增加2.對外部面的邊界,若某條邊不同時(shí)在兩個(gè)面中, 邊必為割邊,

3、由于邊界是閉鏈,則該邊也為圖的度數(shù)貢獻(xiàn)2.從而結(jié)論成立.定理3 設(shè)G是帶v個(gè)頂點(diǎn)，e條邊，r個(gè)面的連通的平面圖，則 v-e+r=2。（歐拉公式）證明:(1)當(dāng)n=e=1時(shí),如下圖,結(jié)論顯然成立.v=2,e=1,r=1v=1,e=1,r=26(2)下用數(shù)學(xué)歸納法證明. 假設(shè)公式對n條邊的圖成立.設(shè)G有n+1條邊.若G不含圈,任取一點(diǎn)x,從結(jié)點(diǎn)x開始沿路行走.因G不含圈,所以每次沿一邊總能達(dá)到一個(gè)新結(jié)點(diǎn),最后會(huì)達(dá)到一個(gè)度數(shù)為1的結(jié)點(diǎn),不妨設(shè)為a,在結(jié)點(diǎn)a不能再繼續(xù)前進(jìn).刪除結(jié)點(diǎn)a及其關(guān)聯(lián)的邊得圖G,G含有n條邊.由假設(shè)公式對G成立,而G比G多一個(gè)結(jié)點(diǎn)和一條邊,且G與G面數(shù)相同,故公式也適合于G.

4、若G含有圈C,設(shè)y是圈C上的一邊,則邊y一定是兩個(gè)不同面的邊界的一部分.刪除邊y得圖G,則G有n條邊.由假設(shè)公式對G成立而G比G多一邊和多一面,G與G得頂點(diǎn)數(shù)相同.故公式也成立.7推論1 設(shè)G是帶v個(gè)頂點(diǎn)，e條邊的連通的平面簡單圖，其中v3，則e3v-6。證明:由于G是簡單圖,則G中無環(huán)和無平行邊.因此G的任何面的度數(shù)至少為3.故2e=d(f)3r (1) 其中r為G的面數(shù).由歐拉公式v-e+r=2所以r=2-v+e,代入(1)中有:2e3(2-v+e)即e3v-6。8推論2 設(shè)G是帶v個(gè)頂點(diǎn)，e條邊的連通的平面簡單圖，其中v3且沒有長度為3的圈，則e2v-4。證明:因?yàn)閳DG中沒有長度為3的圈

5、,從而G的每個(gè)面的度數(shù)至少為4.因此有2e=d(f)4r (1)其中r為G的面數(shù).由歐拉公式v-e+r=2所以r=2-v+e,代入(1)中有:2e4(2-v+e)即e2v-4。例3 K5和K3.3都是非平面圖。解:圖K5有5個(gè)頂點(diǎn)10條邊,而3*5-6=9,即109,由9推論1知,K5是非平面圖. 顯然K3,3沒有長度為3的圈,且有6個(gè)頂點(diǎn)9條邊,因而92*6-4,由推論2知K3,3是非平面圖.推論3 設(shè)G是帶v個(gè)頂點(diǎn)，e條邊，r個(gè)面的平面圖，則 v- e+ r=1+w。其中w為G的連通分支數(shù)。證明:由歐拉公式有: vi- ei+ ri=2(i=1,2,w)從而有 vi- ei+ ri =2w

6、又 vi=v, ei=e, ri =r+(w-1)(外部面被重復(fù)計(jì)算了w-1次.).所以有:V-e+r+(w-1)=2w整理即得: v- e+ r=1+w.10推論4 設(shè)G是任意平面簡單圖，則（G）5。證明:設(shè)G有v個(gè)頂點(diǎn)e條邊.若e6,結(jié)論顯然成立;若e6,假設(shè)G的每個(gè)頂點(diǎn)的度數(shù)6,則由推論1,有6v 2e 6v-12矛盾,所以（G）5.例4平面上有n個(gè)頂點(diǎn)，其中任兩個(gè)點(diǎn)之間的距離至少為1，證明在這n個(gè)點(diǎn)中距離恰好為1的的點(diǎn)對數(shù)至多是3n-6。證明:首先建立圖G=,其中V就取平面上給定的n個(gè)點(diǎn)(位置相同),當(dāng)兩個(gè)頂點(diǎn)之間的距離為1時(shí),兩頂點(diǎn)之間用一條直線段連接,顯然圖G是一個(gè)n階簡單圖.11 由推論1,只要證明G為一平面圖時(shí)即知結(jié)論成立. 反設(shè)G中存在兩條不同的邊a,b和x,y相交于非端點(diǎn)處o,如下圖(a)所示,其夾角為(0 ). 若 =,這時(shí)如下圖(b),顯然存在兩點(diǎn)距離小于1,與已知矛盾,從而0 .由于a到b的距離為1,x到y(tǒng)的距離為1,因此a,b,x,y中至少有兩個(gè)