[可平面性]一個(gè)圖G=(V,E)，若能將其畫在平面上，且任意兩條邊的交點(diǎn)只能是G的頂點(diǎn)，則稱G可嵌入平面，或稱G是可平面的。可平面圖在平面上的一個(gè)嵌入稱為一個(gè)平面圖。樹是一類重要的平面圖。應(yīng)用舉例：印刷電路版、集成電路設(shè)計(jì)。5.1平面圖及其性質(zhì)[可平面性]一個(gè)圖G=(V,E)，若能將其畫在平面上，[區(qū)域]由平面圖的邊包圍而成，其中不含圖的頂點(diǎn)。也稱為面。包圍域R的所有邊組成的回路稱為該域的邊界，回路長度稱為該域的度，記為deg(R)。5.1平面圖及其性質(zhì)v2R1R2R0v1v3v4v5v6v7各域的邊界：R0:v1v2v4v5v7v7v4v3v1R1:v1v2v4v3v1R2:v4v5v7v4v6v4R3:v7v7[例]deg(R0)=8,deg(R1)=4,deg(R2)=5,deg(R3)=1R3[區(qū)域]由平面圖的邊包圍而成，其中不含圖的頂點(diǎn)。也稱為面。[內(nèi)部面和外部面]由平面圖的邊包圍且無窮大的域稱為外部面。（如上例的域R0為外部面）一個(gè)平面圖有且只有一個(gè)外部面。[曲面嵌入]一個(gè)圖可嵌入平面當(dāng)且僅當(dāng)它可嵌入曲面.5.1平面圖及其性質(zhì)[定理5-1-1]平面圖G的所有域的度之和等于其邊數(shù)m的2倍，即：[內(nèi)部面和外部面]由平面圖的邊包圍且無窮大的域稱為外部面。[定理5-1-2歐拉公式]設(shè)平面連通圖G有n個(gè)頂點(diǎn)，m條邊，d個(gè)域，則有n-m+d=2。[證明1]對(duì)m作歸納。[證明2]對(duì)d作歸納。歐拉公式對(duì)非簡單圖仍然成立。[推論]設(shè)平面圖G的連通分支數(shù)為k，并有n個(gè)頂點(diǎn)，m條邊，d個(gè)域，則有n-m+d=k+1。5.1平面圖及其性質(zhì)[定理5-1-2歐拉公式]設(shè)平面連通圖G有n個(gè)頂點(diǎn)，m條[極大平面圖]設(shè)G=(V,E)為簡單平面圖，|V|3，若對(duì)任意vi,vjV，且(vi,vj)E，有G=(V,E{(vi,vj)})為非平面圖，則稱G為一個(gè)極大平面圖?！皹O大性”乃針對(duì)固定頂點(diǎn)數(shù)的圖的邊的數(shù)目而言。5.1平面圖及其性質(zhì)[極大平面圖]設(shè)G=(V,E)為簡單平面圖，|V|3，若[極大平面圖的性質(zhì)]極大平面圖是連通圖。極大平面圖的每個(gè)面都由3條邊組成。極大平面圖有3d=2m（d為面數(shù)目，m為邊數(shù)目）。極大平面圖G=(V,E)，若|V|4，則viV，有deg(vi)3。[證明]5.1平面圖及其性質(zhì)[極大平面圖的性質(zhì)]5.1平面圖及其性質(zhì)[定理5-1-3]設(shè)極大平面圖G有n個(gè)頂點(diǎn)，m條邊，d個(gè)域，則有m=3n-6，d=2n-4。[證明]將3d=2m代入歐拉公式。[推論]簡單平面圖G有m

3n-6，d

2n-4。[定理5-1-4]簡單平面圖至少有一個(gè)頂點(diǎn)的度小于6。[證明]

設(shè)任一點(diǎn)的度6，得m3n，矛盾。5.1平面圖及其性質(zhì)[定理5-1-3]設(shè)極大平面圖G有n個(gè)頂點(diǎn)，m條邊，d個(gè)域[二部圖]圖G=(V,E)，若V可劃分成V1和V2

兩部分，使得：①v1V1，若(

v1,v2)E，則必v2V2;

②v2V2，若(

v1,v2)E，則必v1V1。則稱G為一個(gè)二部圖。5.1平面圖及其性質(zhì)[例][二部圖]圖G=(V,E)，若V可劃分成V1和V2兩部[完全二部圖]設(shè)G=(V,E)為一個(gè)二部圖，V1和V2

如上所述，若(v1

)(v2)(v1V1,v2V2

(

v1,v2

)E)，則稱G為一個(gè)完全二部圖，記為Kn1,n2。(n1=|V1|，n2=|V2

|)5.1平面圖及其性質(zhì)[例]

K3,3[完全二部圖]設(shè)G=(V,E)為一個(gè)二部圖，V1和V2[定理5-1-5]K5和K3,3是不可平面的。[證明]反證法并由歐拉公式導(dǎo)出矛盾.K5和K3,3稱為基本的不可平面圖，或Kuratowski

