平面圖和圖的著色

平面圖和圖的著色1第1頁，課件共55頁，創(chuàng)作于2023年2月

9.1平面圖及歐拉公式

uv

uv

定義9.1.1

圖G稱為被嵌入平面S內(nèi)，如果G的圖解已畫在平面S上，而且任何兩條邊均不相交(除頂點(diǎn)外)。已嵌入平面的圖稱為平面圖。如果一個圖可以嵌入平面，則稱此圖是可平面的。

2第2頁，課件共55頁，創(chuàng)作于2023年2月幾點(diǎn)說明及一些簡單結(jié)論一般所談平面圖不一定是指平面嵌入。但討論某些性質(zhì)時，是指平面嵌入.結(jié)論：

(1)K5,K3,3都不是平面圖(待證).(2)設(shè)G

G，若G為平面圖，則G

也是平面圖.由此可知，Kn(n≤4)，K2,n(n

1)都是平面圖.(3)設(shè)G

G，若G

為非平面圖，則G也是非平面圖.由此可知，Kn(n

5)，Km,n(m,n

3)都是非平面圖.(4)平行邊與環(huán)不影響平面性.

3第3頁，課件共55頁，創(chuàng)作于2023年2月

uvf1f2f3f4

定義9.1.2

平面圖把平面分成了若干個區(qū)域，這些區(qū)域都是單連通的，稱之為G的面，其中無界的那個連通區(qū)域稱為G的外部面，其余的單連通區(qū)域稱為G的內(nèi)部面。平面圖的內(nèi)部面與外部面4第4頁，課件共55頁，創(chuàng)作于2023年2月平面圖的每個內(nèi)部面都是G的某個圈圍成的單連通區(qū)域。沒有圈的圖沒有內(nèi)部面，只有一個外部面。

uvf1f2f3f4

圖15第5頁，課件共55頁，創(chuàng)作于2023年2月(2)面Ri的邊界——包圍Ri的閉通道組(3)面Ri的次數(shù)——Ri邊界的長度幾點(diǎn)補(bǔ)充(1)若平面圖G有k個面，可用R1,R2,…,Rk表示.(4)閉通道組是指：邊界可能是圈，也可能是閉通道.特別地，還可能是非連通的閉通道之并.定理平面圖各面次數(shù)之和等于邊數(shù)的兩倍.6第6頁，課件共55頁，創(chuàng)作于2023年2月如果用V表示多面體的頂點(diǎn)，用E表示棱，用F表示面數(shù)，則V-E+F=2。

定理9.1.1(歐拉公式)

如果一個平面連通圖有p個頂點(diǎn)、q條邊、f個面，則p-q+f=2。證對面數(shù)用歸納法當(dāng)f=1時，G沒有內(nèi)部面，所以G中無圈，G是樹。p-q+f=1+1=2假如對一切不超過f-1個面的平面連通圖歐拉公式成立，現(xiàn)證f個面時的情況。7第7頁，課件共55頁，創(chuàng)作于2023年2月f≥2，G至少有一個內(nèi)部面，從而G中有一個圈。這個內(nèi)部面是由這個圈圍成的，從這個圈上去掉一條邊x，則打通了兩個面。

G-x有p個頂點(diǎn)，q-1條邊，f-1個面。由歸納假設(shè)p-(q-1)+(f-1)=2p-q+f=2因此面數(shù)是f時也成立。

uvf1f2f3f4

uvf1f2f3f48第8頁，課件共55頁，創(chuàng)作于2023年2月定理9.1.2

（歐拉公式的推廣）設(shè)G是具有k(k

2)個連通分支的平面圖，則n

m+r=k+1.9第9頁，課件共55頁，創(chuàng)作于2023年2月

推論9.1.1

若平面連通圖G有p個頂點(diǎn)q條邊且每個面都是由長為n的圈圍成的，則q=n(p-2)/(n-2)。

證

因?yàn)镚的每個面都是長為n的圈圍成的，所以G的每條邊都在G的兩個面上。q=f

n/2f=2q/np-q+2q/n=2q=n(p-2)/(n-2)10第10頁，課件共55頁，創(chuàng)作于2023年2月最大(極大)可平面圖

