CHAP11平面圖教學(xué)講解教學(xué)課件

圖中的邊不要交叉實際中的很多問題都涉及到一個圖中的邊是否會交叉的問題。例如：單面印刷電路板，集成電路的布線，交通設(shè)計問題；等等。由此便抽象出平面圖的概念：沒有交叉(這里當(dāng)然不是指在端點處的相互鄰接）的邊的圖。一個有交叉的邊的圖能不能轉(zhuǎn)換成與之同構(gòu)的平面圖，顯然是人們所關(guān)注的問題。本章就是介紹平面圖以及平面圖的性質(zhì)。7/20/20231離散數(shù)學(xué)§11.1平面圖的概念7/20/20232離散數(shù)學(xué)平面圖定義11.1.1：設(shè)G是平面上由有限個點及以這些點為端點的有限連續(xù)曲線所組成的圖形，如果G中任意兩條線最多只在它們的端點處相交，稱G為平面圖。例1，⑴圖不是平面圖，⑵和⑶是平面圖。⑴⑵⑶7/20/20233離散數(shù)學(xué)可平面圖上例中的圖⑴雖然不是平面圖，但是卻和圖⑵和圖⑶是同構(gòu)的，這樣的圖稱為可平面圖?？善矫鎴D：如果一個圖G與一個平面圖H同構(gòu)，稱G是可平面圖；而稱H是G的一個平面嵌入。上例中的圖⑴是可平面圖，圖⑵和圖⑶是圖⑴的兩個平面嵌入。7/20/20234離散數(shù)學(xué)平面圖的面定義11.1.2：設(shè)G是一個平面圖，平面被G的邊所圍成的區(qū)域稱為面，這些邊稱為該面的邊界；其中有限區(qū)域?qū)?yīng)的面稱為內(nèi)部面，無限區(qū)域?qū)?yīng)的面稱為外部面(用f0表示)。用G(p,q,r)表示一個p個頂點，q條邊以及r個面的平面圖。一個面f所包含的邊數(shù)稱為f的次數(shù)，記為d(f)，若邊為割邊，則計算兩次。7/20/20235離散數(shù)學(xué)計算下圖中各面的次數(shù)：d(f0)=3;d(f1)=5。2431f1f0(a)f1f0(b)f2d(f0)=8;d(f1)=3;d(f2)=3.7/20/20236離散數(shù)學(xué)面的總次數(shù)為邊數(shù)的兩倍定理11.1.1：對任何平面圖G(p,q,r),有d(fi)=2q,(i=1,2,,r).證明：由于G的每條非割邊恰屬于兩個面，所以，在計算這兩個面的次數(shù)時，該邊計算兩次，而割邊只屬于一個面，但由規(guī)定也計算了兩次，故上式成立，即所有面的總次數(shù)為邊數(shù)的兩倍。對比：d(vi)=2q，(i=1,2,,p)，即所有頂點的總度數(shù)為邊數(shù)的二倍。7/20/20237離散數(shù)學(xué)平面圖的同構(gòu)定義11.1.3：設(shè)G和H是兩個平面圖。如果并且f是G中一個由途徑uvwu圍成的面當(dāng)且僅當(dāng)(u)(v)(w)(u)圍成H的一個面f’,則稱G與H同構(gòu)。有時可省略。例1中圖⑵與圖⑶就是平面圖同構(gòu)。7/20/20238離散數(shù)學(xué)圖的同構(gòu)與平面圖的同構(gòu)如果兩個圖是平面圖同構(gòu)，則必是兩個同構(gòu)的圖?？墒莾蓚€同構(gòu)的圖不一定是平面圖同構(gòu)。例1中圖⑴與圖⑵和圖⑶是同構(gòu)的圖，但圖⑴卻不是平面圖，因而不可能和它們平面圖同構(gòu)。下面兩個平面圖是圖同構(gòu)，但不是平面圖同構(gòu)：GH1’3’4’5’1234566’2’7/20/20239離散數(shù)學(xué)外平面圖定義11.1.4：圖G稱為外可平面圖，如果它有一個平面嵌入H，使得G的所有頂點均在H的同一個面的邊界上，這時，稱H為外平面圖。f1f1這是外平面圖這不是外平面圖這是外可平面圖7/20/202310離散數(shù)學(xué)極大平面圖定義11.1.5設(shè)G是一個可平面圖，如果對G中任意兩個互不鄰接的頂點u,v,G+uv成為一個不可平面圖，則稱G是一個極大可平面圖，極大可平面圖的一個平面嵌入稱為極大平面圖。說明：對一個不是極大的可平面圖，可以添加一些邊以得到一個極大可平面圖。(如圖)7/20/202311離散數(shù)學(xué)G是極大平面圖當(dāng)且僅當(dāng)G的每個面都是三角形(必要性)極大簡單平面圖的任何一個面都是三角形K3。證明：(反證)設(shè)G是極大簡單平面圖。若G的某個面f不是K3，不妨設(shè)f由閉途徑v1v2vnv1圍成，且d(f)=n4。為簡單起見，不妨設(shè)n=4，即f由閉途徑v1v2v3v4v1圍成。則f只有以下三種情況：⑴v1與v3不鄰接；⑵v1與v3鄰接，而v2與v4不鄰接；⑶v1與v3鄰接，而v2與v4也鄰接。下面我們對這三種情況分別予以討論：7/20/202312離散數(shù)學(xué)極大平面圖的面都是三角形證明：…⑴若v1與v3不鄰接，則v1v2v3v4v1所圍成內(nèi)部面，v1v2v3v4于是在該面內(nèi)聯(lián)結(jié)v1和v3不破壞G的平面性，此與G的假設(shè)矛盾；⑵若v1與v3鄰接，v2與v4不鄰接，則v1v2v3v1圍成內(nèi)部面，邊v1v4及頂點v4必在此面的外部，v1v2v3v4故聯(lián)結(jié)v2和v4不破壞G的平面性，此與G的假設(shè)矛盾；7/20/202313離散數(shù)學(xué)極大平面圖的面都是三角形證明：…⑶若v1與v3鄰接，且v2與v4鄰接，則v1v2v3v4v1所圍成的區(qū)域是內(nèi)部面。因此邊v1v3，v2v4都在此面之外，因而必相交,此與G的可平面性矛盾。v1v2v3v4綜合以上，知結(jié)論成立。7/20/202314離散數(shù)學(xué)(充分性)若平面圖G的每個面都是三角形，

