1、平面圖和圖的著色第1頁，共55頁，2022年，5月20日，7點26分，星期三1 9.1 平面圖及歐拉公式 uv uv 定義 圖G稱為被嵌入平面S內(nèi)，如果G的圖解已畫在平面S上，而且任何兩條邊均不相交(除頂點外)。已嵌入平面的圖稱為平面圖。如果一個圖可以嵌入平面，則稱此圖是可平面的。 第2頁，共55頁，2022年，5月20日，7點26分，星期三2幾點說明及一些簡單結(jié)論 一般所談平面圖不一定是指平面嵌入。但討論某些性質(zhì)時，是指平面嵌入. 結(jié)論： (1) K5, K3,3都不是平面圖(待證).(2) 設(shè)GG，若G為平面圖，則G也是平面圖.由此可知，Kn(n4)，K2,n(n1) 都是平面圖. (3)

2、 設(shè)GG，若G為非平面圖，則G也是非平面圖.由此可知，Kn(n5)，Km,n(m,n3) 都是非平面圖. (4) 平行邊與環(huán)不影響平面性. 第3頁，共55頁，2022年，5月20日，7點26分，星期三3 uvf1f2f3f4 定義 平面圖把平面分成了若干個區(qū)域，這些區(qū)域都是單連通的，稱之為G的面，其中無界的那個連通區(qū)域稱為G的外部面，其余的單連通區(qū)域稱為G的內(nèi)部面。平面圖的內(nèi)部面與外部面第4頁，共55頁，2022年，5月20日，7點26分，星期三4 平面圖的每個內(nèi)部面都是G的某個圈圍成的單連通區(qū)域。沒有圈的圖沒有內(nèi)部面，只有一個外部面。 uvf1f2f3f4 圖1第5頁，共55頁，2022年，

3、5月20日，7點26分，星期三5(2) 面 Ri 的邊界包圍Ri的閉通道組(3) 面 Ri 的次數(shù)Ri邊界的長度 幾點補充(1)若平面圖G有k個面，可用R1, R2, , Rk表示.(4) 閉通道組是指：邊界可能是 圈，也可能是閉通道. 特別地，還可能是非連通的閉通道之并. 定理 平面圖各面次數(shù)之和等于邊數(shù)的兩倍. 第6頁，共55頁，2022年，5月20日，7點26分，星期三6 如果用V表示多面體的頂點，用E表示棱，用F表示面數(shù)，則V-E+F=2。 定理9.1.1(歐拉公式) 如果一個平面連通圖有p個頂點、q條邊、f個面，則p-q+f=2。證 對面數(shù)用歸納法當(dāng)f=1時，G沒有內(nèi)部面，所以G中無

4、圈，G是樹。p-q+f=1+1=2 假如對一切不超過f-1個面的平面連通圖歐拉公式成立，現(xiàn)證f個面時的情況。第7頁，共55頁，2022年，5月20日，7點26分，星期三7f2，G至少有一個內(nèi)部面，從而G中有一個圈。這個內(nèi)部面是由這個圈圍成的，從這個圈上去掉一條邊x，則打通了兩個面。 G-x有p個頂點，q-1條邊，f-1個面。由歸納假設(shè)p-(q-1)+(f-1)=2p-q+f=2因此面數(shù)是f時也成立。 uvf1f2f3f4 uvf1f2f3f4第8頁，共55頁，2022年，5月20日，7點26分，星期三8 定理 （歐拉公式的推廣）設(shè)G是具有k(k2)個連通分支的平面圖，則nm+r=k+1.第9頁

5、，共55頁，2022年，5月20日，7點26分，星期三9 推論 若平面連通圖G有p個頂點q條邊且每個面都是由長為n的圈圍成的，則q=n(p-2)/(n-2)。 證 因為G的每個面都是長為n的圈圍成的，所以G的每條邊都在G的兩個面上。q=fn/2f=2q/np-q+2q/n=2q=n(p-2)/(n-2)第10頁，共55頁，2022年，5月20日，7點26分，星期三10最大(極大)可平面圖 一個圖稱為最大可平面圖，如果這個可平面圖再加入一條邊，新圖必然是不可平面的。 圖1再加一條邊就是k5，可證k5是不可平面圖。圖1是最大可平面圖。第11頁，共55頁，2022年，5月20日，7點26分，星期三1

