平面圖及圖的著色

8.6

平面圖離散數(shù)學(xué)周金明zjmjz@163.com說(shuō)明平面圖的基本概念歐拉公式平面圖的判斷平面圖的對(duì)偶圖頂點(diǎn)著色及點(diǎn)色數(shù)地圖的著色與平面圖的點(diǎn)著色8.1平面圖的基本概念一、關(guān)于平面圖的一些基本概念1、平面圖的定義定義8.1

G可嵌入曲面S——如果圖G能以這樣的方式畫(huà)在曲面S上，即除頂點(diǎn)處外無(wú)邊相交。

G是可平面圖或平面圖——若G可嵌入平面。G的平面嵌入——畫(huà)出的無(wú)邊相交的平面圖。非平面圖——無(wú)平面嵌入的圖。（2）是（1）的平面嵌入，（4）是（3）的平面嵌入。2、幾點(diǎn)說(shuō)明及一些簡(jiǎn)單結(jié)論一般所談平面圖不一定是指平面嵌入，但討論某些性質(zhì)時(shí)，一定是指平面嵌入。K5和K3,3都不是平面圖。定理8.1設(shè)G

G，若G為平面圖，則G

也是平面圖。定理8.2設(shè)G

G，若G

為非平面圖，則G也是非平面圖。推論

Kn(n

5)和K3,n(n

3)都是非平面圖。定理8.3若G為平面圖，則在G中加平行邊或環(huán)所得圖還是平面圖。

即平行邊和環(huán)不影響圖的平面性。二、平面圖的面與次數(shù)（針對(duì)平面圖的平面嵌入）1、定義定義8.2

設(shè)G是平面圖，G的面——由G的邊將G所在的平面劃分成的每一個(gè)區(qū)域。無(wú)限面（外部面）——面積無(wú)限的面，記作R0。有限面（內(nèi)部面）——面積有限的面，記作R1,R2,…,Rk。面Ri的邊界——包圍面Ri的所有邊組成的回路組。面Ri的次數(shù)——Ri邊界的長(zhǎng)度，記作deg(Ri)。2、幾點(diǎn)說(shuō)明若平面圖G有k個(gè)面，可籠統(tǒng)地用R1,R2,…,Rk表示，不需要指出外部面?；芈方M是指：邊界可能是初級(jí)回路（圈），可能是簡(jiǎn)單回路，也可能是復(fù)雜回路。特別地，還可能是非連通的回路之并。平面圖有4個(gè)面，deg(R1)=1,deg(R2)=3,deg(R3)=2,deg(R0)=8。R1R2R3R0定理8.4

平面圖G中所有面的次數(shù)之和等于邊數(shù)m的兩倍，即本定理中所說(shuō)平面圖是指平面嵌入。

e∈E(G)，當(dāng)e為面Ri和Rj(i≠j)的公共邊界上的邊時(shí)，在計(jì)算Ri和Rj的次數(shù)時(shí)，e各提供1。

當(dāng)e只在某一個(gè)面的邊界上出現(xiàn)時(shí)，則在計(jì)算該面的次數(shù)時(shí)，e提供2。于是每條邊在計(jì)算總次數(shù)時(shí)，都提供2，因而deg(Ri)=2m。證明三、極大平面圖1、定義定義8.3

若在簡(jiǎn)單平面圖G中的任意兩個(gè)不相鄰的頂點(diǎn)之間加一條新邊所得圖為非平面圖，則稱G為極大平面圖。注意：若簡(jiǎn)單平面圖G中已無(wú)不相鄰頂點(diǎn)，G顯然是極大平面圖，如K1（平凡圖）,K2,K3,K4都是極大平面圖。2、極大平面圖的主要性質(zhì)定理8.5

極大平面圖是連通的。定理8.6

n(n

3)階極大平面圖中不可能有割點(diǎn)和橋。定理8.7

設(shè)G為n(n

3))階簡(jiǎn)單連通的平面圖，G為極大平面圖當(dāng)且僅當(dāng)G的每個(gè)面的次數(shù)均為3。本節(jié)只證明必要性，即設(shè)G為n(n

3))階簡(jiǎn)單連通的平面圖，G為極大平面圖，則G的每個(gè)面的次數(shù)均為3。由于n

3,又G必為簡(jiǎn)單平面圖，可知，G每個(gè)面的次數(shù)均

