第七章_平面圖

1、平面圖一個圖G如果能以這樣的方式畫在平面上;除頂點(diǎn)處外沒有邊交叉出現(xiàn),則稱G為平面圖.畫出的沒有邊交叉出現(xiàn)的圖稱為G的一個平面嵌入或G的一個平圖.圖中,(2)是(1)(K4)的平面嵌入,所以(1)是平面圖. (2)是平面圖. (3),(5)都不是平面圖,即K5和K3,3都不是平面圖.平面圖中的一些概念設(shè)G是一個連通的平面圖(指G的某個平面嵌入),G的邊將G所在的平面劃分成若干個區(qū)域,每個區(qū)域稱為G的一個面.其中面積無限的區(qū)域稱為無限面或外部面,常記成R0.包圍每個面的所有邊所構(gòu)成的回路稱為該面的邊界,邊界的長度稱為該面的次數(shù),R的次數(shù)記為deg(R).對于非連通的平面圖G有k(k2)個連通分支

2、,則G的無限面R0的邊界由k個回路圍成.圖(1)所示為連通的平面圖,共有3個面R0,R1,R2.R1的邊界為回路v1v3v4v1,deg(R1)=3.R2的邊界為回路v1v2v3v1,deg(R2)=3.R0的邊界為復(fù)雜回路v1v4v5v6v5v4v3v2v1,deg(R0)=8.例abcdefghijklmR1R2R3R4R0圖(2)與(3)都是(1)的平面嵌入,它們都與(1)同構(gòu)。圖(2),deg(R0)=3;圖(3),deg(R0)=4.定理 在一個平面圖G中,所有面的次數(shù)之和都等于邊數(shù)n的2倍, 即(r為面數(shù)) 1deg()2riiRm極大平面圖、極小非平面圖設(shè)G為一個簡單平面圖,如果

3、在G中任意不相鄰的兩個頂點(diǎn)之間再加一條邊,所得圖為非平面圖,則稱G為極大平面圖.若在非平面圖G中任意刪除一條邊,所得圖為平面圖,則稱G為極小非平面圖.例K5, K3,3是極小非平面圖， K5任意刪除一條邊后所得圖是極大平面圖性質(zhì) 極大平面圖有以下性質(zhì);v (1)極大平面圖是連通的;v (2)任何n(n3)階極大平面圖中,每個面的次數(shù)均為3.v (3)任何n(n4)階極大平面圖G中,均有(G)3.歐拉公式設(shè)G為任意的連通的平面圖,則有 n-m+r2成立.其中,n為G中頂點(diǎn)數(shù),m為邊數(shù),r為面數(shù).證明證明 對邊數(shù)m作歸納法.v (1)m0時,G為孤立點(diǎn),此時n1,r1,結(jié)論自然成立.v (2)設(shè)m

4、k-1(k1)時結(jié)論成立,要證明mk時結(jié)論成立.證明v首先,若G為樹,任取一樹葉v并刪除它,得GG-v, G中有nn-1個頂點(diǎn)mm-1條邊,rr,由歸納假設(shè)有下式成立; n-m+r2,即 (n-1)-(m-1)+r2,整理后得 n-m+r2. 證明v其次,G不是樹,證明則G中必有初級回路.設(shè)C為一初級回路,e在C上.令GG-e,由于e在C上,所以,G仍連通,在G中,nm,mm-1,rr-1,利用歸納假設(shè)可得 n-m+r2. 歐拉公式的推廣v對于任意的p(p2)個連通分支的平面圖G,有 n-m+rp+1成立.定理v設(shè)G是連通的平面圖,且每個面的次數(shù)至少為l(l3),則 (2)2lmnlv證明.

5、2mlr,v n-mr2,vln-lm2m ln-lmlr2l,v lm-2mln-2lv (2)2lmnl推廣v設(shè)G是p(p2)個連通分支的平面圖,每個面的次數(shù)至少為l(l3),則(1)2lmnplK5和K3,3vK5和K3,3都不是平面圖.若K5是平面圖,則每個面的次數(shù)至少為3.但是由前面的定理有; 103(5-2)9這是矛盾的,因而K5不是平面圖. 類似地,K3,3也不是平面圖. 定理6v設(shè)G為連通的簡單的平面圖,則G中至少存在一個頂點(diǎn)v,有d(v)5. v證明.v假設(shè)任意頂點(diǎn)v,d(v)6.v 6n2m,3r2mv 3nmv n-mr2v 63n-3m3rm-3m2m0 這不可能.消去

