圖論第二十五節(jié)課

1、 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 1本次課主要內(nèi)容本次課主要內(nèi)容(一一)、與色數(shù)有關(guān)的幾類圖、與色數(shù)有關(guān)的幾類圖(二二)、完美圖簡(jiǎn)介、完美圖簡(jiǎn)介與色數(shù)有關(guān)的幾類圖和完美圖與色數(shù)有關(guān)的幾類圖和完美圖 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 2 1、臨界圖、臨界圖(一一)、與色數(shù)有關(guān)的幾類圖、與色數(shù)有關(guān)的幾類圖 定義定義1 若對(duì)圖若對(duì)圖G的任意真子圖的任意真子圖H，都有，都有 ，則，則稱稱G是臨界圖。點(diǎn)色數(shù)為是臨界圖。點(diǎn)色數(shù)為k的臨界圖稱為的臨界圖稱為k臨

2、界圖。臨界圖。()( )HG3臨界圖臨界圖4臨界圖臨界圖非臨界圖非臨界圖 注：臨界圖由狄拉克在注：臨界圖由狄拉克在1952年首先提出并研究。上面年首先提出并研究。上面的的4臨界圖是臨界圖是Grotzsch在在1958年提出的。年提出的。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 3 定理定理1 臨界圖有如下性質(zhì)臨界圖有如下性質(zhì) (1) k色圖均有色圖均有k臨界子圖；臨界子圖； (2) 每個(gè)臨界圖均為簡(jiǎn)單連通圖；每個(gè)臨界圖均為簡(jiǎn)單連通圖； (3) 若若G是是k臨界圖，則臨界圖，則k-1k-1。 證明：證明： (1)是顯然的。是顯然

3、的。 (2) 因?yàn)閯h掉環(huán)或平行邊中的一條邊并不破壞原有的頂因?yàn)閯h掉環(huán)或平行邊中的一條邊并不破壞原有的頂點(diǎn)正常著色，所以每個(gè)臨界圖是單圖；又因?yàn)閯h掉色數(shù)點(diǎn)正常著色，所以每個(gè)臨界圖是單圖；又因?yàn)閯h掉色數(shù)較小的分支，剩下部分的圖的色數(shù)和原圖色數(shù)相等，所較小的分支，剩下部分的圖的色數(shù)和原圖色數(shù)相等，所以，臨界圖必須是連通圖。以，臨界圖必須是連通圖。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 4 (3) 若不然，若不然， k-1 k-1。 設(shè)設(shè)d(v)=。因?yàn)?。因?yàn)镚 G是是k k臨界圖，所以臨界圖，所以G-vG-v是是k-1k-1可正常

4、頂可正常頂點(diǎn)著色的。設(shè)點(diǎn)著色的。設(shè)是是G-vG-v的的k-1k-1正常頂點(diǎn)著色方案，顯然，正常頂點(diǎn)著色方案，顯然，它可以擴(kuò)充為它可以擴(kuò)充為G G的的k-1k-1正常點(diǎn)著色方案。這與正常點(diǎn)著色方案。這與G G是是k k臨界圖臨界圖相矛盾。相矛盾。 推論：每個(gè)推論：每個(gè)k色圖至少有色圖至少有k個(gè)度不小于個(gè)度不小于k-1的頂點(diǎn)。的頂點(diǎn)。 證明：因證明：因G是是k色圖，所以，它包含色圖，所以，它包含k臨界子圖臨界子圖G1,所以所以有：有：(G(G1 1)k-1,)k-1,即即G G1 1中至少有中至少有k k個(gè)頂點(diǎn)，其度數(shù)不小于個(gè)頂點(diǎn)，其度數(shù)不小于k-1k-1。所以，。所以，G G中中至少有至少有k個(gè)