3。因?yàn)镚為平面圖，又為極大平面圖。可證G不可能存在次數(shù)>3的面。證明思路假設(shè)存在面Ri的次數(shù)deg(Ri)=s≥4，如圖所示。在G中，若v1與v3不相鄰，在Ri內(nèi)加邊(v1,v3)不破壞平面性，這與G是極大平面圖矛盾，因而v1與v3必相鄰，由于Ri的存在，邊(v1,v3)必在Ri外。類似地，v2與v4也必相鄰，且邊(v2,v4)也必在Ri外部，于是必產(chǎn)生(v1,v3)與(v2,v4)相交于Ri的外部，這又矛盾于G是平面圖，所以必有s＝3，即G中不存在次數(shù)大于或等于4的面，所以G的每個(gè)面為3條邊所圍，也就是各面次數(shù)均為3。sS-1只有右邊的圖為極大平面圖。因?yàn)橹挥性搱D每個(gè)面的次數(shù)都為3。四、極小非平面圖定義8.4

若在非平面圖G中任意刪除一條邊，所得圖G

為平面圖，則稱G為極小非平面圖。由定義不難看出：K5,K3,3都是極小非平面圖。極小非平面圖必為簡(jiǎn)單圖。例如：以下各圖均為極小非平面圖。小節(jié)結(jié)束8.2歐拉公式

一、歐拉公式相關(guān)定理1、

歐拉公式定理8.8對(duì)于任意的連通的平面圖G，有

n-m+r=2

其中，n、m、r分別為G的頂點(diǎn)數(shù)、邊數(shù)和面數(shù)。證明對(duì)邊數(shù)m作歸納法。(1)m＝0時(shí)，由于G為連通圖，所以G只能是由一個(gè)孤立頂點(diǎn)組成的平凡圖，即n=1，m=0，r=1，結(jié)論顯然成立。(2)m＝1時(shí)，由于G為連通圖，所以n=2，m=1，r=1，結(jié)論顯然成立。(3)設(shè)m＝k(k≥1)時(shí)成立，當(dāng)m＝k+1時(shí)，對(duì)G進(jìn)行如下討論。若G是樹(shù)，則G是非平凡的，因而G中至少有兩片樹(shù)葉。設(shè)v為樹(shù)葉，令G'=G-v，則G'仍然是連通圖，且G'的邊數(shù)m'=m-1=k，n'=n-1，r'=r。由假設(shè)可知n'-m'+r'=2，式中n'，m'，r'分別為G'的頂點(diǎn)數(shù)，邊數(shù)和面數(shù)。于是n-m+r=(n'+1)-(m'+1)+r'=n'-m'+r'=2若G不是樹(shù)，則G中含圈。設(shè)邊e在G中某個(gè)圈上，令G'=G-e，則G'仍連通且m'=m-1=k，n'=n，r'=r-1。由假設(shè)有n'-m'+r'=2。于是n-m+r=n'-(m'+1)-(r'+1)=n'-m'+r'=2定理8.9對(duì)于具有k(k≥2)個(gè)連通分支的平面圖G，有

n-m+r=k+1

其中n，m，r分別為G的頂點(diǎn)數(shù)，邊數(shù)和面數(shù)。證明設(shè)G的連通分支分別為G1、G2、…、Gk，并設(shè)Gi的頂點(diǎn)數(shù)、邊數(shù)、面數(shù)分別為ni、mi、ri、i=1，2，…，k。

由歐拉公式可知:ni-mi+ri

=2，i=1，2，…，k (8.1)易知，由于每個(gè)Gi

有一個(gè)外部面，而G只有一個(gè)外部面，所以G的面數(shù)于是，對(duì)(8.1)的兩邊同時(shí)求和得

經(jīng)整理得n-m+r=k+1。2、與歐拉公式有關(guān)的定理定理8.10

設(shè)G為連通的平面圖，且每個(gè)面的次數(shù)至少為l(l3)，則G的邊數(shù)與頂點(diǎn)數(shù)有如下關(guān)系：由定理8.4（面的次數(shù)之和等于邊數(shù)的2倍）及歐拉公式得證明解得推論

K5,K3,3不是平面圖。證明若K5是平面圖，由于K5中無(wú)環(huán)和平行邊，所以每個(gè)面的次數(shù)均大于或等于l≥3，由定理17.10可知邊數(shù)10應(yīng)滿足10≤(3/(3-2))(5-2)=9這是個(gè)矛盾，所以K5不是平面圖。若K3,3是平面圖，由于K3,3中最短圈的長(zhǎng)度為l≥4，于是邊數(shù)9應(yīng)滿足9≤(4/(4-2))(6-2)=8這又是矛盾的，所以K3,3也不是平面圖。定理8.11

設(shè)G是有k(k≥2)個(gè)連通分支的平面圖，各面的次數(shù)至少為l(l≥3)，則邊數(shù)m與頂點(diǎn)數(shù)n應(yīng)有如下關(guān)系：

定理8.12

設(shè)G為n(n

3)階m條邊的簡(jiǎn)單平面圖，則m

3n

6。設(shè)G有k(k

1)個(gè)連通分支，若G為樹(shù)或森林，當(dāng)n

3時(shí)，m=n-k

3n

6為真。若G不是樹(shù)也不是森林，則G中必含圈，又因?yàn)镚是簡(jiǎn)單圖，所以，每個(gè)面至少由l（l