6、1 最大(極大)平面圖的性質(zhì) uv最大(極大)平面圖的主要性質(zhì)：定理 最大(極大)平面圖是連通的. 定理 n(n3)階最大(極大)平面圖中不可能有割點和橋. 第12頁，共55頁，2022年，5月20日，7點26分，星期三12 推論 設(shè)G是一個有p個頂點q條邊的最大可平面圖，則G的每個面都是三角形，q=3p-6，p3。證 若G的一個面不是三角形, . v1v2v3v4 1、假如有兩點不相鄰，則在此面中把不相鄰的兩頂點連接起來，不影響平面性。矛盾，因此不可能有兩點不相鄰。第13頁，共55頁，2022年，5月20日，7點26分，星期三132、假如圈上每兩點都相鄰; . v1v2v3v4 若v1,v2

7、和v2,v4在G中都鄰接,我們可以看到這兩個邊不可能不相交; 綜合以上情況，最大平面圖的每個面都是三角形。第14頁，共55頁，2022年，5月20日，7點26分，星期三14 推論 設(shè)G是一個(p,q)可平面連通圖，而且G的每個面都是一個長為4的圈圍成的，則q=2p-4。 若G是任一有p個頂點q條邊的可平面圖p3，則q3p-6。 若G是2-連通的且沒有三角形，則q2p-4。 1、因為當(dāng)平面圖中每個面都是三角形時其邊數(shù)最多，由推論9.1.2，則q3p-6。 2、若G是2-連通的且沒有三角形,則G中任意兩個頂點都在同一個圈上。已知沒有三角形，所以圈的長都是4時邊數(shù)最多。所以q2p-4。第15頁，共5

8、5頁，2022年，5月20日，7點26分，星期三15推論 K5與K3,3都不是可平面圖 證 如果K5是平面圖，則5-10+f=2，即f=7。每個面至少三條邊， 7個面至少需要21條邊。 考慮到每條邊在兩個面上， 2q3f，即 2021。矛盾。 其實直接利用推論，任意(p,q)平面圖都滿足q3p-6，這里p3。 q=103p-6=9，這是不成立的。所以K5不是可平面圖。第16頁，共55頁，2022年，5月20日，7點26分，星期三16 如果K3,3是平面圖，則p-q+f=2，即6-9+f=2，亦即f=5。 在偶圖K3,3中每個圈的長至少為4，所以2q4f=20，q10，但q=9，矛盾。 所以K3

9、,3不是平面圖。第17頁，共55頁，2022年，5月20日，7點26分，星期三17 每個平面圖G中頂點度的最小值不超過5， 即(G)5。如果G的每個頂點的度大于5，也就是6，由歐拉定理，2q6p，即q3p。仍然用推論9.1.4，q3p-6。那么所有頂點的度數(shù)和大于或等于6p。不滿足推論9.1.4，q3p-6。 因此，每個平面圖G中頂點度的最小值不超過5，即(G)5。第18頁，共55頁，2022年，5月20日，7點26分，星期三18 頂點數(shù)p4的最大平面圖，(G)3。證 設(shè)G是最大平面圖，其最小度頂點為v。設(shè)G-v也是一個平面圖，v在G-v的一個面內(nèi)。在這個面內(nèi)，邊界上至少有三個頂點。由極大性，

