1、CHAP11平面圖精品文檔CHAP11平面圖精品文檔圖中的邊不要交叉實(shí)際中的很多問(wèn)題都涉及到一個(gè)圖中的邊是否會(huì)交叉的問(wèn)題。例如：?jiǎn)蚊嬗∷㈦娐钒?，集成電路的布線，交通設(shè)計(jì)問(wèn)題；等等。由此便抽象出平面圖的概念：沒(méi)有交叉 (這里當(dāng)然不是指在端點(diǎn)處的相互鄰接）的邊的圖。一個(gè)有交叉的邊的圖能不能轉(zhuǎn)換成與之同構(gòu)的平面圖，顯然是人們所關(guān)注的問(wèn)題。本章就是介紹平面圖以及平面圖的性質(zhì)。9/21/20222離散數(shù)學(xué)圖中的邊不要交叉實(shí)際中的很多問(wèn)題都涉及到一個(gè)圖中的邊是否會(huì)交11.1 平面圖的概念9/21/20223離散數(shù)學(xué)11.1 平面圖的概念9/21/20225離散數(shù)學(xué)平面圖定義11.1.1：設(shè)G是平面上由有限

2、個(gè)點(diǎn)及以這些點(diǎn)為端點(diǎn)的有限連續(xù)曲線所組成的圖形，如果G中任意兩條線最多只在它們的端點(diǎn)處相交，稱(chēng)G為平面圖。例1，圖不是平面圖， 和是平面圖。9/21/20224離散數(shù)學(xué)平面圖定義11.1.1：設(shè)G是平面上由有限個(gè)點(diǎn)及以這些點(diǎn)為端可平面圖上例中的圖雖然不是平面圖，但是卻和圖和圖是同構(gòu)的，這樣的圖稱(chēng)為可平面圖?？善矫鎴D：如果一個(gè)圖G與一個(gè)平面圖H同構(gòu)，稱(chēng)G是可平面圖；而稱(chēng)H是G的一個(gè)平面嵌入。上例中的圖是可平面圖，圖和圖是圖的兩個(gè)平面嵌入。9/21/20225離散數(shù)學(xué)可平面圖上例中的圖雖然不是平面圖，但是卻和圖和圖是同構(gòu)平面圖的面定義11.1.2：設(shè)G是一個(gè)平面圖，平面被G的邊所圍成的區(qū)域稱(chēng)為面，

3、這些邊稱(chēng)為該面的邊界；其中有限區(qū)域?qū)?yīng)的面稱(chēng)為內(nèi)部面，無(wú)限區(qū)域?qū)?yīng)的面稱(chēng)為外部面(用f0表示)。用G(p, q, r)表示一個(gè)p個(gè)頂點(diǎn)，q條邊以及r個(gè)面的平面圖。一個(gè)面 f 所包含的邊數(shù)稱(chēng)為 f 的次數(shù)，記為d( f ) ，若邊為割邊，則計(jì)算兩次。9/21/20226離散數(shù)學(xué)平面圖的面定義11.1.2：設(shè)G是一個(gè)平面圖，平面被G的邊所計(jì)算下圖中各面的次數(shù)：d( f0 ) = 3 ; d( f1 ) = 5 。2431f1f0(a)f1f0(b)f2d( f0 ) = 8 ;d( f1 ) = 3 ;d( f2 ) = 3 .9/21/20227離散數(shù)學(xué)計(jì)算下圖中各面的次數(shù)：d( f0 ) =