一個圖稱為最大可平面圖，如果這個可平面圖再加入一條邊，新圖必然是不可平面的。

圖1再加一條邊就是k5，可證k5是不可平面圖。圖1是最大可平面圖。11第11頁，課件共55頁，創(chuàng)作于2023年2月

最大(極大)平面圖的性質(zhì)

uv最大(極大)平面圖的主要性質(zhì)：定理最大(極大)平面圖是連通的.定理

n(n

3)階最大(極大)平面圖中不可能有割點(diǎn)和橋.

12第12頁，課件共55頁，創(chuàng)作于2023年2月

推論9.1.2

設(shè)G是一個有p個頂點(diǎn)q條邊的最大可平面圖，則G的每個面都是三角形，q=3p-6，p≥3。證若G的一個面不是三角形,

...

v1v2v3v4

1、假如有兩點(diǎn)不相鄰，則在此面中把不相鄰的兩頂點(diǎn)連接起來，不影響平面性。矛盾，因此不可能有兩點(diǎn)不相鄰。13第13頁，課件共55頁，創(chuàng)作于2023年2月2、假如圈上每兩點(diǎn)都相鄰;

...

v1v2v3v4若v1,v2和v2,v4在G中都鄰接,我們可以看到這兩個邊不可能不相交;綜合以上情況，最大平面圖的每個面都是三角形。14第14頁，課件共55頁，創(chuàng)作于2023年2月

推論9.1.3

設(shè)G是一個(p,q)可平面連通圖，而且G的每個面都是一個長為4的圈圍成的，則q=2p-4。

推論9.1.4若G是任一有p個頂點(diǎn)q條邊的可平面圖p≥3，則q≤3p-6。若G是2-連通的且沒有三角形，則q≤2p-4。1、因?yàn)楫?dāng)平面圖中每個面都是三角形時其邊數(shù)最多，由推論9.1.2，則q≤3p-6。

2、若G是2-連通的且沒有三角形,則G中任意兩個頂點(diǎn)都在同一個圈上。已知沒有三角形，所以圈的長都是4時邊數(shù)最多。所以q≤2p-4。15第15頁，課件共55頁，創(chuàng)作于2023年2月推論9.1.5K5與K3,3都不是可平面圖

證

如果K5是平面圖，則5-10+f=2，即f=7。每個面至少三條邊，7個面至少需要21條邊。考慮到每條邊在兩個面上，2q≥3f，即20≥21。矛盾。

其實(shí)直接利用推論9.1.4，任意(p,q)平面圖都滿足q≤3p-6，這里p≥3。q=10≤3p-6=9，這是不成立的。所以K5不是可平面圖。16第16頁，課件共55頁，創(chuàng)作于2023年2月如果K3,3是平面圖，則p-q+f=2，即6-9+f=2，亦即f=5。在偶圖K3,3中每個圈的長至少為4，所以2q≥4f=20，q≥10，但q=9，矛盾。

所以K3,3不是平面圖。17第17頁，課件共55頁，創(chuàng)作于2023年2月

推論9.1.6每個平面圖G中頂點(diǎn)度的最小值不超過5，即(G)≤5。如果G的每個頂點(diǎn)的度大于5，也就是≥6，由歐拉定理，2q≥6p，即q≥3p。仍然用推論9.1.4，q≤3p-6。那么所有頂點(diǎn)的度數(shù)和大于或等于6p。不滿足推論9.1.4，q≤3p-6。因此，每個平面圖G中頂點(diǎn)度的最小值不超過5，即(G)≤5。18第18頁，課件共55頁，創(chuàng)作于2023年2月例9.1.1頂點(diǎn)數(shù)p≥4的最大平面圖，(G)≥3。證

設(shè)G是最大平面圖，其最小度頂點(diǎn)為v。設(shè)G-v也是一個平面圖，v在G-v的一個面內(nèi)。在這個面內(nèi)，邊界上至少有三個頂點(diǎn)。由極大性，v必然與這些頂點(diǎn)都相連。因此，

(G)≥3。

v19第19頁，課件共55頁，創(chuàng)作于2023年2月

定理9.2.1