10、v必然與這些頂點都相連。因此， (G)3。 v第19頁，共55頁，2022年，5月20日，7點26分，星期三19 定理 設(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條邊圍成

11、的面1個第20頁，共55頁，2022年，5月20日，7點26分，星期三20 證 因為C是G的哈密頓圈，所以G的所有頂點都在圈C上。因此C的內(nèi)部與外部不再含有G的頂點。 C的內(nèi)部的每個面都是由C上的某邊及C上兩頂點間的“連線”圍成的區(qū)域。 v1v2v3v4v5v6v7v8 設(shè)q是C的內(nèi)部(不含C)邊的條數(shù)，這些邊之集記為E。先把C內(nèi)部的邊都去掉，這時C里只有一個面。 把E的一條邊加入C中。就把C分成兩個面。 再加入E的另一條邊就把這兩個面之一分為兩個面，如此進行，直到把E的邊都加入為止。這樣，C的內(nèi)部就有q+1個面。第21頁，共55頁，2022年，5月20日，7點26分，星期三21f1+f2+f

12、3+.= 其次，由j條邊圍成面共fj個，這些面上的邊的總數(shù)為jfj，所以，C內(nèi)部的q+1個面上的邊數(shù)共有 。其中C上的每條邊在每個內(nèi)部面上至多出現(xiàn)一次且不是兩個內(nèi)部面的公共邊，所以在上述計數(shù)中C上每條邊各計數(shù)一次。 但E中的每條邊是兩個面之公共邊，所以每條邊計數(shù)兩次，因此 。 v1v2v3v4v5v6v7v8第22頁，共55頁，2022年，5月20日，7點26分，星期三22 從(2)式兩邊分別減去(1)式兩邊的兩倍便得到f1+f2+f3+.=(1)(2)用同樣的方法可得:(3)(4)(3)式兩邊分別減去(4)式的兩邊得第23頁，共55頁，2022年，5月20日，7點26分，星期三23 例 下圖

13、是一個哈密頓圖，證明：任一哈密頓圈上如果包含邊x，那么這個哈密頓圈上就一定不包含邊y。 xy 證 右圖G是哈密頓平面圖，它的面或由4條邊圍成，或由5條邊圍成，由定理有:2(f4-g4)+3(f5-g5)=0所以f4-g4能被3整除，即五個由4條邊圍成的面中有四個面在G的哈密頓圈C外，一個在C內(nèi)；或相反即一個在C外，四個在C的內(nèi)部。1234567第24頁，共55頁，2022年，5月20日，7點26分，星期三24 同樣，以y為公共邊的兩側(cè)的四條邊圍成的兩個面中，必一個在C的內(nèi)部，另一個在C的外部。這就得到矛盾，故C不能同時含邊x與y。 xy 因此，C的內(nèi)部與C的外部均至少有兩個四條邊圍成的面。 假

14、如C既含邊x又含邊y，則以x為公共邊的兩側(cè)的四條邊圍成的兩面中必有一個在C的內(nèi)部，另一個在C的外部。第25頁，共55頁，2022年，5月20日，7點26分，星期三25K5和K3,3不是平面圖。9.3 庫拉托斯基定理、對偶圖 平面圖的每個子圖都是平面圖，因此，平面圖中不含子圖K5和K3,3。 定義 設(shè)x=uv是圖G=(V,E)的一條邊，w不是G的頂點，則當(dāng)用邊uw和wv代替邊x時，就稱x被細分。 如果G的某些邊被細分，產(chǎn)生的圖稱為G的細分圖。 uv圖Gx uvwG的細分圖第26頁，共55頁，2022年，5月20日，7點26分，星期三26 定義 兩個圖稱為同胚的，如果它們都可以從同一個圖通過一系列

15、的邊細分得到。下面幾個圖是同胚的。 uv圖Gx uvwG的細分圖 圖與圖之間同胚第27頁，共55頁，2022年，5月20日，7點26分，星期三27 定義 所定義的的細分也稱為插入2度頂點。與之相對應(yīng)的還有一種方法：消去2度頂點。補充(1) 消去2度頂點v，見下圖中，由(1) 到(2) ；(2) 插入2度頂點v，見下圖中，從(2) 到(1) .定義 若G1G2，或經(jīng)過反復(fù)插入或消去2度頂點后所得G1G2，則稱G1與G2同胚. 第28頁，共55頁，2022年，5月20日，7點26分，星期三28 定理（庫拉托斯基,1930）一個圖是可平面的充分必要條件是它沒有同胚于K5和K3,3的子圖。 例 證明左

16、下圖不是可平面圖。因為它含有與K5同胚的子圖。 uv庫拉托斯基定理第29頁，共55頁，2022年，5月20日，7點26分，星期三29例 證明所示圖(1)與(2)均為非平面圖. (1) (2)右圖(1),(2)分別為原圖(1), (2)的子圖與K3,3, K5同胚. 子圖 (1) 子圖(2) 第30頁，共55頁，2022年，5月20日，7點26分，星期三30 定義 一個圖G的一個初等收縮由合并兩個鄰接的頂點u和v得到，即從G中去掉u和v，然后再加上一個新頂點w，使得w相鄰所有與u或v相鄰的頂點。 uv w 一個圖G可收縮到圖H，如果H可以從G經(jīng)一系列的初等收縮得到。圖G的初等收縮第31頁，共55

17、頁，2022年，5月20日，7點26分，星期三31 定理 一個圖是可平面的當(dāng)且僅當(dāng)它沒有一個可以收縮到K5或K3,3的子圖。 例 證明左下圖不是可平面圖。因為它可以收縮到K5 。第32頁，共55頁，2022年，5月20日，7點26分，星期三32 定義 設(shè)G=(V,E)是一個平面圖，由G按如下方法構(gòu)造一個圖G*，G*稱為G的對偶圖。 3、如果某條邊x僅在一個面中出現(xiàn)而不是兩個面的公共邊 (是不是橋？) ，則在G*中這個面對應(yīng)的頂點有一個環(huán)。 1、對G的每個面f對應(yīng)地有G*的一個頂點f*； 2、對G的每條邊e對應(yīng)地有G*的一條邊e*：G*的兩個頂點f*與g*由邊e*聯(lián)結(jié)，當(dāng)且僅當(dāng)G中與頂點f*與g

18、*對應(yīng)的面f與g有公共邊e。平面圖的對偶圖第33頁，共55頁，2022年，5月20日，7點26分，星期三33 下面兩圖中，實線邊圖為平面圖，虛線邊圖為其對偶圖. 實例第34頁，共55頁，2022年，5月20日，7點26分，星期三34對偶圖的性質(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頁，共55頁，2022年，5月20日，7點26分，星期

19、三35(6) 設(shè)G*是連通平面圖G的對偶圖，n*, m*, r*和n, m, r分別為G*和G的頂點數(shù)、邊數(shù)和面數(shù)，則1) n*= r；2) m*=m；3) r*=n；4) 設(shè)G*的頂點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頁，共55頁，2022年，5月20日，7點26分，星期三369.4 圖的頂點著色 定義 圖的一種(頂點)著色是指對圖的每個頂點指定一種顏色，使得沒有兩個相鄰的頂點有