圖。K5K3,35.1平面圖及其性質(zhì)[定理5-1-5]K5和K3,3是不可平面的。K5和[串聯(lián)邊]圖G=(V,E)，若e1=(u1,u2)，e2=(u2,u3)，且deg(u2)=2，則稱e1與e2串聯(lián)。e1e2u1u2u35.2Kuratowski定理[例][串聯(lián)邊]圖G=(V,E)，若e1=(u1,u2)[串聯(lián)邊置換]

將上述e1,e2置換成e3=(u1,u3)，并消去可能的多重邊的過程，稱為串聯(lián)邊置換。e1e2u1u2u3e3u1u3u1u3e3e1e2u1u2u3e3u1u3e35.2Kuratowski定理[串聯(lián)邊置換]將上述e1,e2置換成e3=(u1,[同胚]設(shè)無向圖G和G，若存在G，使得G和G分別經(jīng)若干串聯(lián)邊置換后與G同構(gòu)，則稱G和G同胚.與K5同胚的圖，稱為K(1)型圖；與K3,3同胚的圖，稱為K(2)型圖；K(1)型圖和K(2)型圖統(tǒng)稱K型圖。[定理5-2-1(Kuratowski)]圖G=(V,E)可平面當(dāng)且僅當(dāng)G中不存在任何K型子圖。(證略)Kuratowski定理的實(shí)際應(yīng)用較為困難。5.2Kuratowski定理[同胚]設(shè)無向圖G和G，若存在G，使得G和G分別[例]Petersen圖不是平面圖。5.2Kuratowski定理AAABBBK3,3[例]Petersen圖不是平面圖。5.2Kurato[平面性等價(jià)圖]

圖G=(V,E)，滿足下列條件之一的圖G*=(V*,E*)稱為圖G的平面性等價(jià)圖：G是不連通圖，在G的兩個(gè)連通分支之間增加一條邊得到G*;對(duì)G中存在割點(diǎn)v，將G從v處分割得到由若干連通分支構(gòu)成的G*；對(duì)G作串聯(lián)邊置換得到G*;從G中移去自環(huán)得到G*；從G中移去多重邊得到G*。5.3圖的平面性檢測[平面性等價(jià)圖]圖G=(V,E)，滿足下列條件之一的圖G[平面性的不完全判定]

圖G*=(V*,E*)，n=|V|，m=|E|，則當(dāng)n<5，或n>=5且m<9時(shí)，G是可平面的；當(dāng)m>3n-6，G是不可平面的；[平面性檢測的DMP算法]

戴書P755.3圖的平面性檢測[平面性的不完全判定]圖G*=(V*,E*)，n=|V|[對(duì)偶圖]

圖G=(V,E)，滿足下列條件的圖G*=(V*,E*)稱為圖G的對(duì)偶圖：G的任一域fi

內(nèi)有且僅有一點(diǎn)vi*;對(duì)G的域fi,fj的共同邊界ek，畫一條ek*=(vi*

,vj*

)且只與ek交于一點(diǎn)；若ek完全處于fi中，則vi*有一自環(huán)ek*且與ek相交與一點(diǎn)。上述過程稱為求對(duì)偶圖的D過程，得到的對(duì)偶圖稱為原圖的拓?fù)鋵?duì)偶。5.4對(duì)偶圖[對(duì)偶圖]圖G=(V,E)，滿足下列條件的圖G*=(V對(duì)平面圖G，D過程構(gòu)造的G*是唯一的；對(duì)于非平面圖，D過程可能不成立；對(duì)平面圖G，D過程構(gòu)造的G*也是平面圖；不論圖G是否連通，D過程得到的G*是連通的；若圖G連通，且存在G*，則(G*)*=G；對(duì)圖G，若存在G*，則G中回路相對(duì)應(yīng)于G*中割集，G中割集相對(duì)應(yīng)于G*中回路；若GG*，稱G為一個(gè)自對(duì)偶圖。5.4對(duì)偶圖對(duì)平面圖G，D過程構(gòu)造的G*是唯一的；對(duì)于非平面圖，D過程[定理5-4-1(Whitney)]圖G有對(duì)偶圖當(dāng)且僅當(dāng)G是平面圖。[證明]

在平面圖上施行D過程即得。反證：設(shè)G有對(duì)偶G*且G不是平圖。由

Kuratowski

定理，此時(shí)G中含有K型子圖。只需證明K(1)型圖和K(2)型圖，或K5和K3,3都沒有對(duì)偶即引起矛盾。5.4對(duì)偶圖[定理5-4-1(Whitney)]圖G有對(duì)偶圖當(dāng)且僅當(dāng)G[定理5-4-2]

對(duì)圖G施行D過程得到G*，設(shè)n,m,d和n*,m*,d*分別表示G和G*的結(jié)點(diǎn)數(shù)、邊數(shù)及域數(shù)，則有：

m*=m,n*=d,deg(vi*)=deg(fi)[證明]由D過程直接得到。5.4對(duì)偶圖[定理5-4-2]對(duì)圖G施行D過程得到G*，設(shè)n,m,[定理5-4-3]

設(shè)G為平面圖，施行D過程得到G*，設(shè)n,m,d和n*,m*