5、度不小于個(gè)度不小于k-1的頂點(diǎn)。的頂點(diǎn)。 例例1 利用上面推論證明：對(duì)任意圖利用上面推論證明：對(duì)任意圖G，有：，有：()()1GG 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 5 證明：設(shè)證明：設(shè)G的點(diǎn)色數(shù)為的點(diǎn)色數(shù)為 。由推論，。由推論，G中至少有中至少有 個(gè)頂點(diǎn)，其度數(shù)不小于個(gè)頂點(diǎn)，其度數(shù)不小于()()1GG ()G()G()1G 所以，所以， ，即：，即：()()1GG 例例2 求證：臨界圖沒(méi)有割點(diǎn)。求證：臨界圖沒(méi)有割點(diǎn)。 證明：設(shè)證明：設(shè)G是是k臨界圖。如果臨界圖。如果G有割點(diǎn)有割點(diǎn)v, 設(shè)設(shè)G1,G2,Gr是是G-v的分

6、支。又設(shè)第的分支。又設(shè)第i個(gè)分支頂點(diǎn)集為個(gè)分支頂點(diǎn)集為Vi (1ir)ir)。 設(shè)設(shè)Hi=GViv, (1ir)。則。則Hi是是k-1可正常點(diǎn)著色可正常點(diǎn)著色的，現(xiàn)對(duì)每個(gè)的，現(xiàn)對(duì)每個(gè)Hi進(jìn)行進(jìn)行k-1正常點(diǎn)著色，且正常點(diǎn)著色，且v都分配同一種顏色，都分配同一種顏色，那么，將著色后的那么，將著色后的Hi合在一起，得到合在一起，得到G的的k-1正常點(diǎn)著色方正常點(diǎn)著色方案，這與案，這與G是是k色圖矛盾。所以臨界圖沒(méi)有割點(diǎn)。色圖矛盾。所以臨界圖沒(méi)有割點(diǎn)。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 6 例例3 求證：僅有的求證：僅有的1臨

7、界圖是臨界圖是k1;僅有的僅有的2臨界圖是臨界圖是K2;僅僅有的有的3臨界圖奇圈。臨界圖奇圈。 證明：由于證明：由于1色圖是空?qǐng)D，所以色圖是空?qǐng)D，所以1臨界圖只能是臨界圖只能是K1;2色色圖是偶圖，所以，圖是偶圖，所以，2臨界圖只能是臨界圖只能是K2; 3色圖必然含有奇圈，色圖必然含有奇圈，而奇圈的色數(shù)是而奇圈的色數(shù)是3，所以，所以，3臨界圖只能是奇圈。臨界圖只能是奇圈。 例例4 求證：布魯克斯定理等價(jià)于下述命題：若求證：布魯克斯定理等價(jià)于下述命題：若G是是k臨臨界圖界圖(k4), 且不是完全圖，則且不是完全圖，則2mn(k-1)+1,其中其中m為為G的的邊數(shù)而邊數(shù)而n為頂點(diǎn)數(shù)。為頂點(diǎn)數(shù)。 證

8、明：證明：(1) 由布魯克斯定理推例由布魯克斯定理推例4中命題。中命題。 因因G是是k臨界圖臨界圖,所以所以G是連通單圖，又是連通單圖，又k4, 所以所以G不能不能是奇圈，再由是奇圈，再由G不是完全圖，所以由布魯克斯定理有不是完全圖，所以由布魯克斯定理有 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 7 定理定理2(布魯克斯，布魯克斯，1941) 若若G是連通的是連通的單圖，并且它既不是奇圈，又不是完全單圖，并且它既不是奇圈，又不是完全圖圖 ()()GG 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1

9、 0.5 0 0.5 1 n 8 k。 再由再由k臨界圖的性質(zhì)，有臨界圖的性質(zhì)，有k-1.k-1.所以：所以：()2( )(1)v V Gmd vn (1)(1)knk(1)1n k (2) 由例由例4中命題推布魯克斯定理。中命題推布魯克斯定理。 因?yàn)檫B通單圖因?yàn)檫B通單圖G不是奇圈，也不是完全圖。設(shè)不是奇圈，也不是完全圖。設(shè)G的的k臨臨界子圖是界子圖是H。 情形情形1， H是奇圈。是奇圈。 在這種情況下，由于在這種情況下，由于G不是奇圈，所以，不是奇圈，所以，H之外必然之外必然有邊和有邊和H相連，即相連，即(G)3,(G)3,另一方面，另一方面，k(G)=k(H)=3,k(G)=k(H)=3,