設(shè)G=(V,E)是一個(p,q)平面哈密頓圖,C是G的哈密頓圈，令fi為C的內(nèi)部由i條邊圍成的面的個數(shù)，gi為C的外部i條邊圍成的面的個數(shù)，則9.2非哈密頓平面圖(1)1f3+2f4+3f5+...+(p-2)fp=(2)1g3+2g4+3g5+...+(p-2)gp=(3)1(f3-g3)+2(f4-g4)+3(f5-g5)+...=

v1v2v3v4v5v6v7v8有哈密頓圈v1v2v3v4v8v7v6v5v1圈內(nèi)有3條邊圍成的面2個圈內(nèi)有4條邊圍成的面2個圈外有8條邊圍成的面1個20第20頁，課件共55頁，創(chuàng)作于2023年2月

證

因?yàn)镃是G的哈密頓圈，所以G的所有頂點(diǎn)都在圈C上。因此C的內(nèi)部與外部不再含有G的頂點(diǎn)。

C的內(nèi)部的每個面都是由C上的某邊及C上兩頂點(diǎn)間的“連線”圍成的區(qū)域。

v1v2v3v4v5v6v7v8設(shè)q

是C的內(nèi)部(不含C)邊的條數(shù)，這些邊之集記為E

。先把C內(nèi)部的邊都去掉，這時C里只有一個面。把E

的一條邊加入C中。就把C分成兩個面。再加入E的另一條邊就把這兩個面之一分為兩個面，如此進(jìn)行，直到把E的邊都加入為止。這樣，C的內(nèi)部就有q+1個面。21第21頁，課件共55頁，創(chuàng)作于2023年2月f1+f2+f3+...=其次，由j條邊圍成面共fj個，這些面上的邊的總數(shù)為jfj，所以，C內(nèi)部的q+1個面上的邊數(shù)共有。其中C上的每條邊在每個內(nèi)部面上至多出現(xiàn)一次且不是兩個內(nèi)部面的公共邊，所以在上述計(jì)數(shù)中C上每條邊各計(jì)數(shù)一次。但E

中的每條邊是兩個面之公共邊，所以每條邊計(jì)數(shù)兩次，因此。

v1v2v3v4v5v6v7v822第22頁，課件共55頁，創(chuàng)作于2023年2月從(2)式兩邊分別減去(1)式兩邊的兩倍便得到f1+f2+f3+...=(1)(2)用同樣的方法可得:(3)(4)(3)式兩邊分別減去(4)式的兩邊得23第23頁，課件共55頁，創(chuàng)作于2023年2月

例9.2.2

下圖是一個哈密頓圖，證明：任一哈密頓圈上如果包含邊x，那么這個哈密頓圈上就一定不包含邊y。

xy證右圖G是哈密頓平面圖，它的面或由4條邊圍成，或由5條邊圍成，由定理9.2.1有:2(f4-g4)+3(f5-g5)=0所以f4-g4能被3整除，即五個由4條邊圍成的面中有四個面在G的哈密頓圈C外，一個在C內(nèi)；或相反即一個在C外，四個在C的內(nèi)部。123456724第24頁，課件共55頁，創(chuàng)作于2023年2月同樣，以y為公共邊的兩側(cè)的四條邊圍成的兩個面中，必一個在C的內(nèi)部，另一個在C的外部。這就得到矛盾，故C不能同時含邊x與y。

xy因此，C的內(nèi)部與C的外部均至少有兩個四條邊圍成的面。假如C既含邊x又含邊y，則以x為公共邊的兩側(cè)的四條邊圍成的兩面中必有一個在C的內(nèi)部，另一個在C的外部。25第25頁，課件共55頁，創(chuàng)作于2023年2月K5和K3,3不是平面圖。9.3庫拉托斯基定理、對偶圖平面圖的每個子圖都是平面圖，因此，平面圖中不含子圖K5和K3,3。

定義9.3.1

設(shè)x=uv是圖G=(V,E)的一條邊，w不是G的頂點(diǎn)，則當(dāng)用邊uw和wv代替邊x時，就稱x被細(xì)分。如果G的某些邊被細(xì)分，產(chǎn)生的圖稱為G的細(xì)分圖。

uv圖Gx

