離散數(shù)學(xué)第十七章平面圖課件

第十七章平面圖本章的主要內(nèi)容平面圖的基本概念平面圖的判斷平面圖的對偶圖1引言許多實際問題可以抽象為這樣的模式：在一些表示客體的結(jié)點之間“布線”、“建通道”，以建立它們之間的某些聯(lián)系，要求這些“線”、“通道”在一個平面上而又不相互交疊。這正是本章要討論的圖論問題。例如，要在三個工作點A,B,C和三個原料庫L,M,N之間建立各工作點到原料庫的傳輸線，問是否可能使這些線路互不相交？如果用結(jié)點表示工作站，用邊表示傳輸線，那么上述問題便可描述為：K3,3是否可以在一個平面上圖示出來，使圖中各邊除端點外均不相交？另外，印刷電路板上的布線與交通道路的設(shè)計等都是此類問題。為了深入討論這個問題，需要引入平面圖的概念。2在圖中，(2)是(1)的平面嵌入，(4)是(3)的平面嵌入.17.1平面圖的基本概念定義17.1

(1)G可嵌入曲面S——若能將G除頂點外無邊相交地畫在S上(2)G是可平面圖或平面圖——G可嵌入平面(3)平面嵌入——畫出的無邊相交的平面圖(4)非平面圖——無平面嵌入的無向圖

(1)(2)(3)(4)3平面圖(平面嵌入)的面與次數(shù)定義17.2(1)G的面——由G的平面嵌入的邊將平面化分成的區(qū)域(2)無限面或外部面——（可用R0表示）——面積無限的面(3)有限面或內(nèi)部面（可用R1,R2,…,Rk等表示）——面積有限的面(4)面Ri的邊界——包圍Ri的回路組(5)面Ri的次數(shù)——Ri邊界的長度，用deg(Ri)表示5定理17.4平面圖各面次數(shù)之和等于邊數(shù)的兩倍.幾點說明若平面圖G有k個面，可籠統(tǒng)地用R1,R2,…,Rk表示，不需要指出外部面.定義17.2(4)中回路組是指：邊界可能是初級回路(圈)，可能是簡單回路，也可能是復(fù)雜回路.特別地，還可能是非連通的回路之并.平面圖有4個面，deg(R1)=1,deg(R2)=3,deg(R3)=2,deg(R0)=8.請寫各面的邊界.

6極大平面圖定義17.3若在簡單平面圖G中的任意兩個不相鄰的頂點之間加一條新邊所得圖為非平面圖，則稱G為極大平面圖.注意：若簡單平面圖G中已無不相鄰頂點，G顯然是極大平面圖，如K1(平凡圖),K2,K3,K4都是極大平面圖.極大平面圖的主要性質(zhì)定理17.5極大平面圖是連通的.證明線索：否則，加新邊不破壞平面性定理17.6

n（n3）階極大平面圖中不可能有割點和橋.證明線索：由定理17.5及n3可知，G中若有橋，則一定有割點，因而只需證無割點即可.方法還是反證法.7定理17.7中的條件也是極大平面圖的充分條件.定理17.7

設(shè)G為n(n3)階平面圖，且每個面的次數(shù)均為3，則G為極大平面圖.定理的應(yīng)用上圖中，只有(3)為極大平面圖

(1)(2)(3)9極小非平面圖定義17.4若在非平面圖G中任意刪除一條邊，所得圖G為平面圖，則稱G為極小非平面圖.由定義不難看出：(1)K5,K3,3都是極小非平面圖(2)極小非平面圖必為簡單圖圖中所示各圖都是極小非平面圖.10定理17.9（歐拉公式的推廣）設(shè)G是具有k（k2）個連通分支的平面圖，則nm+r=k+1證明中對各連通分支用歐拉公式，并注意即可.17.2歐拉公式定理17.8設(shè)G為n階m條邊r個面的連通平面圖，則nm+r=2（此公式稱為歐拉公式）證對邊數(shù)m做歸納法m=0，G為平凡圖，結(jié)論為真.設(shè)m=k（k1）結(jié)論為真，m=k+1時分情況討論.(1)G中無圈，則G為樹，刪除一片樹葉，用歸納假設(shè).(2)否則，在某一個圈上刪除一條邊，進(jìn)行討論.11定理17.12設(shè)G為n（n3）階m條邊的簡單平面圖，則m3n6.證設(shè)G有k（k1）個連通分支，若G為樹或森林，當(dāng)n3時，m3n6為真.否則G中含圈，每個面至少由l（l3）條邊圍成，又定理17.13