10、所所 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 9 以，以，k(G)(G);(G); 情形情形2， H是完全圖是完全圖Hk 在這種情況下，由于在這種情況下，由于G是連通的非完全圖，那么在是連通的非完全圖，那么在H之外，必然有邊和之外，必然有邊和H相連，即相連，即K(H)=k(G);K(H)=k(G); 情形情形3， H既不是奇圈又不是完全圖，由例既不是奇圈又不是完全圖，由例3知道，知道，k4。H滿足例滿足例4中條件。中條件。 所以，由例所以，由例4中的結(jié)論有：中的結(jié)論有：() ()2()()( ()1)1H n Hm Hn Hk

11、 H()( ()1)1n Hk G 所以，有：所以，有：1()( ()1)()Hk Gn H 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 10 即證明：即證明：()()Gk G 2、唯一可著色圖、唯一可著色圖 對(duì)圖的頂點(diǎn)進(jìn)行正常著色，實(shí)際上給出圖的頂點(diǎn)集合對(duì)圖的頂點(diǎn)進(jìn)行正常著色，實(shí)際上給出圖的頂點(diǎn)集合的一種劃分，不同的著色方案，給出的劃分一般不同。的一種劃分，不同的著色方案，給出的劃分一般不同。但是，也存在一類特殊圖，對(duì)于任意的最優(yōu)著色方案，但是，也存在一類特殊圖，對(duì)于任意的最優(yōu)著色方案，導(dǎo)出的頂點(diǎn)劃分卻是相同的。為此，我們給出如

12、下定義。導(dǎo)出的頂點(diǎn)劃分卻是相同的。為此，我們給出如下定義。 定義定義2 設(shè)簡(jiǎn)單標(biāo)定圖設(shè)簡(jiǎn)單標(biāo)定圖G的點(diǎn)色數(shù)是的點(diǎn)色數(shù)是k, 如果在任意的如果在任意的k正正常點(diǎn)著色方案下，導(dǎo)出的頂點(diǎn)集合劃分唯一，稱常點(diǎn)著色方案下，導(dǎo)出的頂點(diǎn)集合劃分唯一，稱G是唯一是唯一k可著色圖，簡(jiǎn)稱唯一可著色圖?？芍珗D，簡(jiǎn)稱唯一可著色圖。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 11 例例5 考察下面考察下面3色圖是否是唯一色圖是否是唯一3可著色圖?？芍珗D。v3v2v1G1v1G2v5v4v3v2G3v5v4v3v2v1 解：解：(1) 對(duì)于對(duì)于G1來(lái)說(shuō)

13、，來(lái)說(shuō)，G1的任意的任意3正常著色方案導(dǎo)出的正常著色方案導(dǎo)出的頂點(diǎn)劃分均是頂點(diǎn)劃分均是v1, v2v3，所以，所以，G1是唯是唯一一3可著色圖；可著色圖； 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 12v1G2v5v4v3v2 (2) 對(duì)于對(duì)于G2來(lái)說(shuō)，來(lái)說(shuō)，G2的任意的任意3正常著色方案導(dǎo)出的頂點(diǎn)正常著色方案導(dǎo)出的頂點(diǎn)劃分均是劃分均是v1, v2，v4v3,v5，所以，所以，G2是是唯一唯一3可著色圖；例如：可著色圖；例如：v1G2v5v4v3v2v1G2v5v4v3v2 (3) 對(duì)于對(duì)于G3來(lái)說(shuō)，來(lái)說(shuō)，G3不是唯一不是唯一3