uvwG的細(xì)分圖26第26頁，課件共55頁，創(chuàng)作于2023年2月

定義9.3.2

兩個圖稱為同胚的，如果它們都可以從同一個圖通過一系列的邊細(xì)分得到。下面幾個圖是同胚的。

uv圖Gx

uvwG的細(xì)分圖

圖與圖之間同胚27第27頁，課件共55頁，創(chuàng)作于2023年2月定義9.3.1

所定義的的細(xì)分也稱為插入2度頂點(diǎn)。與之相對應(yīng)的還有一種方法：消去2度頂點(diǎn)。補(bǔ)充(1)消去2度頂點(diǎn)v，見下圖中，由(1)到(2)；(2)插入2度頂點(diǎn)v，見下圖中，從(2)到(1).定義若G1

G2，或經(jīng)過反復(fù)插入或消去2度頂點(diǎn)后所得G

1

G

2，則稱G1與G2同胚.28第28頁，課件共55頁，創(chuàng)作于2023年2月

定理9.3.1（庫拉托斯基,1930）一個圖是可平面的充分必要條件是它沒有同胚于K5和K3,3的子圖。

例9.3.1

證明左下圖不是可平面圖。因?yàn)樗信cK5同胚的子圖。

uv庫拉托斯基定理29第29頁，課件共55頁，創(chuàng)作于2023年2月例9.3.2

證明所示圖(1)與(2)均為非平面圖.

(1)(2)右圖(1),(2)分別為原圖(1),(2)的子圖與K3,3,K5同胚.

子圖(1)子圖(2)

30第30頁，課件共55頁，創(chuàng)作于2023年2月

定義9.3.3

一個圖G的一個初等收縮由合并兩個鄰接的頂點(diǎn)u和v得到，即從G中去掉u和v，然后再加上一個新頂點(diǎn)w，使得w相鄰所有與u或v相鄰的頂點(diǎn)。

uv

w一個圖G可收縮到圖H，如果H可以從G經(jīng)一系列的初等收縮得到。圖G的初等收縮31第31頁，課件共55頁，創(chuàng)作于2023年2月

定理9.3.2

一個圖是可平面的當(dāng)且僅當(dāng)它沒有一個可以收縮到K5或K3,3的子圖。

例9.3.1

證明左下圖不是可平面圖。因?yàn)樗梢允湛s到K5。32第32頁，課件共55頁，創(chuàng)作于2023年2月

定義9.3.4

設(shè)G=(V,E)是一個平面圖，由G按如下方法構(gòu)造一個圖G*，G*稱為G的對偶圖。

3、如果某條邊x僅在一個面中出現(xiàn)而不是兩個面的公共邊(是不是橋？)，則在G*中這個面對應(yīng)的頂點(diǎn)有一個環(huán)。

1、對G的每個面f對應(yīng)地有G*的一個頂點(diǎn)f*；

2、對G的每條邊e對應(yīng)地有G*的一條邊e*：G*的兩個頂點(diǎn)f*與g*由邊e*聯(lián)結(jié)，當(dāng)且僅當(dāng)G中與頂點(diǎn)f*與g*對應(yīng)的面f與g有公共邊e。平面圖的對偶圖33第33頁，課件共55頁，創(chuàng)作于2023年2月下面兩圖中，實(shí)線邊圖為平面圖，虛線邊圖為其對偶圖.

實(shí)例34第34頁，課件共55頁，創(chuàng)作于2023年2月對偶圖的性質(zhì)G的對偶圖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)的.35第35頁，課件共55頁，創(chuàng)作于2023年2月(6)設(shè)G*是連通平面圖G的對偶圖，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中，則

degG*(v*i)=面Ri的次數(shù).對偶圖的性質(zhì)只證明(3)r*=n。由圖G與G*都是連通平面圖，所以n*-m*+r*=2得r*=m*-n*+2=m-r+2n-m+r=2可得n=m-r+2因此r*=n。36第36頁，課件共55頁，創(chuàng)作于2023年2月9.4圖的頂點(diǎn)著色

定義9.4.1