6、 插入v 在圖(1)中,從左到右的變換稱為消去2度頂點(diǎn)w.圖(2)中從左到右的變換稱為插入2度頂點(diǎn)w.同胚 初等收縮v如果兩個圖G1和G2同構(gòu),或經(jīng)過反復(fù)插入或消去2度頂點(diǎn)后同構(gòu),則稱G1與G2同胚.v圖G中相鄰頂點(diǎn)u,v之間的初等收縮由下面方法給出;刪除邊(u,v),用新的頂點(diǎn)w取代u,v,使w關(guān)聯(lián)u,v關(guān)聯(lián)的一切邊(除(u,v)外).庫拉圖斯基定理v一個圖是平面圖當(dāng)且僅當(dāng)它不含與K5同胚子圖,也不含與K3,3同胚子圖.v另一種敘述形式; 一個圖是平面圖當(dāng)且僅當(dāng)它沒有可以收縮到K5的子圖,也沒有收縮到K3,3的子圖.agcdefhibj收縮邊(a, f), (b, g), (c, h), (

7、d, i), (e, j)，所得圖為K5?；蛘吡頖=G-(j, g), (d, c)，則G與K3,3同胚例abcdefg令G=G-(d, f), (g, c)，易知G與K5同胚。令G=G-(a, e), (a, f), (b, g), (g, f)，則G與K3,3同胚對偶圖v設(shè)平面圖G,G有r個面,n個頂點(diǎn),m條邊.用如下的方法構(gòu)造G*;v (1)在G的面Ri中任取一個頂點(diǎn)vi*作為G*的頂點(diǎn),G*的頂點(diǎn)集V*v1*,v2*,.,vr*,對偶圖v(2)若面Ri和Rj的邊界中有公共邊ek,連接對應(yīng)頂點(diǎn)vi*和vj*,得G*的邊ek*與ek相交.當(dāng)ek只在G的一個面Rj的邊界中出現(xiàn)時,以Ri中的頂

8、點(diǎn)vi*為頂點(diǎn)做環(huán)ek*,ek*為G*中一個環(huán).設(shè)G*的邊集為E*,由于G*的邊數(shù)與G的邊數(shù)相同,則E*e1*,e2*,em*,稱G*為G的對偶圖.例(a)(b)對偶圖v對于任意的連通的平面圖G,有n*=r,m*=m,r*=n成立,其中,n,m,r分別為G的頂點(diǎn)數(shù)、邊數(shù)和面數(shù).n*,m*,r*分別為G的對偶圖G*的頂點(diǎn)數(shù)、邊數(shù)和面數(shù).v同構(gòu)平面圖的對偶圖,不一定是同構(gòu)的.G的對偶圖G*的對偶圖G*不一定與G同構(gòu).染色圖 v一個圖用彩色將每個頂點(diǎn)著色一個圖用彩色將每個頂點(diǎn)著色,相鄰頂點(diǎn)染不相鄰頂點(diǎn)染不同顏色同顏色.v一個平面圖用彩色將每個面著色一個平面圖用彩色將每個面著色,相鄰面染不相鄰面染不同

9、顏色同顏色.只要換成其對偶圖即可只要換成其對偶圖即可.v平面圖平面圖G最少用最少用k種顏色染色種顏色染色,就稱為就稱為k色圖色圖.vk稱為稱為chromatic number of G.記做記做(G)v四色定理四色定理:任何一個平面圖都是四色任何一個平面圖都是四色圖圖.染色多項式 v用用n種顏色染一個圖種顏色染一個圖,有多少不同的有多少不同的方法方法,記做記做P G(n)vPG是一個多項式函數(shù)是一個多項式函數(shù),稱為稱為chromatic polynomial of G.v例例4. v設(shè)設(shè)L4是是4個頂點(diǎn)的一條線個頂點(diǎn)的一條線.用用x種顏種顏色色,第一點(diǎn)第一點(diǎn),x種方法著色種方法著色,第二點(diǎn)第二