14、可著色圖；因?yàn)椋嚎芍珗D；因?yàn)椋篏3v5v4v3v2v1G3v5v4v3v2v1 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 13 下面給出唯一可著色圖的幾個(gè)特征。下面給出唯一可著色圖的幾個(gè)特征。 定理定理2(哈拉里，哈拉里，1968） 設(shè)設(shè)G是唯一是唯一k可著色圖，可著色圖，k2, 則：則： (1) k-1;k-1; (2) 在在G G的任意一種的任意一種k k著色中，著色中，G G的任意兩個(gè)色組的并的的任意兩個(gè)色組的并的導(dǎo)出子圖是連通的。導(dǎo)出子圖是連通的。 證明：證明： (1) 若不然，設(shè)若不然，設(shè) k-1, 令令d(u) =

15、,則則 ( )1uN ukuN (u) 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 14 設(shè)設(shè)是是G G的的k k著色方案，因?yàn)橹桨福驗(yàn)?，所以，所以，在在下，至少有一種顏色下，至少有一種顏色u u及其鄰域均沒(méi)有用到，設(shè)該色及其鄰域均沒(méi)有用到，設(shè)該色為為m,m,改變改變u u的顏色為的顏色為m,m,其余點(diǎn)的著色不變，這樣得到其余點(diǎn)的著色不變，這樣得到G G的的k k著色方案著色方案1 1. .顯然，顯然，與與1 1導(dǎo)出的導(dǎo)出的G G的頂點(diǎn)劃分不同，這的頂點(diǎn)劃分不同，這與與G G是唯一可著色圖矛盾。是唯一可著色圖矛盾。 ()1

16、uNuk (2) 若不然，則存在若不然，則存在G的的k k著色方案著色方案和和G G的兩個(gè)色組的兩個(gè)色組C C1 1與與C C2 2, ,使得使得H=GCH=GC1 1CC2 2 不連通。設(shè)不連通。設(shè)H H1 1與與H H2 2是是H H的兩個(gè)分支。的兩個(gè)分支。 因?yàn)橐驗(yàn)镚是唯一可著色圖，所以，對(duì)任意點(diǎn)是唯一可著色圖，所以，對(duì)任意點(diǎn)u和其鄰域和其鄰域N(u), 它們?cè)谒鼈冊(cè)谙?，必然用完了下，必然用完了k k種顏色，否則，由種顏色，否則，由(1)(1)的的證明，得到證明，得到G G是非唯一可著色圖。是非唯一可著色圖。 這樣，這樣，H1與與H2中同時(shí)含有中同時(shí)含有C1和和C2中的頂點(diǎn)。中的頂點(diǎn)。