設(shè)G為n（n3）階m條邊的極大平面圖，則m=3n6.證由定理17.4,歐拉公式及定理17.7所證.定理17.14設(shè)G為簡單平面圖，則(G)5.證階數(shù)n6，結(jié)論為真.當(dāng)n7時，用反證法.否則會推出2m6n

m3n，這與定理17.12矛盾.與歐拉公式有關(guān)的定理在l=3達(dá)到最大值，由定理17.11可知m3n6.1317.3平面圖的判斷1.插入2度頂點和消去2度頂點定義17.5(1)消去2度頂點v，見下圖中，由(1)到(2)(2)插入2度頂點v，見下圖中，從(2)到(1).

(1)(2)142.收縮邊e，見下圖所示.3.圖之間的同胚定義17.6若G1G2，或經(jīng)過反復(fù)插入或消去2度頂點后所得G1G2，則稱G1與G2同胚.圖的同胚右邊兩個圖同胚1517.4平面圖的對偶圖定義17.7設(shè)G是某平面圖的某個平面嵌入，構(gòu)造G的對偶圖G*如下：(1)在G的面Ri中放置G*的頂點v*i.(2)設(shè)e為G的任意一條邊.若e在G的面Ri與Rj的公共邊界上，做G*的邊e*與e相交，且e*關(guān)聯(lián)G*的位于Ri與Rj中的頂點v*i與v*j，即

e*=(v*i,v*j)，e*不與其它任何邊相交.若e為G中的橋且在面Ri的邊界上，則e*是以Ri中G*的頂點v*i為端點的環(huán)，即e*=(v*i,v*i).17下面兩圖中，實線邊圖為平面圖，虛線邊圖為其對偶圖.

實例18G的對偶圖G*有以下性質(zhì)：(1)G*是平面圖，而且是平面嵌入.(2)G*是連通圖(3)若邊e為G中的環(huán)，則G*與e對應(yīng)的邊e*為橋，若e為橋，則G*中與e對應(yīng)的邊e*為環(huán).(4)在多數(shù)情況下，G*為多重圖（含平行邊的圖）.(5)同構(gòu)的平面圖（平面嵌入）的對偶圖不一定是同構(gòu)的.如上面的例子.對偶圖的性質(zhì)19平面圖與對偶圖的

階數(shù)、邊數(shù)與面數(shù)之間的關(guān)系定理17.18設(shè)G*是具有k（k2）個連通分支的平面圖G的對偶圖，則(1)n*=r(2)m*=m(3)r*=nk+1(4)設(shè)G*的頂點v*i位于G的面Ri中，則dG*(v*i)=deg(Ri)其中n*,m*,r*,n,m,r同定理17.17.證明(3)時應(yīng)同時應(yīng)用歐拉公式及歐拉公式的推廣.21自對偶圖定義17.8設(shè)G*是平面圖G的對偶圖，若G*G，則稱G為自對偶圖.輪圖定義如下：在n1（n4）邊形Cn1內(nèi)放置1個頂點，使這個頂點與Cn1上的所有的頂點均相鄰.所得n階簡單圖稱為n階輪圖.n為奇數(shù)的輪圖稱為奇階輪圖，n為偶數(shù)的輪圖稱為偶階輪圖，常將n階輪圖記為Wn.輪圖都是自對偶圖.圖中給出了W6和W7.請畫出它們的對偶圖，從而說明它們都是自對偶圖.22第十七章習(xí)題課主要內(nèi)容平面圖的基本概念歐拉公式平面圖的判斷平面圖的對偶圖基本要求深刻理解本部分的基本概念：平面圖、平面嵌入、面、次數(shù)、極大平面圖、極小非平面圖、對偶圖牢記極大平面圖的主要性質(zhì)和判別方法熟記歐拉公式及推廣形式，并能用歐拉公式及推廣形式證明有關(guān)定理與命題會用庫拉圖斯基定理證明某些圖不是平面圖

記住平面圖與它的對偶圖階數(shù)、邊數(shù)、面數(shù)之間的關(guān)系232.設(shè)G是階數(shù)n11的無向平面圖，證明G和不可能全是平面圖.證

只需證明G和中至少有一個是非平面圖.采用反證法.否則與G都是平面圖，下面來推出矛盾.G與的邊數(shù)m,m應(yīng)滿足(Kn的邊數(shù))

①由鴿巢原理知m或m，不妨設(shè)m，

②又由定理17.12知m

3n6③由②與③得