10、點(diǎn)x-1種方法著色種方法著色.第三第四點(diǎn)都是第三第四點(diǎn)都是x-1.vPL4(x)=x(x-1)3. (L4)2.v例例5vP Kn(x)=x(x-1)(x-2)(x-n+1)=xn.v(Kn)n.v定理定理1. 設(shè)設(shè)G1,G2,Gm是是G的連的連通分量通分量,則則vP G(x) = P G1(x) P G2(x)P Gm(x).v(G)max(G1), (G2),(Gm)v例例6. vG是兩個不相連三角形是兩個不相連三角形,PG(x)= x2(x-1)2(x-2)2.v例例7. vG是是n個不相連頂點(diǎn)個不相連頂點(diǎn),PG(x)=xn.Ge是是G去掉去掉e導(dǎo)出的子圖導(dǎo)出的子圖,Ge是將是將e的的兩

11、端點(diǎn)粘合得到的圖兩端點(diǎn)粘合得到的圖.定理定理2. PG(x)PGe(x)-PGe(x)v證明證明. v設(shè)設(shè)e的端點(diǎn)為的端點(diǎn)為a,b.G著色必須將著色必須將ab著著不同色不同色. Ge著色必須將著色必須將ab著同色著同色.Ge著色著色a,b可著同色可著同色,可著不同色可著不同色.vPGe(x)PG(x)+PGe(x).例 如下圖 vPGe(x)=x2(x-1)2(x-2)2,vPGe(x)= x (x-1)2(x-2)2,vPG(x)= PGe(x)-P Ge(x)v=x2(x-1)2(x-2)2-x (x-1)2(x-2)2vx (x-1)3(x-2)2,v(G)=3, G是是3色圖色圖.ev

12、定理定理3.v設(shè)設(shè)G是簡單圖是簡單圖,G已染色已染色,相鄰頂點(diǎn)顏相鄰頂點(diǎn)顏色不同色不同.G中染色中染色兩種顏色的頂兩種顏色的頂點(diǎn)導(dǎo)出子圖為點(diǎn)導(dǎo)出子圖為G.交換交換G中一個中一個連通分量中染色連通分量中染色和和,G仍然保持仍然保持相鄰頂點(diǎn)不同顏色相鄰頂點(diǎn)不同顏色.v證明證明.G中任意相鄰兩點(diǎn)中任意相鄰兩點(diǎn)a,b. vb G,或或a,bG,或或aG且且b G,a,b染色仍然不同染色仍然不同.v定理定理4(五色定理五色定理)vG是任意一個平面圖是任意一個平面圖,則則(G)5.v證明證明.對對G的頂點(diǎn)個數(shù)歸納的頂點(diǎn)個數(shù)歸納.G中至少中至少有一點(diǎn)有一點(diǎn)a,D(a)5.歸納假設(shè)去掉歸納假設(shè)去掉a,導(dǎo)出導(dǎo)出

13、的子圖的子圖G可以用可以用5重顏色著色重顏色著色.v如果如果a只與只與G中中4個點(diǎn)相鄰個點(diǎn)相鄰,a可以用第可以用第五種顏色著色五種顏色著色. v如果如果a與與G中中5個點(diǎn)相鄰個點(diǎn)相鄰,但但5點(diǎn)中點(diǎn)中有重復(fù)顏色有重復(fù)顏色,a可以用第五種顏色著可以用第五種顏色著色色.v假設(shè)假設(shè)a與與G中中5個點(diǎn)相鄰個點(diǎn)相鄰,5點(diǎn)著色點(diǎn)著色各不相同各不相同,5點(diǎn)分別是點(diǎn)分別是b1,b2,b5. v設(shè)設(shè)b1著色著色,b2著色著色,而而b1,b2,不不在在G的同一個連通分量中的同一個連通分量中.由引由引理理3,交換交換b3所在分量中顏色所在分量中顏色和和,可以使可以使b1,b3著色相同著色相同.這時這時a可可著色著色.v設(shè)設(shè)b1著色著色,b3著色著色,而而b1,b3在在G的同一個連通分量中的同一個連通分量中.這