17、0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 15 如果交換如果交換C1V(H1)與與C2V(H1)中頂點(diǎn)顏色，得到中頂點(diǎn)顏色，得到G的的k著色著色1 1, ,顯然，顯然，與與1 1的色劃分是不同的。這與的色劃分是不同的。這與G G的著的著色唯一性矛盾。色唯一性矛盾。v1Gv5v4v3v2 例如，在下圖例如，在下圖G中，由黃色、紅色色組導(dǎo)出的子圖是中，由黃色、紅色色組導(dǎo)出的子圖是連通的。連通的。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 16 定理定理3 (夏特朗）每

18、個(gè)唯一夏特朗）每個(gè)唯一n (n2)可著色圖是可著色圖是(n-1)連通的。連通的。 證明：設(shè)證明：設(shè)G是唯一是唯一n可著色圖可著色圖(n2)。 情形情形1，如果，如果G是完全圖，則是完全圖，則G=Kn,顯然顯然G是是n-1連通的。連通的。 情形情形2，如果，如果G是非完全圖，假若是非完全圖，假若G不是不是(n-1)連通的，那連通的，那么其連通度么其連通度k(G)n-2n-2。于是。于是G G中存在點(diǎn)集中存在點(diǎn)集S S，S S=n-2, =n-2, 使得使得G-SG-S不連通。不連通。 設(shè)設(shè)是是G G的的n n著色方案。在該方案下，至少有兩種顏色著色方案。在該方案下，至少有兩種顏色c c1 1與與

19、c c2 2，S S中的頂點(diǎn)都沒(méi)有使用。中的頂點(diǎn)都沒(méi)有使用。 而由定理而由定理2的的(2), 著著c1與與c2色的點(diǎn)導(dǎo)出子圖必連通。所以色的點(diǎn)導(dǎo)出子圖必連通。所以,著著c1與與c2色的頂點(diǎn)在色的頂點(diǎn)在G-S中的同一個(gè)分支中，設(shè)該分支為中的同一個(gè)分支中，設(shè)該分支為G1. 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 17 在在G-S中取一個(gè)不在中取一個(gè)不在G1中的點(diǎn)中的點(diǎn)u,將其染上將其染上c1色，這樣得到色，這樣得到G的另一個(gè)的另一個(gè)n著色方案。著色方案。 顯然，兩種著色方案導(dǎo)出的色劃分不同，這與條件矛盾。顯然，兩種著色方案導(dǎo)出的色

20、劃分不同，這與條件矛盾。 推論：設(shè)推論：設(shè)G是唯一是唯一n(n2)可著色圖，可著色圖，是任意一種是任意一種n n著色著色方案，方案，則由則由的的任意任意k個(gè)色組導(dǎo)出的子圖是個(gè)色組導(dǎo)出的子圖是(k-1)連通的。連通的。 證明：顯然，任意證明：顯然，任意k個(gè)色組導(dǎo)出子圖是唯一個(gè)色組導(dǎo)出子圖是唯一k可著色圖，可著色圖，由定理由定理3得到推論結(jié)論。得到推論結(jié)論。 注：注： (1) 唯一唯一1可著色圖是零圖；可著色圖是零圖； (2) 唯一唯一2可著色圖是偶圖；可著色圖是偶圖； 除此之外，沒(méi)有簡(jiǎn)單的結(jié)論！除此之外，沒(méi)有簡(jiǎn)單的結(jié)論！ 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2

21、 1 0.5 0 0.5 1 n 18 定理定理4 每個(gè)唯一每個(gè)唯一4可著色可平面圖都是極大可平面圖?？芍善矫鎴D都是極大可平面圖。 證明：只需證明：證明：只需證明：m=3n-6即可。即可。 一方面：一方面：G是可平面圖，有：是可平面圖，有：m3n-6;3n-6; 另一方面：設(shè)另一方面：設(shè)G是唯一是唯一4可著色的可平面圖，可著色的可平面圖，是一種是一種4 4著色方案，色組記為著色方案，色組記為V Vi i(1i4).(1i4). 因?yàn)橐驗(yàn)閕j時(shí)，時(shí)，GViVVj j 是連通的，所以是連通的，所以: :( )1ijijm G VVnn 于是：于是：41()(1)36ijijim Gnnn 所以

22、，所以，m=3n-6,即即G是極大可平面圖。是極大可平面圖。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 19 定義定義3 若圖若圖G的點(diǎn)色數(shù)是的點(diǎn)色數(shù)是k，且，且G中不含有三角形，稱中不含有三角形，稱G是一個(gè)不含三角形的是一個(gè)不含三角形的k色圖。色圖。 3、不含三角形的、不含三角形的k色圖色圖 例如：例如：不含三角形的三色圖不含三角形的三色圖不含三角形的不含三角形的4色圖色圖 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 20 數(shù)學(xué)家狄拉克數(shù)學(xué)家狄拉克1953年在其論