3）條邊圍成，又在l=3達(dá)到最大值，由定理8.11可知證明定理8.13

設(shè)G為n(n

3)階m條邊的極大平面圖，則m=3n

6。證明由于極大平面圖是連通圖，由歐拉公式得:

r=2+m-n

(8.4)

又因?yàn)镚是極大平面圖，由定理17.7的必要性可知，G的每個(gè)面的次數(shù)均為3，所以：將(8.4)代入(8.5)，整理后得m=3n-6。二、一個(gè)意義重大的定理定理8.14

設(shè)G為簡(jiǎn)單平面圖，則G的最小度

(G)

5。若階數(shù)n

6，結(jié)論顯然成立。若階數(shù)n

7時(shí)，用反證法。假設(shè)

(G)

6，由握手定理可知：證明因而m

3n，這與定理8.12矛盾。所以，假設(shè)不成立，即G的最小度

(G)

5。本定理在圖著色理論中占重要地位。說(shuō)明定理8.7

設(shè)G為n(n

3))階簡(jiǎn)單連通的平面圖，G為極大平面圖當(dāng)且僅當(dāng)G的每個(gè)面的次數(shù)均為3。（僅證充分性）由定理17.4可知，證明又因?yàn)镚是連通的，由歐拉公式可知將(8.7)代入(8.6)，經(jīng)過(guò)整理得m=3n-6。 (8.8)若G不是極大平面圖，則G中一定存在不相鄰得頂點(diǎn)u,v，使得G

=G

(u,v)還是簡(jiǎn)單平面圖，而G

的邊數(shù)m=m+1，n=n。由(8.8)可知，m>3n-6

，這與定理8.2矛盾。所以，G為極大平面圖。小節(jié)結(jié)束1、插入2度頂點(diǎn)和消去2度頂點(diǎn)定義8.5設(shè)e=(u,v)為圖G的一條邊，在G中刪除e，增加新的頂點(diǎn)w，使u、v均與w相鄰，稱為在G中插入2度頂點(diǎn)w。設(shè)w為G中一個(gè)2度頂點(diǎn)，w與u、v相鄰，刪除w，增加新邊(u,v)，稱為在G中消去2度頂點(diǎn)w。8.3平面圖的判斷2、圖之間的同胚定義8.6

若兩個(gè)圖G1與G2同構(gòu)，或通過(guò)反復(fù)插入或消去2度頂點(diǎn)后是同構(gòu)的，則稱G1與G2是同胚的。上面兩個(gè)圖分別與K3,3,K5同胚。二、兩個(gè)判斷定理定理8.15(庫(kù)拉圖斯基定理1)圖G是平面圖當(dāng)且僅當(dāng)G中既不含與K5同胚子圖，也不含與K3,3同胚子圖。8.4平面圖的對(duì)偶圖一、對(duì)偶圖的定義定義8.7

設(shè)G是平面圖，構(gòu)造G的對(duì)偶圖G*如下：在G的面Ri中放置G*的頂點(diǎn)vi*。設(shè)e為G的任意一條邊，