20、同一顏色。 若圖G=(V,E)的頂點已著色，則著同一顏色的那些頂點之集稱為G的一個色組。 同一色組內(nèi)的各頂點不相鄰，這樣的頂點集合稱為G的一個頂點獨立集。 如果G有一個n著色，則G的頂點集V被這種n著色劃分為n個色組。圖G的一個n著色是用n種顏色對G的頂點著色。 121232121第37頁，共55頁，2022年，5月20日，7點26分，星期三37 定義 圖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頁，共55頁，2022年，5月20日，7點26分，

21、星期三38 定理 一個圖是可雙色的當(dāng)且僅當(dāng)它沒有奇數(shù)長的圈。一個圖是可雙色的當(dāng)且僅當(dāng)是偶圖。偶圖的充分必要條件是它的圈的長度都是偶數(shù)。若G是偶數(shù)個頂點的圈C2n，則(C2n)=2。若G是奇數(shù)個頂點的圈C2n+1，則(C2n+1)=3。 121232121 12122121第39頁，共55頁，2022年，5月20日，7點26分，星期三39 定理 設(shè)=(G)為圖G的頂點度的最大值，則G是(+1)可著色的。證 對頂點數(shù)p用歸納法。當(dāng)p=1時，結(jié)論成立。 假設(shè)對頂點數(shù)為p-1的圖定理成立，今設(shè)G是一個有p個頂點的圖。從G中去掉一個頂點v，則G-v有p-1個頂點，(G-v)(G)由歸納假設(shè)G-v是(+1

22、)可著色的。 但在G中與v相鄰的頂點最多有個，與v相鄰的頂點最多用去種顏色，剩下一種給頂點v著色即可。第40頁，共55頁，2022年，5月20日，7點26分，星期三40 定理 如果G是一個連通圖且不是完全圖也不是奇數(shù)長的圈，則G是(G)可著色的。第41頁，共55頁，2022年，5月20日，7點26分，星期三41定理 每個平面圖都是6可著色的。如果頂點數(shù)小于7，顯然是6可著色的。證 對平面圖的頂點數(shù)p用歸納法。 設(shè)G是一個有p個頂點的平面圖，由推論知G有頂點v，degv5，G-v是一個p-1個頂點的平面圖。 假設(shè)對p-1個頂點的平面圖是6可著色的，只需證對有p個頂點的平面圖也是6可著色的即可。