23、文年在其論文“k色圖的構(gòu)造色圖的構(gòu)造”中提出一中提出一個(gè)問(wèn)題：對(duì)于任意大的一個(gè)正整數(shù)個(gè)問(wèn)題：對(duì)于任意大的一個(gè)正整數(shù)k, 是否存在一個(gè)圖，不是否存在一個(gè)圖，不包含三角形但色數(shù)是包含三角形但色數(shù)是k？ 上面問(wèn)題分別由勃蘭克上面問(wèn)題分別由勃蘭克.斯德卡茲斯德卡茲(1954), 米歇爾斯基米歇爾斯基(1955)獨(dú)立作出了回答。獨(dú)立作出了回答。 米歇爾斯基米歇爾斯基(1955)給出了由一個(gè)不含三角形的給出了由一個(gè)不含三角形的k色圖色圖Gk構(gòu)造一個(gè)不含三角形的構(gòu)造一個(gè)不含三角形的k+1色圖色圖Gk+1的方法。的方法。 構(gòu)造方法：設(shè)構(gòu)造方法：設(shè)Gk的頂點(diǎn)是的頂點(diǎn)是u1,u2,un, 添加點(diǎn)添加點(diǎn)v1,v2,

24、vn和點(diǎn)和點(diǎn)v。將將vi與與ui的所有鄰點(diǎn)及的所有鄰點(diǎn)及v相連，相連，1inin。如此得到的圖就是一。如此得到的圖就是一個(gè)不含三角形的個(gè)不含三角形的k+1k+1色圖。色圖。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 21 例例6，利用米歇爾斯基方法構(gòu)造一個(gè)不含三角形的，利用米歇爾斯基方法構(gòu)造一個(gè)不含三角形的4色圖。色圖。 解：注意到解：注意到C5是不含三角形的是不含三角形的3色圖，于是由色圖，于是由C5可以構(gòu)造可以構(gòu)造出不含三角形的出不含三角形的4色圖。色圖。不含三角形的不含三角形的3色圖色圖u4u3u2u1u5不含三角形的不含

25、三角形的4色圖色圖u1u2u3u4u5v1v2v3v4v5v 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 22 注：利用米歇爾斯基方法構(gòu)造一個(gè)不含三角形的注：利用米歇爾斯基方法構(gòu)造一個(gè)不含三角形的k色圖時(shí)，色圖時(shí)，結(jié)果圖與初始圖有關(guān)。結(jié)果圖與初始圖有關(guān)。 例例7，設(shè)，設(shè)Gk是不含三角形的是不含三角形的k色圖，頂點(diǎn)數(shù)為色圖，頂點(diǎn)數(shù)為f(k), 而而Gk+1是是由米歇爾斯基方法構(gòu)造出來(lái)的不含三角形的由米歇爾斯基方法構(gòu)造出來(lái)的不含三角形的k+1色圖，其頂點(diǎn)色圖，其頂點(diǎn)數(shù)設(shè)為數(shù)設(shè)為f(k+1)。求出。求出f(k)的遞推公式。的遞推公式。

26、解：解：(1)( )1f kf k 定理定理5 (米歇爾斯基米歇爾斯基)對(duì)于任意正整數(shù)對(duì)于任意正整數(shù)k, 存在不含三角形的存在不含三角形的k色圖。色圖。 1961年，數(shù)學(xué)家年，數(shù)學(xué)家Erdos用概率方法證明了更一般結(jié)論：用概率方法證明了更一般結(jié)論： 定理定理6 (Erdos)對(duì)于任意正整數(shù)對(duì)于任意正整數(shù)m和和n, 存在一個(gè)圍長(zhǎng)超過(guò)存在一個(gè)圍長(zhǎng)超過(guò)m的的n色圖。色圖。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 23 1968年，羅瓦斯構(gòu)造性地證明了上面定理年，羅瓦斯構(gòu)造性地證明了上面定理6 注：定理注：定理6實(shí)際上是數(shù)學(xué)家凱利提出