若e在G的面Ri與Rj的公共邊界上，做G*的邊e*與e相交，且e*關(guān)聯(lián)G*的位于Ri與Rj中的頂點(diǎn)vi*與vj*，即e*=(vi*,vj*)，e*不與其它任何邊相交。

若e為G中的橋且在面Ri的邊界上，則e*是以Ri中G*的頂點(diǎn)vi*為端點(diǎn)的環(huán)，即e*=(vi*,vi*)。實(shí)線邊圖為平面圖，虛線邊圖為其對(duì)偶圖。從定義不難看出G的對(duì)偶圖G*有以下性質(zhì)：G*是平面圖。G*是連通圖。若邊e為G中的環(huán)，則G*與e對(duì)應(yīng)的邊e*為橋，若e為橋，則G*中與e對(duì)應(yīng)的邊e*為環(huán)。在多數(shù)情況下，G*為多重圖（含平行邊的圖）。同構(gòu)的平面圖的對(duì)偶圖不一定是同構(gòu)的。二、平面圖與對(duì)偶圖的階數(shù)、邊數(shù)與面數(shù)之間的關(guān)系。定理8.16

設(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(1)、(2)由G*的構(gòu)造可知是顯然的。(3)由于G與G*都連通，因而滿足歐拉公式:

n-m+r=2

n*-m*+r*=2 由(1)、(2))可知，r*=2+m*-n*=2+m-r=n證明定理8.17

設(shè)G*是具有k（k

2）個(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

k+1三、自對(duì)偶圖定義8.8

設(shè)G*是平面圖G的對(duì)偶圖，若G*

G，則稱G為自對(duì)偶圖。在n

1(n

4)邊形Cn

1內(nèi)放置1個(gè)頂點(diǎn)，使這個(gè)頂點(diǎn)與Cn

1上的所有的頂點(diǎn)均相鄰，所得n階簡(jiǎn)單圖稱為n階輪圖。記為Wn。n為奇數(shù)的輪圖稱為奇階輪圖。n為偶數(shù)的輪圖稱為偶階輪圖。輪圖都是自對(duì)偶圖。小節(jié)結(jié)束8.5圖中頂點(diǎn)的著色規(guī)定：點(diǎn)著色都是對(duì)無(wú)環(huán)無(wú)向圖進(jìn)行的。一、關(guān)于頂點(diǎn)著色的基本概念定義8.9

（1）圖G的一種著色——對(duì)無(wú)環(huán)圖G的每個(gè)頂點(diǎn)涂上一種顏

色，使相鄰頂點(diǎn)涂不同的顏色。（2）對(duì)G進(jìn)行k著色（G是k-可著色的）——能用k種顏色給G

的頂點(diǎn)著色。（3）G的色數(shù)

(G)=k——G是k-可著色的，但不是(k

1)-可著

色的。二、關(guān)于頂點(diǎn)著色的幾個(gè)簡(jiǎn)單結(jié)果定理8.18

(G)=1當(dāng)且僅當(dāng)G為零圖。定理8.19

(Kn)=n。

定理8.20

奇階輪圖的色數(shù)均為3，偶階輪圖的色數(shù)為4。定理8.21

設(shè)G中至少含有一條邊，則

(G)=2當(dāng)且僅當(dāng)G為二部圖。三、色數(shù)的上界定理8.22

對(duì)于任意無(wú)向圖G，均有

(G)

(G)+1。n=1時(shí)，結(jié)論成立。設(shè)n=k(k≥1)時(shí)結(jié)論成立，則當(dāng)n=k+1時(shí)，設(shè)v為G中任一個(gè)頂點(diǎn)，令G'=G-v，則G'的階數(shù)為k，由假設(shè)可知

(G')

(G')+1≤Δ(G)+1。

當(dāng)將G'還原成G時(shí)，由于v至多與G'中Δ(G)個(gè)頂點(diǎn)相鄰，而在G'的點(diǎn)著色中，Δ(G)個(gè)頂點(diǎn)至多用了Δ(G)種顏色，于是在Δ(G)+1種顏色中至少存在一種顏色給v涂色，使v與相鄰頂點(diǎn)涂不同顏色。證明提示：對(duì)G的階數(shù)n作歸納法。例

求下面各圖的色數(shù)。定理8.23(布魯克斯定理)若連通無(wú)向圖G不是Kn(n

3)，也不是奇數(shù)階的圈，則