則是G是極大平面圖。證明：設(shè)平面圖G的每個面都是K3，若G不是極大平面圖.則G中存在u、vV(G)，使得uvE(G)，且G+uv仍為平面圖。設(shè)uv是G+uv中兩個面fi和fj的公共邊界.于是，G中fi和fj的面是一個面fk，顯然，d(fk)3,由此G與的每個面是K3矛盾！7/20/202315離散數(shù)學(xué)§11.2歐拉公式7/20/202316離散數(shù)學(xué)歐拉公式定理:對任何一個簡單平面圖G(p,q,r)均滿足：p–q+r=2.證明：對面數(shù)r作歸納證明。當(dāng)r=1時，G是樹，此時q=p–1，結(jié)論成立。假設(shè)對G(p,q,r-1)，r2，結(jié)論成立，設(shè)G是有r個面的平面圖，G至少有一條回路。設(shè)e是某回路上的邊，G–e仍是連通平面圖，它有p個頂點，q–1條邊和r–1個面，由歸納假設(shè)有，p–(q–1)+(r–1)=2。整理即得p–q+r=2。由歸納法原理，歐拉公式成立。7/20/202317離散數(shù)學(xué)面等次平面圖中邊與點的關(guān)系推論11.2.1：若簡單平面圖G(p,q,r)的每個面的次數(shù)均為m,則

q=m(p–2)/(m–2)證明：由定理11.1.1，2q=d(fi)=mr，解出r，代入歐拉公式,得p–q+(2/m)q=2整理上式即得證。7/20/202318離散數(shù)學(xué)簡單平面圖邊數(shù)的上界推論11.2.2對任何簡單平面圖G(p,q,r)(p3),q3p–6.證明：由于極大簡單平面圖的每個面都是K3,故將m=3代入推論11.2.1中的式q=m(p–2)/(m–2)

有q=3(p–2)=3p–6.故對一般簡單平面圖有q3p–6.7/20/202319離散數(shù)學(xué)K5是不可平面圖推論11.2.3K5是不可平面圖。證明：若K5是可平面圖，則由推論11.2.2知q3p–6，于是10=q3p–6=35–6=9,即：109，矛盾。故結(jié)論成立。7/20/202320離散數(shù)學(xué)無3次面的平面圖邊數(shù)的上界推論11.2.4：若簡單平面圖G(p,q,r)的每個面均不是K3，則q2p–4.證明：由假設(shè)每個面的次數(shù)至少不小于4

2q=d(fi)4r即rq/2,從而由歐拉公式有2=p–q+rp–q+q/2=p–q/2

整理后得q2p–4.7/20/202321離散數(shù)學(xué)K3,3是不可平面圖推論11.2.5：K3,3是不可平面圖。證明：因K3,3是二分圖，故它不含K3，假設(shè)K3,3是可平面圖，則由推論11.2.4知9=q2p–4=26–4=8,即：98，矛盾。故結(jié)論成立。7/20/202322離散數(shù)學(xué)簡單平面圖的最小度小于6推論11.2.6：任何簡單平面圖G(p,q,r)均有(G)