27、的一個(gè)猜想。實(shí)際上是數(shù)學(xué)家凱利提出的一個(gè)猜想。(二二)、完美圖簡(jiǎn)介、完美圖簡(jiǎn)介 1、相關(guān)概念、相關(guān)概念 定義定義4 (1)單單 圖圖G的團(tuán)：若單圖的團(tuán)：若單圖G的一個(gè)頂點(diǎn)子集的一個(gè)頂點(diǎn)子集S在在G中的導(dǎo)出子圖是完全圖中的導(dǎo)出子圖是完全圖,則稱則稱S是是G的一個(gè)團(tuán)；的一個(gè)團(tuán)； (2) 單圖單圖G的團(tuán)數(shù)：?jiǎn)螆D的團(tuán)數(shù)：?jiǎn)螆DG的最大團(tuán)包含的頂點(diǎn)數(shù)稱為的最大團(tuán)包含的頂點(diǎn)數(shù)稱為G的團(tuán)數(shù)，記為的團(tuán)數(shù)，記為c l (G) ,即：即：()maxcl GS SG是 的團(tuán) 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 24 顯然，圖顯然，圖G的點(diǎn)色數(shù)與團(tuán)

28、數(shù)的關(guān)系為：的點(diǎn)色數(shù)與團(tuán)數(shù)的關(guān)系為： 定義定義5 設(shè)設(shè)G是一個(gè)圖。若對(duì)是一個(gè)圖。若對(duì)G的每個(gè)點(diǎn)導(dǎo)出子圖的每個(gè)點(diǎn)導(dǎo)出子圖H，均，均有有 ,則稱則稱G為完美圖。為完美圖。()()Gcl G()()Hcl H 例如例如Kn, 偶圖是完美圖，而不含三角形但含奇圈的圖不偶圖是完美圖，而不含三角形但含奇圈的圖不是完美圖。是完美圖。 因?yàn)椴缓切蔚牡嫒Φ膱D的團(tuán)數(shù)為因?yàn)椴缓切蔚牡嫒Φ膱D的團(tuán)數(shù)為2，但色數(shù)為，但色數(shù)為3，所以，它不能是完美圖。所以，它不能是完美圖。 注：完美圖問(wèn)題是點(diǎn)著色的進(jìn)一步討論題材，屬于比較注：完美圖問(wèn)題是點(diǎn)著色的進(jìn)一步討論題材，屬于比較高深和困難的問(wèn)題。高深和困難的問(wèn)題。

29、0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 25 圖圖G的點(diǎn)獨(dú)立數(shù)記為的點(diǎn)獨(dú)立數(shù)記為(G)(G)或或。 定義定義6 設(shè)設(shè)G是一個(gè)圖。由是一個(gè)圖。由G中若干互不鄰接的頂點(diǎn)作成中若干互不鄰接的頂點(diǎn)作成的子集稱為的子集稱為G的一個(gè)點(diǎn)獨(dú)立集；的一個(gè)點(diǎn)獨(dú)立集；G中含頂點(diǎn)數(shù)最多的點(diǎn)獨(dú)中含頂點(diǎn)數(shù)最多的點(diǎn)獨(dú)立集稱為立集稱為G的最大獨(dú)立集，其包含的頂點(diǎn)數(shù)稱為獨(dú)立數(shù)。的最大獨(dú)立集，其包含的頂點(diǎn)數(shù)稱為獨(dú)立數(shù)。 對(duì)該問(wèn)題的研究，早在對(duì)該問(wèn)題的研究，早在1932年哥尼和加萊就已經(jīng)涉及，年哥尼和加萊就已經(jīng)涉及，但到了但到了1960年，完美圖概念才被貝爾熱正式

30、提出。所以，年，完美圖概念才被貝爾熱正式提出。所以，貝爾熱是完美圖研究的代表人物。貝爾熱是完美圖研究的代表人物。 注：關(guān)于圖的覆蓋與圖的點(diǎn)獨(dú)立數(shù)之間的關(guān)系，加萊得注：關(guān)于圖的覆蓋與圖的點(diǎn)獨(dú)立數(shù)之間的關(guān)系，加萊得到了一些很漂亮的結(jié)論。其中之一是：到了一些很漂亮的結(jié)論。其中之一是： 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 26 定理定理7 偶圖的補(bǔ)圖是完美圖。偶圖的補(bǔ)圖是完美圖。 分析：欲證分析：欲證 是完美圖，要證明對(duì)任意是完美圖，要證明對(duì)任意 有有 GHG()()Hcl G 由于由于 也是某偶圖的補(bǔ)，所以只需要證明也是某偶圖的