23、由歸納假設(shè)，G-v是6可著色的,與v相鄰的頂點至多5個，所以與v相鄰的頂點著色時至多用了5種色。 用另一種未用的顏色對v著色即得G的一個6著色。 因此,G是6可著色的。第42頁，共55頁，2022年，5月20日，7點26分，星期三42定理 每個可平面圖是5可著色的證 對可平面圖的頂點數(shù)進行歸納證明。當(dāng)p5時。定理顯然成立。 假設(shè)所有p個頂點的可平面圖都是5可著色的，需證所有p+1個頂點的可平面圖也是5可著色的。 設(shè)G是一個有p+1個頂點可平面圖，由推論知G中有一個頂點v使degv5。于是，G-v是一個有p個頂點的可平面圖，由歸納假設(shè)，G-v是5可著色的。 1、如果degv4,則必有一種顏色，在

24、G-v的一種5-著色時，對與v相鄰的頂點著色中未用此色，于是，用此色對頂點v著色便得到G的5-著色。第43頁，共55頁，2022年，5月20日，7點26分，星期三43 2、degv=5且對G-v的5-著色中，與v相鄰的5個頂點v1,v2,v3,v4,v5分別著5種顏色c1,c2,c3,c4,c5。 v1vv2v3v4v5 令G13為G-v的一個子圖，其頂點為著c1色或c3色的頂點之集V13,G13就是V13導(dǎo)出的子圖。(1)若v1和v3在G13的不同支中，則在含v1的支中交換兩種色，即原著c1色頂點改著c3色，原著c3色的頂點改著c1色。 c3c1c3c1c3c1c3c1c1c3c1c3c3然

25、后用c1給頂點v著色，于是得到G的一種5著色。第44頁，共55頁，2022年，5月20日，7點26分，星期三44 (2)若v1和v3在G13的同一個支中，則在G13中有一條從v1到v3的路，于是，在G中v1vv3與這條路合起來形成一個圈。 v1vv2v3v4v53131 這個圈或把v2圈在圈內(nèi)或把v4和v5圈在內(nèi)。 若令G24表示G-v的由著c2或c4色的頂點導(dǎo)出的子圖，則v2與v4屬于G24的不同支里。 424242 交換G24的含v2支中著c2色頂點與著c4色頂點的顏色，然后，用c2色為v著色得到G的一個5著色。 任何情況下，不存在聯(lián)結(jié)v2和v4的路且路上各頂點或著c2或著c4色。第45頁

26、，共55頁，2022年，5月20日，7點26分，星期三454色猜想 每個可平面圖是4可著色的。定理 每個可平面圖是4可著色的。 1852年，剛從倫敦大學(xué)畢業(yè)的哥斯尼從事地圖染色工作，他發(fā)現(xiàn)在一幅正規(guī)地圖中，最多只用四種顏色著色，就能把這些國家區(qū)別開來。 如果國家用圖的頂點來表示，兩個頂點相鄰當(dāng)且僅當(dāng)兩個國家相鄰，就形成一個平面圖。第46頁，共55頁，2022年，5月20日，7點26分，星期三469.5 圖的邊著色 定義 圖G的一個k邊著色是對G的每條邊指定k種色之一，使得任何兩條相鄰的邊被指定色是不同的。 如果圖G是k邊著色的，但不(k-1)邊著色的，則稱G的邊色數(shù)為k，G的邊色數(shù)記為(G)。

27、 12314234 如果=(G)是圖G的頂點的最大度數(shù)，則顯然有(G)。右圖存在一個4邊著色不存在3邊著色(G)=4第47頁，共55頁，2022年，5月20日，7點26分，星期三47 對某些特殊類型的圖，我們能容易確定它的邊色數(shù)。 例如：偶數(shù)長的圈C2n的邊色數(shù)是(C2n)=2。 121232121 12122121對奇數(shù)長的圈C2n+1有(C2n+1)=3。第48頁，共55頁，2022年，5月20日，7點26分，星期三48 定理 如果p是不為1的奇數(shù)，則(Kp)=p。 如果p是偶數(shù)，則(Kp)=p-1。證 設(shè)p是奇數(shù)，把Kp的p個頂點安放在正p邊形的頂點上，對正p邊形的p個邊分別著p個不同色。 而平行于p邊形的對角線的邊著與這條邊同一顏色，這就得到Kp的一個p邊著色。 1、證明當(dāng)p是奇數(shù)時，Kp是p邊著色的。第49頁，共55頁，2022年，5月20日，7點26分，星期三49Kp最多有(p-1) (Kp)/2條邊;(p-1)/2條平行邊已關(guān)聯(lián)了(p-1)個頂點，所以在Kp的邊著色中至多有(p-1)/2條同色邊。Kp最多有(p-1) (Kp)/2p(p-1/2)條邊;(Kp)p;所以(Kp)=p。