＜6。證明：若(G)6，則q=(1/2)d(vi)(2q=d(vi))(1/2)p(G)(6/2)p>3p–6,此與推論11.2.2(對任何簡單平面圖G(p,q,r)(p3)，都有q3p–6)矛盾。故結(jié)論成立。7/20/202323離散數(shù)學(xué)極大平面圖的五個性質(zhì)定理11.2.2：設(shè)簡單平面圖G(p,q,r)是極大平面圖(p4)，于是①q=3p–6;②r=2p–4;

④(G)3;⑤G中至少有4個頂點的度不超過5.7/20/202324離散數(shù)學(xué)極大平面圖的邊數(shù)證明：由定理11.1.2(極大簡單平面圖的任何一個面都是三角形K3)，將推論11.2.1中的式q=m(p–2)/(m–2)中的m用m=3代入，即可得q=3p–6;7/20/202325離散數(shù)學(xué)極大平面圖的面數(shù)證明：由性質(zhì)①有q=3p–6，將其代入歐拉公式得：

p–q+r=p–(3p–6)+r=2,

整理即得r=2p–4；7/20/202326離散數(shù)學(xué)極大平面圖連通度不小于3證明：∵G的面都是K3，∴(G)2。假設(shè)(G)=2，則有頂點割S={u,v}。其中的u和v都應(yīng)該與G–S的至少兩個連通分支中的頂點在G中鄰接。不妨設(shè)在G的一個平面嵌入G中與u鄰接的點按環(huán)繞u的順序依次為u1,,ut。而u1,,ut中除可能有一點是v外，其余的點分別屬于G–S的至少兩個分支，必有兩點ui和ui+1分屬G–S的兩個不同分支。7/20/202327離散數(shù)學(xué)極大平面圖連通度不小于3證明：…S是頂點割，…ui和ui+1分別屬于G–S的兩個不同分支。uvui+1uif1由ui和ui+1的取法可知，在uui和uui+1之間沒有其它與u鄰接的邊，依據(jù)定理11.1.2，在G中uuiui+1是一個K3面，故ui和ui+1鄰接。從而在G–S中，ui也和ui+1鄰接，這與S是頂點割相矛盾。所以(G)3。7/20/202328離散數(shù)學(xué)極大平面圖最小度不小于3證明：由定理7.1.1可知圖的連通度不大于邊連通度，而邊連通度又不大于最小度，即(G)(G)(G)；又由性質(zhì)③即可得極大平面圖最小度不小于3，即(G)(G)3。7/20/202329離散數(shù)學(xué)至少有4個頂點的度不超過5證明：設(shè)G的頂點集V={v1,v2,,vp}。

若對i=1,2,,p–3，均有d(vi)6，則由性質(zhì)④，對i=p–2,p–1,

p，有d(vi)(G)3。

于是，6p–21=2q–9？因為由性質(zhì)①，q=3p–6，于是6p–12=2q2q–d(vj)(這里j=p–2,p-1,p)=d(vi)(這里i=1,2,,p–3)6(p–3)=6p–18.此為矛盾，故結(jié)論成立。習(xí)題7/20/202330離散數(shù)學(xué)§11.3可平面性判定7/20/202331離散數(shù)學(xué)剖分圖定義11.3.1：設(shè)G是一個圖，e=uv∈E(G)，在G–uv中增加一個新點w及邊wu,wv.稱此過程為對圖G的一次剖分運算。如果H是由G經(jīng)過有限次剖分運算得到的，則稱H是G的剖分圖。直觀地說，剖分就是在圖的某邊上加個頂點。右邊就是K4的剖分。7/20/202332離散數(shù)學(xué)可平面圖的充要條件定理11.3.1(Kuratowski定理)一個圖是可平面圖的充分必要條件是它不包含K5或K3,3的剖分圖.該定理亦可描述為：一個圖是可平面的當(dāng)且僅當(dāng)它沒有一個可以收縮到K5或K3,3的子圖。7/20/202333離散數(shù)學(xué)Petersen圖的收縮和剖分Petersen圖例如：Petersen圖不是可平面圖，因為它含有K3,3的剖分。Petersen圖含有K3,3的剖分Petersen圖收縮為K5它也可以收縮為K5。7/20/202334離散數(shù)學(xué)§11.4平面圖的面著色7/20/202335離散數(shù)學(xué)給平面圖著色對簡單圖G(p,q)只考慮頂點和邊，其著色也只有點著色和邊著色。對簡單平面圖G(p,q,r)則還需要考慮面，其著色還由相應(yīng)的面著色。平面圖著色的一個直接的重要的應(yīng)用:地圖著色

