單擊此處編輯母版標(biāo)題樣式,*,第十七章 平面圖,引言,許多實(shí)際問(wèn)題可以抽象為這樣的模式：在一些表示客體的結(jié)點(diǎn)之間“布線”、“建通道”，以建立它們之間的某些聯(lián)系，要求這些“線”、“通道”在一個(gè)平面上而又不相互交疊。這正是本章要討論的圖論問(wèn)題。,例如，要在三個(gè)工作點(diǎn)A,B,C和三個(gè)原料庫(kù)L,M,N之間建立各工作點(diǎn)到原料庫(kù)的傳輸線，問(wèn)是否可能使這些線路互不相交？如果用結(jié)點(diǎn)表示工作站，用邊表示傳輸線，那么上述問(wèn)題便可描述為：K,3,3,是否可以在一個(gè)平面上圖示出來(lái)，使圖中各邊除端點(diǎn)外均不相交？另外，印刷電路板上的布線與交通道路的設(shè)計(jì)等都是此類(lèi)問(wèn)題。為了深入討論這個(gè)問(wèn)題，需要引入平面圖的概念。,在圖中，(2)是(1)的平面嵌入，(4)是(3)的平面嵌入.,17.1 平面圖,的基本概念,定義17.1,(1),G,可嵌入曲面,S,若能將,G,除頂點(diǎn)外無(wú)邊相交地畫(huà)在,S,上,(2),G,是,可平面圖,或,平面圖,G,可嵌入平面,(3),平面嵌入,畫(huà)出的無(wú)邊相交的平面圖,(4),非平面圖,無(wú)平面嵌入的無(wú)向圖,(1)(2)(3)(4),幾點(diǎn)說(shuō)明及一些簡(jiǎn)單結(jié)論,一般所談平面圖不一定是指平面嵌入，上圖中4個(gè)圖都是平,面圖，但討論某些性質(zhì)時(shí)，一定是指平面嵌入.,結(jié)論：,(1),K,5,K,3,3,都不是平面圖（待證）,(2)設(shè),G,G,，若,G,為平面圖，則,G,也是平面圖（定理17.1）,(3)設(shè),G,G,，若,G,為非平面圖，則,G,也是非平面圖（定理17.2），由此可知，,K,n,(,n,6)，,K,3,n,(,n,4)都是非平面圖.,(4)平行邊與環(huán)不影響平面性.,平面圖(平面嵌入)的面與次數(shù),定義17.2,(1),G,的,面,由,G,的平面嵌入的邊將平面化分成的區(qū)域,(2),無(wú)限面,或,外部面,（可用,R,0,表示）面積無(wú)限的面,(3),有限面,或,內(nèi)部面,（可用,R,1,R,2,R,k,等表示）面積,有限的面,(4),面,R,i,的邊界,包圍,R,i,的回路組,(5),面,R,i,的次數(shù),R,i,邊界的長(zhǎng)度，用deg(,R,i,)表示,定理17.4,平面圖各面次數(shù)之和等于邊數(shù)的兩倍.,幾點(diǎn)說(shuō)明,若平面圖,G,有,k,個(gè)面，可籠統(tǒng)地用,R,1,R,2,R,k,表示，不需要指出外部面,.,定義,17.2(4),中回路組是指：邊界可能是初級(jí)回路,(,圈,),，可能是簡(jiǎn)單回路，也可能是復(fù)雜回路,.,特別地，還可能是非連通的回路之并,.,平面圖有4個(gè)面，deg(,R,1,)=1,deg(,R,2,)=3,deg(,R,3,)=2,deg(,R,0,)=8.請(qǐng)寫(xiě)各面的邊界.,極大平面圖,定義17.3,若在簡(jiǎn)單平面圖,G,中的任意兩個(gè)不相鄰的頂點(diǎn)之間,加一條新邊所得圖為非平面圖，則稱(chēng),G,為,極大平面圖,.,注意：若簡(jiǎn)單平面圖,G,中已無(wú)不相鄰頂點(diǎn)，,G,顯然是極大平,面圖，如,K,1,(平凡圖),K,2,K,3,K,4,都是極大平面圖.,極大平面圖的主要性質(zhì),定理17.5,極大平面圖是連通的.,證明線索：否則，加新邊不破壞平面性,定理17.6,n,（,n,3）階極大平面圖中不可能有割點(diǎn)和橋.,證明線索：由定理17.5及,n,3可知，,G,中若有橋，則一定有割點(diǎn)，因而只需證無(wú)割點(diǎn)即可.方法還是反證法.,證明線索：,(1)由于,n,3,又,G,必為簡(jiǎn)單,平面圖可知，,G,每個(gè)面的,次數(shù)均,3.,(2)因?yàn)?G,為平面圖，又為極,大平面圖.可證,G,不可能,存在次數(shù)3的面.,就給出的圖討論即可.,極大平面圖的性質(zhì),定理17.7,設(shè),G,為,n,（,n,3,）階極大平面圖，則,G,的每個(gè)面的,次數(shù)均為3.,定理17.7中的條件也是極大平面圖的充分條件.,定理17.7,設(shè),G,為,n,(,n,3),階平面圖，且每個(gè)面的次數(shù)均為3，則,G,為極大平面圖.,定理的應(yīng)用,上圖中，只有,(3),為極大平面圖,(1)(2)(3),極小非平面圖,定義17.4,若在非平面圖,G,中任意刪除一條邊，所得圖,G,為平面圖，則稱(chēng),G,為,極小非平面圖,.,由定義不難看出：,(1),K,5,K,3,3,都是極小非平面圖,(2)極小非平面圖必為簡(jiǎn)單圖,圖中所示各圖都是極小非平面圖.,定理17.9,（歐拉公式的推廣）設(shè),G,是具有,k,（,k,2,）個(gè)連通分支的平面圖，則,n,m,+,r,=,k,+1,證明中對(duì)各連通分支用歐拉公式，并注意,即可.,17.2,歐拉公式,定理17.8,設(shè),G,為,n,階,m,條邊,r,個(gè)面的連通平面圖，則,n,m,+,r,=2,（此公式稱(chēng)為,歐拉公式,）,證 對(duì)邊數(shù),m,做歸納法,m,=0，,G,為平凡圖，結(jié)論為真.,設(shè),m,=,k,（,k,1,）結(jié)論為真，,m,=,k,+1時(shí)分情況討論.,(1),G,中無(wú)圈，則,G,為樹(shù)，刪除一片樹(shù)葉，用歸納假設(shè).,(2)否則，在某一個(gè)圈上刪除一條邊，進(jìn)行討論.,解得,定理17.11,在具有,k,（,k,2,）個(gè)連通分支的平面圖中，,與歐拉公式有關(guān)的定理,定理17.10,設(shè),G,為連通的平面圖，且deg(,Ri,),l,l,3,，則,證 由定理,17.4及,歐拉公式得,推論,K,5,K,3,3,不是平面圖.,定理17.12,設(shè),G,為,n,（,n,3,）階,m,條邊的簡(jiǎn)單平面圖，則,m,3,n,6.,證 設(shè),G,有,k,（,k,1,）個(gè)連通分支，若,G,為樹(shù)或森林，當(dāng),n,3,時(shí)，,m,3,n,6,為真.否則,G,中含圈，每個(gè)面至少由,l,（,l,3,）條邊圍成，又,定理17.13,設(shè),G,為,n,（,n,3,）階,m,條邊的極大平面圖，則,m,=3,n,6.,證 由定理17.4,歐拉公式及定理17.7所證.,定理17.14,設(shè),G,為簡(jiǎn)單平面圖，則,(,G,),5.,證 階數(shù),n,6,，結(jié)論為真.當(dāng),n,7,時(shí)，用反證法.否則會(huì)推出2,m,6,n,m,3,n,，這與定理17.12矛盾.,與歐拉公式有關(guān)的定理,在,l,=3達(dá)到最大值，由定理17.11可知,m,3,n,6.,17.3,平面圖的判斷,1.插入2度頂點(diǎn)和消去2度頂點(diǎn),定義17.5,(1)消去2度頂點(diǎn),v,，見(jiàn)下圖中，由(1)到(2),(2)插入2度頂點(diǎn),v,，見(jiàn)下圖中，從(2)到(1).,(1)(2),2.收縮邊,e,，見(jiàn)下圖所示.,3.,圖之間的同胚,定義17.6,若,G,1,G,2,，或經(jīng)過(guò)反復(fù)插入或消去2度頂點(diǎn)后所得,G,1,G,2,，則稱(chēng),G,1,與,G,2,同胚,.,圖的同胚,右邊兩個(gè)圖同胚,平面圖判定定理,定理17.15,G,是平面圖,G,中不含與,K,5,或,K,3,3,同胚的子圖.,定理17.16,G,是平面圖,G,中無(wú)可收縮為,K,5,或,K,3,3,的子圖,例,1,證明所示圖(1)與(2)均為非平面圖.,(1)(2),右圖(1),(2)分別為,原圖(1),(2)的子圖,與,K,3,3,K,5,同胚.,子圖 (1)(2),17.4,平面圖的對(duì)偶圖,定義17.7,設(shè),G,是某平面圖的某個(gè)平面嵌入，構(gòu)造,G,的對(duì)偶圖,G,*如下：,(1)在,G,的面,R,i,中放置,G,*的頂點(diǎn),v,*,i,.,(2)設(shè),e,為,G,的任意一條邊.,若,e,在,G,的面,R,i,與,R,j,的公共邊界上，做,G,*的邊,e,*與,e,相,交，且,e,*關(guān)聯(lián),G,*的位于,R,i,與,R,j,中的頂點(diǎn),v,*,i,與,v,*,j,，即,e,*=(,v,*,i,v,*,j,)，,e,*不與其它任何邊相交.,若,e,為,G,中的橋且在面,R,i,的邊界上，則,e,*是以,R,i,中,G,*的頂,點(diǎn),v,*,i,為端點(diǎn)的環(huán)，即,e,*=(,v,*,i,v,*,i,).,下面兩圖中，實(shí)線邊圖為平面圖，虛線邊圖為其對(duì)偶圖.,實(shí)例,G,的對(duì)偶圖,G,*有以下性質(zhì)：,(1),G,*是平面圖，而且是平面嵌入.,(2),G,*是連通圖,(3)若邊,e,為,G,中的環(huán)，則,G,*與,e,對(duì)應(yīng)的邊,e,*為橋，若,e,為橋，則,G,*中與,e,對(duì)應(yīng)的邊,e,*為環(huán).,(4)在多數(shù)情況下，,G,*為多重圖（含平行邊的圖）.,(5)同構(gòu)的平面圖（平面嵌入）的對(duì)偶圖不一定是同構(gòu)的.,如上面的例子.,對(duì)偶圖的性質(zhì),平面圖與對(duì)偶圖的階數(shù)、邊數(shù)與面數(shù)之間的關(guān)系,定理17.17,設(shè),G,*是連通平面圖,G,的對(duì)偶圖，,n,*,m,*,r,*和,n,m,r,分別為,G,*和,G,的頂點(diǎn)數(shù)、邊數(shù)和面數(shù)，則,(1),n,*=,r,(2),m,*=,m,(3),r,*=,n,(4)設(shè),G,*的頂點(diǎn),v,*,i,位于,G,的面,Ri,中，則,dG,*(,v,*,i,)=deg(,Ri,),證明線索,(1)、(2)平凡.,(3)應(yīng)用歐拉公式.,(4)的證明中注意，橋只能在某個(gè)面的邊界中，非橋邊在兩個(gè)面的邊界上.,平面圖與對(duì)偶圖的階數(shù)、邊數(shù)與面數(shù)之間的關(guān)系,定理17.18,設(shè),G,*是具有,k,（,k,2）個(gè)連通分支的平面圖,G,的對(duì),偶圖，則,(1),n,*=,r,(2),m,*=,m,(3),r,*=,n,k,+1,(4)設(shè),G,*的頂點(diǎn),v,*,i,位于,G,的面,Ri,中，則,dG,*(,v,*,i,)=deg(,Ri,),其中,n,*,m,*,r,*,n,m,r,同定理17.17.,證明(3)時(shí)應(yīng)同時(shí)應(yīng)用歐拉公式及歐拉公式的推廣.,自對(duì)偶圖,定義17.8,設(shè),G,*是平面圖,G,的對(duì)偶圖，若,G,*,G,，則稱(chēng),G,為,自,對(duì)偶圖,.,輪圖,定義如下：,在,n,1（,n,4）邊形,C,n,1,內(nèi)放置1個(gè)頂點(diǎn)，使這個(gè)頂點(diǎn)與,C,n,1,上的所有的頂點(diǎn)均相鄰.所得,n,階簡(jiǎn)單圖稱(chēng)為,n,階輪圖,.,n,為奇,數(shù)的輪圖稱(chēng)為,奇階輪圖,，,n,為偶數(shù)的輪圖稱(chēng)為,偶階輪圖,，常,將,n,階輪圖記為,W,n,.,輪圖都是自對(duì)偶圖.,圖中給出了,W,6,和,W,7,.,請(qǐng)畫(huà)出它們的對(duì)偶圖，,從而說(shuō)明它們都是自對(duì)偶圖.,第十七章 習(xí)題課,主要內(nèi)容,平面圖的基本概念,歐拉公式,平面圖的判斷,平面圖的對(duì)偶圖,基本要求,深刻理解本部分的基本概念：平面圖、平面嵌入、面、次數(shù)、極大平面圖、極小非平面圖、對(duì)偶圖,牢記極大平面圖的主要性質(zhì)和判別方法,熟記歐拉公式及推廣形式，并能用歐拉公式及推廣形式證明有關(guān)定理與命題,會(huì)用庫(kù)拉圖斯基定理證明某些圖不是平面圖,記住平面圖與它的對(duì)偶圖階數(shù)、邊數(shù)、面數(shù)之間的關(guān)系,練習(xí),1,解 設(shè),G,的階數(shù)、邊數(shù)、面數(shù)分別為,n,m,r,.,(1)否則，由歐拉公式得,2,m,5,r,=5(2+,m,n,),由于,(,G,),3及握手定理又有 2,m,3,n,由與得,m,30 ,又有,r,=2+,m,n,12 ,由及又可得,m,30 ,是矛盾的.,(2),正十二面體是一個(gè)反例,1.設(shè),G,是連通的簡(jiǎn)單的平面圖，面數(shù),r,12，,(,G,),3.,(1)證明,G,中存在次數(shù),4的面,(2)舉例說(shuō)明當(dāng),r,=12時(shí)，(1)中結(jié)論不真.,2.設(shè),G,是階數(shù),n,11,的無(wú)向平面圖，證明,G,和,不可能全是平面圖.,證,只需證明,G,和 中至少有一個(gè)是非平面圖.采用反證法.否則 與,G,都是平面圖，下面來(lái)推出矛盾.,G,與 的邊數(shù),m,m,應(yīng)滿足,(,K,n,的邊數(shù)),由鴿巢原理知,m,或,m,，不妨設(shè),m,，,又由定理17.12 知,m,3,n,6,由與得,n,2,13,n,+24,0,由解得 2,n,10,與,n,11,矛盾.,其實(shí)，當(dāng),n,=9,10時(shí)，命題結(jié)論已真.,練習(xí),2,3.證明下圖為非平面圖,練習(xí),3,證明,證 用庫(kù)拉圖斯基定理證明,方法一.下圖為原圖的子,圖，它是,K,3,3,，由庫(kù)拉圖斯,基定理得證命題.,方法二.下圖為原圖的子圖（刪除邊(,a,f,)），收縮本圖中的(,a,e,)和(,f,g,)所得圖為,K,5,由庫(kù)拉圖斯基定理得證命題.,圖20,圖19,練習(xí),4,4.設(shè),G,為,n,（,n,3,）階極大平面圖，證明,G,的對(duì)偶圖,G,*是2-邊連通的3-正則圖.,證 證明中用上,n,3,的極大平面圖的性質(zhì)，以及平面圖與對(duì)偶圖的關(guān)系，對(duì)偶圖的連通性等.,(1)證,G,*是2-邊連