圖的一種(頂點(diǎn))著色是指對圖的每個頂點(diǎn)指定一種顏色，使得沒有兩個相鄰的頂點(diǎn)有同一顏色。若圖G=(V,E)的頂點(diǎn)已著色，則著同一顏色的那些頂點(diǎn)之集稱為G的一個色組。同一色組內(nèi)的各頂點(diǎn)不相鄰，這樣的頂點(diǎn)集合稱為G的一個頂點(diǎn)獨(dú)立集。如果G有一個n著色，則G的頂點(diǎn)集V被這種n著色劃分為n個色組。圖G的一個n著色是用n種顏色對G的頂點(diǎn)著色。

12123212137第37頁，課件共55頁，創(chuàng)作于2023年2月

定義9.4.2

圖G的色數(shù)是使G為n著色的數(shù)的最小值，圖G的色數(shù)記為

(G)。若

(G)n，則稱G是n可著色的。若

(G)=n，則稱G是n色的。

(Kp)=p

(Kpc)=1

(Km,n)=2,

圖G的色數(shù)的概念38第38頁，課件共55頁，創(chuàng)作于2023年2月

定理9.4.1

一個圖是可雙色的當(dāng)且僅當(dāng)它沒有奇數(shù)長的圈。一個圖是可雙色的當(dāng)且僅當(dāng)是偶圖。偶圖的充分必要條件是它的圈的長度都是偶數(shù)。若G是偶數(shù)個頂點(diǎn)的圈C2n，則

(C2n)=2。若G是奇數(shù)個頂點(diǎn)的圈C2n+1，則

(C2n+1)=3。

121232121

1212212139第39頁，課件共55頁，創(chuàng)作于2023年2月

定理9.4.2

設(shè)

=(G)為圖G的頂點(diǎn)度的最大值，則G是(+1)—可著色的。證

對頂點(diǎn)數(shù)p用歸納法。當(dāng)p=1時，結(jié)論成立。假設(shè)對頂點(diǎn)數(shù)為p-1的圖定理成立，今設(shè)G是一個有p個頂點(diǎn)的圖。從G中去掉一個頂點(diǎn)v，則G-v有p-1個頂點(diǎn)，

(G-v)≤(G)由歸納假設(shè)G-v是(+1)—可著色的。但在G中與v相鄰的頂點(diǎn)最多有個，與v相鄰的頂點(diǎn)最多用去種顏色，剩下一種給頂點(diǎn)v著色即可。40第40頁，課件共55頁，創(chuàng)作于2023年2月

定理9.4.3

如果G是一個連通圖且不是完全圖也不是奇數(shù)長的圈，則G是

(G)—可著色的。41第41頁，課件共55頁，創(chuàng)作于2023年2月定理9.4.4

每個平面圖都是6可著色的。如果頂點(diǎn)數(shù)小于7，顯然是6—可著色的。證

對平面圖的頂點(diǎn)數(shù)p用歸納法。設(shè)G是一個有p個頂點(diǎn)的平面圖，由推論9.1.6知G有頂點(diǎn)v，degv≤5，G-v是一個p-1個頂點(diǎn)的平面圖。假設(shè)對p-1個頂點(diǎn)的平面圖是6—可著色的，只需證對有p個頂點(diǎn)的平面圖也是6—可著色的即可。由歸納假設(shè)，G-v是6—可著色的,與v相鄰的頂點(diǎn)至多5個，所以與v相鄰的頂點(diǎn)著色時至多用了5種色。用另一種未用的顏色對v著色即得G的一個6—著色。因此,G是6可著色的。42第42頁，課件共55頁，創(chuàng)作于2023年2月定理9.4.5

每個可平面圖是5—可著色的證對可平面圖的頂點(diǎn)數(shù)進(jìn)行歸納證明。當(dāng)p≤5時。定理顯然成立。假設(shè)所有p個頂點(diǎn)的可平面圖都是5—可著色的，需證所有p+1個頂點(diǎn)的可平面圖也是5—可著色的。設(shè)G是一個有p+1個頂點(diǎn)可平面圖，由推論9.1.6知G中有一個頂點(diǎn)v使degv≤5。于是，G-v是一個有p個頂點(diǎn)的可平面圖，由歸納假設(shè)，G-v是5可著色的。