4、3 ; 2431f面的總次數(shù)為邊數(shù)的兩倍定理11.1.1：對(duì)任何平面圖G(p, q, r) ,有 d( fi ) =2q , (i =1 , 2 , ,r).證明：由于G的每條非割邊恰屬于兩個(gè)面，所以，在計(jì)算這兩個(gè)面的次數(shù)時(shí)，該邊計(jì)算兩次，而割邊只屬于一個(gè)面，但由規(guī)定也計(jì)算了兩次，故上式成立，即所有面的總次數(shù)為邊數(shù)的兩倍。對(duì)比：d( vi ) =2q，(i =1 , 2 , , p)，即所有頂點(diǎn)的總度數(shù)為邊數(shù)的二倍。9/21/20228離散數(shù)學(xué)面的總次數(shù)為邊數(shù)的兩倍定理11.1.1：對(duì)任何平面圖G(p,平面圖的同構(gòu)定義11.1.3：設(shè)G和H是兩個(gè)平面圖。如果并且 f 是G中一個(gè)由途徑uvwu圍

5、成的面當(dāng)且僅當(dāng)(u)(v) (w)(u)圍成H的一個(gè)面 f , 則稱(chēng)G與H同構(gòu)。有時(shí)可省略。例1中圖與圖就是平面圖同構(gòu)。9/21/20229離散數(shù)學(xué)平面圖的同構(gòu)定義11.1.3：設(shè)G和H是兩個(gè)平面圖。如果并且圖的同構(gòu)與平面圖的同構(gòu)如果兩個(gè)圖是平面圖同構(gòu)，則必是兩個(gè)同構(gòu)的圖?？墒莾蓚€(gè)同構(gòu)的圖不一定是平面圖同構(gòu)。例1中圖與圖和圖是同構(gòu)的圖，但圖卻不是平面圖，因而不可能和它們平面圖同構(gòu)。下面兩個(gè)平面圖是圖同構(gòu)，但不是平面圖同構(gòu)：GH1345123456629/21/202210離散數(shù)學(xué)圖的同構(gòu)與平面圖的同構(gòu)如果兩個(gè)圖是平面圖同構(gòu)，則必是兩個(gè)同構(gòu)外平面圖定義11.1.4：圖G稱(chēng)為外可平面圖，如果它有一

6、個(gè)平面嵌入H，使得G的所有頂點(diǎn)均在H的同一個(gè)面的邊界上，這時(shí)，稱(chēng)H為外平面圖。f1f1這是外平面圖這不是外平面圖這是外可平面圖9/21/202211離散數(shù)學(xué)外平面圖定義11.1.4：圖G稱(chēng)為外可平面圖，如果它有一個(gè)平極大平面圖定義11.1.5 設(shè)G是一個(gè)可平面圖，如果對(duì)G中任意兩個(gè)互不鄰接的頂點(diǎn)u , v , G+uv成為一個(gè) 不可平面圖，則稱(chēng)G是一個(gè)極大可平面圖，極大可平面圖的一個(gè)平面嵌入稱(chēng)為極大平面圖。說(shuō)明：對(duì)一個(gè)不是極大的可平面圖，可以添加一些邊以得到一個(gè)極大可平面圖。(如圖)9/21/202212離散數(shù)學(xué)極大平面圖定義11.1.5 設(shè)G是一個(gè)可平面圖，如果對(duì)G中G是極大平面圖當(dāng)且僅當(dāng)G

7、的每個(gè)面都是三角形(必要性) 極大簡(jiǎn)單平面圖的任何一個(gè)面都是三角形K3。 證明： (反證)設(shè)G是極大簡(jiǎn)單平面圖。若G的某個(gè)面 f 不是K3，不妨設(shè) f 由閉途徑v1v2vnv1圍成，且d(f) = n 4。為簡(jiǎn)單起見(jiàn)，不妨設(shè)n = 4，即f 由閉途徑v1v2v3v4v1圍成。則 f 只有以下三種情況：v1與v3不鄰接；v1與v3鄰接，而v2與 v4不鄰接； v1與v3鄰接，而v2與 v4也鄰接。 下面我們對(duì)這三種情況分別予以討論：9/21/202213離散數(shù)學(xué)G是極大平面圖當(dāng)且僅當(dāng)G的每個(gè)面都是三角形(必要性) 極大極大平面圖的面都是三角形證明：若v1與v3不鄰接，則v1v2v3v4v1所圍成

8、內(nèi)部面，v1v2v3v4 于是在該面內(nèi)聯(lián) 結(jié)v1和v3不破壞G的平面性，此與G的假設(shè)矛盾；若v1與v3鄰接，v2與v4不鄰接，則v1v2v3 v1 圍成內(nèi)部面，邊v1v4及頂點(diǎn)v4必在此面的外部，v1v2v3v4 故聯(lián)結(jié)v2和v4不破壞G的平面性，此與G的假設(shè)矛盾；9/21/202214離散數(shù)學(xué)極大平面圖的面都是三角形證明：v1v2v3v4 極大平面圖的面都是三角形證明：若v1與v3鄰接，且 v2與v4鄰接，則v1v2v3v4v1所圍成的區(qū)域是內(nèi)部面。因此邊v1v3，v2v4都在此面之外，因而必相交, 此與G的可平面性矛盾。v1v2v3v4綜合以上，知結(jié)論成立。9/21/202215離散數(shù)學(xué)極

9、大平面圖的面都是三角形證明：v1v2v3v4綜合以上，知(充分性)若平面圖G的每個(gè)面都是三角形， 則是G是極大平面圖。 證明：設(shè)平面圖G的每個(gè)面都是K3，若G不是極大平面圖.則G中存在u、vV(G)，使得uvE(G)，且G+uv仍為平面圖。設(shè)uv是G+uv中兩個(gè)面fi和fj的公共邊界.于是，G中fi和fj的面是一個(gè)面fk ，顯然，d(fk)3,由此G與的每個(gè)面是K3矛盾！9/21/202216離散數(shù)學(xué)(充分性)若平面圖G的每個(gè)面都是三角形， 則是G11.2 歐拉公式9/21/202217離散數(shù)學(xué)11.2 歐拉公式9/21/202219離散數(shù)學(xué) 歐拉公式定理:對(duì)任何一個(gè)簡(jiǎn)單平面圖G (p, q,

10、 r)均滿(mǎn)足： p q + r = 2 .證明：對(duì)面數(shù)r作歸納證明。當(dāng)r=1時(shí)，G是樹(shù)，此時(shí)q = p 1，結(jié)論成立。假設(shè)對(duì)G (p, q, r-1)， r2，結(jié)論成立，設(shè)G是有r個(gè)面的平面圖，G至少有一條回路。設(shè)e是某回路上的邊，G e仍是連通平面圖，它有p個(gè)頂點(diǎn)，q 1條邊和r 1個(gè)面，由歸納假設(shè)有， p (q 1)+(r 1) = 2。整理即得 p q + r = 2。由歸納法原理，歐拉公式成立。9/21/202218離散數(shù)學(xué) 歐拉公式定理:對(duì)任何一個(gè)簡(jiǎn)單平面圖G (p, q, r)均面等次平面圖中邊與點(diǎn)的關(guān)系推論11.2.1：若簡(jiǎn)單平面圖G (p, q, r)的每個(gè)面的次數(shù)均為m ,

11、則 q = m(p 2) / (m 2)證明：由定理11.1.1，2q = d( fi ) = mr ，解出r，代入歐拉公式, 得 p q + (2/m)q = 2 整理上式即得證。9/21/202219離散數(shù)學(xué)面等次平面圖中邊與點(diǎn)的關(guān)系推論11.2.1：若簡(jiǎn)單平面圖G 簡(jiǎn)單平面圖邊數(shù)的上界推論11.2.2 對(duì)任何簡(jiǎn)單平面圖G (p, q, r) ( p 3) , q 3p 6 .證明：由于極大簡(jiǎn)單平面圖的每個(gè)面都是K3 ,故將 m = 3代入推論11.2.1中的式q = m(p 2) / (m 2) 有 q= 3(p 2) = 3p 6 . 故對(duì)一般簡(jiǎn)單平面圖有q 3p 6 .9/21/20

12、2220離散數(shù)學(xué)簡(jiǎn)單平面圖邊數(shù)的上界推論11.2.2 對(duì)任何簡(jiǎn)單平面圖GK5是不可平面圖推論11.2.3 K5是不可平面圖。證明：若K5是可平面圖，則由推論11.2.2知q 3p 6 ，于是 10 = q 3p 6 =35 6 = 9 , 即 ：10 9 ，矛盾。故結(jié)論成立。9/21/202221離散數(shù)學(xué)K5是不可平面圖推論11.2.3 K5是不可平面圖。9/無(wú)3次面的平面圖邊數(shù)的上界推論11.2.4：若簡(jiǎn)單平面圖G (p, q, r)的每個(gè)面均不是K3 ，則 q 2p 4 .證明：由假設(shè)每個(gè)面的次數(shù)至少不小于4 2q = d( fi ) 4r即 r q /2 ,從而由歐拉公式有 2 = p

13、q + r p q + q /2 = p q /2 整理后得 q 2p 4 .9/21/202222離散數(shù)學(xué)無(wú)3次面的平面圖邊數(shù)的上界推論11.2.4：若簡(jiǎn)單平面圖G K3,3是不可平面圖推論11.2.5：K3,3是不可平面圖。證明：因K3,3是二分圖，故它不含K3 ，假設(shè)K3,3是可平面圖，則由推論11.2.4知 9 = q 2p 4 =26 4 = 8 , 即 ：9 8 ，矛盾。故結(jié)論成立。9/21/202223離散數(shù)學(xué)K3,3是不可平面圖推論11.2.5：K3,3是不可平面圖。簡(jiǎn)單平面圖的最小度小于6推論11.2.6：任何簡(jiǎn)單平面圖G (p, q, r)均有(G) 6。證明：若(G) 6

14、，則 q = (1/2) d( vi ) (2q = d( vi ) ) (1/2)p (G) (6/2)p 3p 6 ,此與推論11.2.2( 對(duì)任何簡(jiǎn)單平面圖G (p, q, r) ( p 3)，都有 q 3p 6 )矛盾。故結(jié)論成立。9/21/202224離散數(shù)學(xué)簡(jiǎn)單平面圖的最小度小于6推論11.2.6：任何簡(jiǎn)單平面圖G 極大平面圖的五個(gè)性質(zhì) 定理11.2.2：設(shè)簡(jiǎn)單平面圖G (p, q, r)是極大平面圖( p 4) ，于是 q = 3p 6 ; r = 2p 4 ; (G) 3 ; G中至少有4個(gè)頂點(diǎn)的度不超過(guò)5 . 9/21/202225離散數(shù)學(xué)極大平面圖的五個(gè)性質(zhì) 定理11.2.

15、2：設(shè)簡(jiǎn)單平面圖G (p極大平面圖的邊數(shù)證明：由定理11.1.2(極大簡(jiǎn)單平面圖的任何一個(gè)面都是三角形K3 ) ，將推論11.2.1中的式q = m(p 2) / (m 2)中的m用m=3 代入，即可得q = 3p 6 ;9/21/202226離散數(shù)學(xué)極大平面圖的邊數(shù)證明：由定理11.1.2(極大簡(jiǎn)單平面圖的任極大平面圖的面數(shù)證明：由性質(zhì)有q = 3p 6 ，將其代入歐拉公式得： p q + r = p (3p 6) + r = 2 , 整理即得r = 2p 4 ；9/21/202227離散數(shù)學(xué)極大平面圖的面數(shù)證明：由性質(zhì)有q = 3p 6 ，將其極大平面圖連通度不小于3證明：G的面都是K3，

16、 (G) 2。 假設(shè)(G) = 2 ，則有頂點(diǎn)割S =u, v。其中的u和v都應(yīng)該與G S的至少兩個(gè)連通分支中的頂點(diǎn)在G中鄰接。不妨設(shè)在G的一個(gè)平面嵌入G 中與u鄰接的點(diǎn)按環(huán)繞u的順序依次為u1, , ut。而 u1, , ut中除可能有一點(diǎn)是v外，其余的點(diǎn)分別屬于GS的至少兩個(gè)分支，必有兩點(diǎn)ui和ui+1分屬G S的兩個(gè)不同分支。9/21/202228離散數(shù)學(xué)極大平面圖連通度不小于3證明：G的面都是K3， (G)極大平面圖連通度不小于3證明： S是頂點(diǎn)割，ui和ui+1分別屬于G S的兩個(gè)不同分支。uvui+1uif1由ui和ui+1的取法可知，在uui和uui+1之間沒(méi)有其它與u鄰接的邊，

17、依據(jù)定理 11.1.2，在G 中u uiui+1是一個(gè)K3面，故ui和ui+1鄰接。從而在G S中， ui也和ui+1鄰接，這與S是頂點(diǎn)割相矛盾。所以 (G) 3。9/21/202229離散數(shù)學(xué)極大平面圖連通度不小于3證明： S是頂點(diǎn)割，ui和ui+極大平面圖最小度不小于3證明：由定理7.1.1可知圖的連通度不大于邊連通度，而邊連通度又不大于最小度，即(G) (G) (G) ；又由性質(zhì)即可得極大平面圖最小度不小于3，即(G) (G) 3 。9/21/202230離散數(shù)學(xué)極大平面圖最小度不小于3證明：由定理7.1.1可知圖的連通度至少有4個(gè)頂點(diǎn)的度不超過(guò)5證明：設(shè)G的頂點(diǎn)集V = v1 , v2

18、 , , vp。 若對(duì)i = 1, 2, , p 3，均有d(vi) 6，則由性質(zhì)， 對(duì)i = p2 , p1, p，有d(vi) (G) 3。 于是，6p 21= 2q 9？因?yàn)橛尚再|(zhì)，q = 3p 6 ，于是6p 12 = 2q 2q d( vj ) (這里j = p2, p-1, p) = d(vi ) (這里i =1, 2, , p 3) 6(p 3) = 6p 18 .此為矛盾，故結(jié)論成立。習(xí)題9/21/202231離散數(shù)學(xué)至少有4個(gè)頂點(diǎn)的度不超過(guò)5證明：設(shè)G的頂點(diǎn)集V = v1 11.3 可平面性判定9/21/202232離散數(shù)學(xué)11.3 可平面性判定9/21/202234離散數(shù)學(xué)

19、剖分圖定義11.3.1：設(shè)G是一個(gè)圖，e = uv E(G)，在G uv中增加一個(gè)新點(diǎn)w及邊wu , wv .稱(chēng)此過(guò)程為對(duì)圖G的一次剖分運(yùn)算。如果H是由G經(jīng)過(guò)有限次剖分運(yùn)算得到的，則稱(chēng)H是G的剖分圖。直觀地說(shuō)，剖分就是在圖的某邊上加個(gè)頂點(diǎn)。右邊就是K4的剖分。9/21/202233離散數(shù)學(xué)剖分圖定義11.3.1：設(shè)G是一個(gè)圖，e = uv E(可平面圖的充要條件定理11.3.1 (Kuratowski定理) 一個(gè)圖是可平面圖的充分必要條件是它不包含K5或K3,3的剖分圖.該定理亦可描述為：一個(gè)圖是可平面的當(dāng)且僅當(dāng)它沒(méi)有一個(gè)可以收縮到K5或K3,3的子圖。9/21/202234離散數(shù)學(xué)可平面圖的

20、充要條件定理11.3.1 (Kuratowski定Petersen圖的收縮和剖分Petersen圖例如：Petersen圖不是可平面圖，因?yàn)樗蠯3,3的剖分。Petersen圖含有K3,3的剖分Petersen圖收縮為K5它也可以收縮為K5。9/21/202235離散數(shù)學(xué)Petersen圖的收縮和剖分Petersen圖例如：Pet11.4 平面圖的面著色9/21/202236離散數(shù)學(xué)11.4 平面圖的面著色9/21/202238離散數(shù)學(xué)給平面圖著色對(duì)簡(jiǎn)單圖G(p, q)只考慮頂點(diǎn)和邊，其著色也只有點(diǎn)著色和邊著色。對(duì)簡(jiǎn)單平面圖G (p, q, r)則還需要考慮面，其著色還由相應(yīng)的面著色。平面

21、圖著色的一個(gè)直接的重要的應(yīng)用:地圖著色 。用顏色來(lái)區(qū)分地圖中的區(qū)域，需要多少種顏色呢？這就是著名的四色問(wèn)題。9/21/202237離散數(shù)學(xué)給平面圖著色對(duì)簡(jiǎn)單圖G(p, q)只考慮頂點(diǎn)和邊，其著色也只面的鄰接定義1.4.1：設(shè) f1 和 f2是平面圖G的兩個(gè)面。若 f1 和 f2的邊界至少有一條公共邊，則稱(chēng)f1與 f2是鄰接的，否則稱(chēng) f1與 f2不鄰接。三種鄰接： 點(diǎn)鄰接：兩個(gè)頂點(diǎn)有邊相關(guān)聯(lián)； 邊鄰接：兩條邊有共同的端點(diǎn)； 面鄰接：兩個(gè)面有共同的邊。9/21/202238離散數(shù)學(xué)面的鄰接定義1.4.1：設(shè) f1 和 f2是平面圖G的兩個(gè)面有公共頂點(diǎn)的面不是鄰接的面注意：兩個(gè)面如果在邊界上只有一

22、個(gè)或有限個(gè)公共點(diǎn)，則它們是不鄰接的。如下左圖中的面A與E , A與C , A與D都不是鄰接的面。下右圖中的面A與C，B與D也都不是鄰接的面ABCDEFABCD9/21/202239離散數(shù)學(xué)有公共頂點(diǎn)的面不是鄰接的面注意：兩個(gè)面如果在邊界上只有一個(gè)或面著色定義11.4.2：設(shè)G是平面圖，S = 1, 2, , k，k1。若存在面集R(G)到S的滿(mǎn)射r，則稱(chēng)r為G的k面著色，S為面色集。若對(duì)G中任意兩個(gè)鄰接面 f1和 f2 ，均有r(f1)r(f2)，則稱(chēng)r是正常k面著色，并稱(chēng)G是k面可著色的。圖G 的正常k面可著色中最小的k稱(chēng)為G的面色數(shù)，記為*(G) 。對(duì)比：色數(shù)(G) ：最小正常k(頂點(diǎn))著

23、色； 邊色數(shù)(G) ：最小正常k邊著色； 面色數(shù)*(G) ：最小正常k面著色。9/21/202240離散數(shù)學(xué)面著色定義11.4.2：設(shè)G是平面圖，S = 1, 2, 對(duì)偶圖如果把每個(gè)面看作一個(gè)頂點(diǎn)，若兩個(gè)面的邊界有一條公共邊，則看作兩個(gè)頂點(diǎn)之間有一條邊關(guān)聯(lián)。這樣就可以把一個(gè)平面圖G中面與面之間鄰接關(guān)系描述為另一個(gè)圖G*中頂點(diǎn)與頂點(diǎn)之間的鄰接關(guān)系。這樣對(duì)一個(gè)平面圖G進(jìn)行轉(zhuǎn)換，所得到的圖G*稱(chēng)為圖G的對(duì)偶圖于是可將對(duì)平面圖G的面著色轉(zhuǎn)換為對(duì)其對(duì)偶圖G*的點(diǎn)著色問(wèn)題。9/21/202241離散數(shù)學(xué)對(duì)偶圖如果把每個(gè)面看作一個(gè)頂點(diǎn)，若兩個(gè)面的邊界有一條公共邊，對(duì)偶圖的構(gòu)造對(duì)偶圖的構(gòu)造：在G的每個(gè)面內(nèi)放一

24、個(gè)頂點(diǎn) f*，這些頂點(diǎn)就構(gòu)成了G*的頂點(diǎn)集V(G*)。 若G的兩個(gè)面 f 和g有一條公共邊e， 則畫(huà)一條以 f*和 g*為端點(diǎn)的邊e*， e*僅穿過(guò)e一次，對(duì)于G中僅屬于一個(gè)面的割邊e，則畫(huà)一條以 f*為端點(diǎn)的環(huán)，穿過(guò)e一次。如果一個(gè)圖的對(duì)偶圖就是它自己，則稱(chēng)為自對(duì)偶圖。9/21/202242離散數(shù)學(xué)對(duì)偶圖的構(gòu)造對(duì)偶圖的構(gòu)造：在G的每個(gè)面內(nèi)放一個(gè)頂點(diǎn) f*，這對(duì)偶圖的舉例自對(duì)偶圖9/21/202243離散數(shù)學(xué)對(duì)偶圖的舉例自對(duì)偶圖9/21/202245離散數(shù)學(xué)G與G*的關(guān)系對(duì)任何一個(gè)平面圖G，G*是唯一確定的：p(G)* = r(G) , q(G*) = q(G) ;G*中的頂點(diǎn) f* 和 g*

25、 鄰接當(dāng)且僅當(dāng)G中與 f* 和 g*對(duì)應(yīng)的兩個(gè)面 f 和 g 鄰接；G*有多重邊當(dāng)且僅當(dāng)G的某兩個(gè)面至少有兩條公共邊；G*有環(huán)當(dāng)且僅當(dāng)G中有割邊?？蓪?duì)平面圖G的面著色轉(zhuǎn)換為對(duì)其對(duì)偶圖G*的點(diǎn)著色問(wèn)題：(G*) = *(G)。9/21/202244離散數(shù)學(xué)G與G*的關(guān)系對(duì)任何一個(gè)平面圖G，G*是唯一確定的：9/21四色問(wèn)題定理11.4.1：所有平面圖都是4面可著色的當(dāng)且僅當(dāng)所有平面圖都是4可著色的.與四色問(wèn)題等價(jià)的問(wèn)題：對(duì)一個(gè)簡(jiǎn)單平面圖G，是否(G) 4 ? 1976年 ,美國(guó)的Appel, Haken, Koch 借助計(jì)算機(jī)證明了四色問(wèn)題.9/21/202245離散數(shù)學(xué)四色問(wèn)題定理11.4.1：所有平面圖都是4面可著色的當(dāng)且僅當(dāng)五色問(wèn)題(一)定理11.4.2 (Headhood ,1890)：對(duì)任何平面圖G,(G) 5 .證明：對(duì)頂點(diǎn)數(shù)p作歸納證明 。 歸納基礎(chǔ)：當(dāng)p 5時(shí)，結(jié)論顯然成立。 歸納步驟：假設(shè)對(duì)所有頂點(diǎn)數(shù)小于 p 的平面圖，結(jié)論成立。設(shè)G為p+1個(gè)頂點(diǎn)的平面圖，由推論11