。用顏色來區(qū)分地圖中的區(qū)域，需要多少種顏色呢？這就是著名的四色問題。7/20/202336離散數(shù)學(xué)面的鄰接定義1.4.1：設(shè)f1和f2是平面圖G的兩個面。若f1和f2的邊界至少有一條公共邊，則稱f1與f2是鄰接的，否則稱f1與f2不鄰接。三種鄰接：⑴點鄰接：兩個頂點有邊相關(guān)聯(lián)；⑵邊鄰接：兩條邊有共同的端點；⑶面鄰接：兩個面有共同的邊。7/20/202337離散數(shù)學(xué)有公共頂點的面不是鄰接的面注意：兩個面如果在邊界上只有一個或有限個公共點，則它們是不鄰接的。如下左圖中的面A與E,A與C,A與D都不是鄰接的面。下右圖中的面A與C，B與D也都不是鄰接的面ABCDEFABCD7/20/202338離散數(shù)學(xué)面著色定義11.4.2：設(shè)G是平面圖，S={1,2,,k}，k1。若存在面集R(G)到S的滿射r，則稱r為G的k面著色，S為面色集。若對G中任意兩個鄰接面f1和f2

，均有r(f1)≠r(f2)，則稱r是正常k面著色，并稱G是k面可著色的。圖G的正常k面可著色中最小的k稱為G的面色數(shù)，記為*(G)

。對比：色數(shù)(G)

：最小正常k(頂點)著色；

邊色數(shù)’(G)

：最小正常k邊著色；面色數(shù)*(G)：最小正常k面著色。7/20/202339離散數(shù)學(xué)對偶圖如果把每個面看作一個頂點，若兩個面的邊界有一條公共邊，則看作兩個頂點之間有一條邊關(guān)聯(lián)。這樣就可以把一個平面圖G中面與面之間鄰接關(guān)系描述為另一個圖G*中頂點與頂點之間的鄰接關(guān)系。這樣對一個平面圖G進行轉(zhuǎn)換，所得到的圖G*稱為圖G的對偶圖于是可將對平面圖G的面著色轉(zhuǎn)換為對其對偶圖G*的點著色問題。7/20/202340離散數(shù)學(xué)對偶圖的構(gòu)造對偶圖的構(gòu)造：在G的每個面內(nèi)放一個頂點f*，這些頂點就構(gòu)成了G*的頂點集V(G*)。若G的兩個面f和g有一條公共邊e，則畫一條以f*和g*為端點的邊e*，e*僅穿過e一次，對于G中僅屬于一個面的割邊e，則畫一條以f*為端點的環(huán)，穿過e一次。如果一個圖的對偶圖就是它自己，則稱為自對偶圖。7/20/202341離散數(shù)學(xué)對偶圖的舉例自對偶圖7/20/202342離散數(shù)學(xué)G與G*的關(guān)系對任何一個平面圖G，G*是唯一確定的：p(G)*=r(G),q(G*)=q(G);G*中的頂點f*

和g*

鄰接當(dāng)且僅當(dāng)G中與f*

和g*對應(yīng)的兩個面f和g鄰接；G*有多重邊當(dāng)且僅當(dāng)G的某兩個面至少有兩條公共邊；G*有環(huán)當(dāng)且僅當(dāng)G中有割邊。可將對平面圖G的面著色轉(zhuǎn)換為對其對偶圖G*的點著色問題：(G*)=*(G)。7/20/202343離散數(shù)學(xué)四色問題定理11.4.1：所有平面圖都是4面可著色的當(dāng)且僅當(dāng)所有平面圖都是4可著色的.與四色問題等價的問題：對一個簡單平面圖G，是否(G)4?

1976年,美國的Appel,Haken,Koch借助計算機證明了四色問題.7/20/202344離散數(shù)學(xué)五色問題(一)定理11.4.2(Headhood,1890)：對任何平面圖G,(G)5.證明：對頂點數(shù)p作歸納證明。歸納基礎(chǔ)：當(dāng)p5時，結(jié)論顯然成立。歸納步驟：假設(shè)對所有頂點數(shù)小于p的平面圖，結(jié)論成立。設(shè)G為p+1個頂點的平面圖，由推論11.2.6,(G)

5。

考慮(p–1)階平面圖G–v，由歸納假設(shè)G–v有正常5著色。7/20/202345離散數(shù)學(xué)五色問題(二)證明：…G–v有正常5著色。若d(v)<5，則中至少