1、如果degv≤4,則必有一種顏色，在G-v的一種5-著色時，對與v相鄰的頂點(diǎn)著色中未用此色，于是，用此色對頂點(diǎn)v著色便得到G的5-著色。43第43頁，課件共55頁，創(chuàng)作于2023年2月

2、degv=5且對G-v的5-著色中，與v相鄰的5個頂點(diǎn)v1,v2,v3,v4,v5分別著5種顏色c1,c2,c3,c4,c5。

v1vv2v3v4v5令G13為G-v的一個子圖，其頂點(diǎn)為著c1色或c3色的頂點(diǎn)之集V13,G13就是V13導(dǎo)出的子圖。(1)若v1和v3在G13的不同支中，則在含v1的支中交換兩種色，即原著c1色頂點(diǎn)改著c3色，原著c3色的頂點(diǎn)改著c1色。

c3c1c3c1

c3c1c3c1

c1c3c1c3

c3然后用c1給頂點(diǎn)v著色，于是得到G的一種5—著色。44第44頁，課件共55頁，創(chuàng)作于2023年2月

(2)若v1和v3在G13的同一個支中，則在G13中有一條從v1到v3的路，于是，在G中v1vv3與這條路合起來形成一個圈。

v1vv2v3v4v5

3131這個圈或把v2圈在圈內(nèi)或把v4和v5圈在內(nèi)。若令G24表示G-v的由著c2或c4色的頂點(diǎn)導(dǎo)出的子圖，則v2與v4屬于G24的不同支里。

4

2

4

2

4

2交換G24的含v2支中著c2色頂點(diǎn)與著c4色頂點(diǎn)的顏色，然后，用c2色為v著色得到G的一個5著色。任何情況下，不存在聯(lián)結(jié)v2和v4的路且路上各頂點(diǎn)或著c2或著c4色。45第45頁，課件共55頁，創(chuàng)作于2023年2月4色猜想每個可平面圖是4—可著色的。定理9.4.6

每個可平面圖是4—可著色的。

1852年，剛從倫敦大學(xué)畢業(yè)的哥斯尼從事地圖染色工作，他發(fā)現(xiàn)在一幅正規(guī)地圖中，最多只用四種顏色著色，就能把這些國家區(qū)別開來。如果國家用圖的頂點(diǎn)來表示，兩個頂點(diǎn)相鄰當(dāng)且僅當(dāng)兩個國家相鄰，就形成一個平面圖。46第46頁，課件共55頁，創(chuàng)作于2023年2月9.5圖的邊著色

定義9.5.1

圖G的一個k—邊著色是對G的每條邊指定k種色之一，使得任何兩條相鄰的邊被指定色是不同的。如果圖G是k—邊著色的，但不(k-1)—邊著色的，則稱G的邊色數(shù)為k，G的邊色數(shù)記為

(G)。

12314234如果=(G)是圖G的頂點(diǎn)的最大度數(shù)，則顯然有

(G)≥。右圖存在一個4—邊著色不存在3—邊著色

(G)=447第47頁，課件共55頁，創(chuàng)作于2023年2月對某些特殊類型的圖，我們能容易確定它的邊色數(shù)。例如：偶數(shù)長的圈C2n的邊色數(shù)是

(C2n)=2。

121232121

12122121對奇數(shù)長的圈C2n+1有

(C2n+1)=3。48第48頁，課件共55頁，創(chuàng)作于2023年2月

定理9.5.1

如果p是不為1的奇數(shù)，則

(Kp)=p。如果p是偶數(shù)，則

(Kp)=p-1。證

設(shè)p是奇數(shù)，把Kp的p個頂點(diǎn)安放在正p邊形的頂點(diǎn)上，對正p邊形的p個邊分別著p個不同色。而平行于p邊形的對角線的邊著與這條邊同一顏色，這就得到Kp的一個p—邊著色。

1、證明當(dāng)p是奇數(shù)時，Kp是p邊著色的。49第49頁，課件共55頁，創(chuàng)作于2023年2月Kp最多有(p-1)

(Kp)/2條邊;(p-1)/2條平行邊已關(guān)聯(lián)了(p-1)個頂點(diǎn)，所以在Kp的邊著色中至多有(p-1)/2條同