31、補(bǔ)，所以只需要證明H()()Gcl G 補(bǔ)充定理：設(shè)補(bǔ)充定理：設(shè)G是一個(gè)偶圖，記是一個(gè)偶圖，記h為為G的最大匹配包含的最大匹配包含的邊數(shù)，的邊數(shù)，i為為G的最大獨(dú)立集包含的頂點(diǎn)數(shù)，的最大獨(dú)立集包含的頂點(diǎn)數(shù)，j為構(gòu)成覆蓋為構(gòu)成覆蓋G的頂點(diǎn)的的頂點(diǎn)的G的最小點(diǎn)邊集合，則：的最小點(diǎn)邊集合，則：i = j = m+n-h。 2、關(guān)于色數(shù)的完美圖的主要結(jié)論、關(guān)于色數(shù)的完美圖的主要結(jié)論 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 27 定理定理8 圖圖G是完美圖當(dāng)且僅當(dāng)對(duì)是完美圖當(dāng)且僅當(dāng)對(duì)G的每個(gè)真導(dǎo)出子圖的每個(gè)真導(dǎo)出子圖H,存在一個(gè)獨(dú)立集存

32、在一個(gè)獨(dú)立集I，使得：，使得： 所以：所以： 偶圖的補(bǔ)圖是完美圖。偶圖的補(bǔ)圖是完美圖。()()Hcl GG()G 證明：在證明：在 的正常著色方案下，每個(gè)色組對(duì)應(yīng)的正常著色方案下，每個(gè)色組對(duì)應(yīng)G的一的一個(gè)頂點(diǎn)或者個(gè)頂點(diǎn)或者K2。這樣，。這樣， 應(yīng)該是應(yīng)該是G的最小點(diǎn)覆蓋中包含的最小點(diǎn)覆蓋中包含的點(diǎn)數(shù)和邊數(shù)。由補(bǔ)充定理：它等于的點(diǎn)數(shù)和邊數(shù)。由補(bǔ)充定理：它等于G中最大獨(dú)立集包含中最大獨(dú)立集包含的頂點(diǎn)數(shù)，即等于的頂點(diǎn)數(shù)，即等于 的團(tuán)數(shù)。所以有：的團(tuán)數(shù)。所以有：G()()cl HIcl H 證明略。證明略。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0

33、.5 1 n 28 定義定義7 設(shè)設(shè)S是圖是圖G的頂點(diǎn)集合的一個(gè)劃分。如果的頂點(diǎn)集合的一個(gè)劃分。如果S的每個(gè)的每個(gè)子集在子集在G中的導(dǎo)出子圖均是完全圖，稱中的導(dǎo)出子圖均是完全圖，稱S是是G的一個(gè)完全分的一個(gè)完全分類。類。G的最小完全分類所包含的元素個(gè)數(shù)稱為的最小完全分類所包含的元素個(gè)數(shù)稱為G的完全數(shù)，的完全數(shù)，記為記為(G),(G),即：即： 3、關(guān)于獨(dú)立數(shù)的完美圖、關(guān)于獨(dú)立數(shù)的完美圖()minGS SG為 的完全分類 注：注： 。這是因?yàn)楠?dú)立集中任意一點(diǎn)應(yīng)該屬。這是因?yàn)楠?dú)立集中任意一點(diǎn)應(yīng)該屬于于S中的某個(gè)頂點(diǎn)子集，同時(shí)，中的某個(gè)頂點(diǎn)子集，同時(shí)，S中每個(gè)頂點(diǎn)子集最多包含中每個(gè)頂點(diǎn)子集最多包含獨(dú)立集中的一個(gè)元素。獨(dú)立集中的一個(gè)元素。()()GG 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.