圖論課件與色數(shù)有關(guān)的幾類圖和完美圖

圖論課件與色數(shù)有關(guān)的幾類圖和完美圖1第一頁，共三十二頁，2022年，8月28日本次課主要內(nèi)容(一)、與色數(shù)有關(guān)的幾類圖(二)、完美圖簡介與色數(shù)有關(guān)的幾類圖和完美圖2第二頁，共三十二頁，2022年，8月28日

1、臨界圖(一)、與色數(shù)有關(guān)的幾類圖定義1若對(duì)圖G的任意真子圖H，都有，則稱G是臨界圖。點(diǎn)色數(shù)為k的臨界圖稱為k臨界圖。3臨界圖4臨界圖非臨界圖注：臨界圖由狄拉克在1952年首先提出并研究。上面的4臨界圖是Grotzsch在1958年提出的。3第三頁，共三十二頁，2022年，8月28日定理1臨界圖有如下性質(zhì)

(1)k色圖均有k臨界子圖；

(2)每個(gè)臨界圖均為簡單連通圖；

(3)若G是k臨界圖，則δ≥k-1。證明：(1)是顯然的。

(2)因?yàn)閯h掉環(huán)或平行邊中的一條邊并不破壞原有的頂點(diǎn)正常著色，所以每個(gè)臨界圖是單圖；又因?yàn)閯h掉色數(shù)較小的分支，剩下部分的圖的色數(shù)和原圖色數(shù)相等，所以，臨界圖必須是連通圖。4第四頁，共三十二頁，2022年，8月28日

(3)若不然，δ<k-1。設(shè)d(v)=δ。因?yàn)镚是k臨界圖，所以G-v是k-1可正常頂點(diǎn)著色的。設(shè)п是G-v的k-1正常頂點(diǎn)著色方案，顯然，它可以擴(kuò)充為G的k-1正常點(diǎn)著色方案。這與G是k臨界圖相矛盾。推論：每個(gè)k色圖至少有k個(gè)度不小于k-1的頂點(diǎn)。證明：因G是k色圖，所以，它包含k臨界子圖G1,所以有：δ(G1)≥k-1,即G1中至少有k個(gè)頂點(diǎn)，其度數(shù)不小于k-1。所以，G中至少有k個(gè)度不小于k-1的頂點(diǎn)。例1利用上面推論證明：對(duì)任意圖G，有：5第五頁，共三十二頁，2022年，8月28日證明：設(shè)G的點(diǎn)色數(shù)為。由推論，G中至少有個(gè)頂點(diǎn)，其度數(shù)不小于所以，，即：例2求證：臨界圖沒有割點(diǎn)。證明：設(shè)G是k臨界圖。如果G有割點(diǎn)v,設(shè)G1,G2,…,Gr是G-v的分支。又設(shè)第i個(gè)分支頂點(diǎn)集為Vi(1≦i≦r)。設(shè)Hi=G[Vi∪｛v｝],(1≦i≦r)。則Hi是k-1可正常點(diǎn)著色的，現(xiàn)對(duì)每個(gè)Hi進(jìn)行k-1正常點(diǎn)著色，且v都分配同一種顏色，那么，將著色后的Hi合在一起，得到G的k-1正常點(diǎn)著色方案，這與G是k色圖矛盾。所以臨界圖沒有割點(diǎn)。6第六頁，共三十二頁，2022年，8月28日例3求證：僅有的1臨界圖是k1;僅有的2臨界圖是K2;僅有的3臨界圖奇圈。證明：由于1色圖是空圖，所以1臨界圖只能是K1;2色圖是偶圖，所以，2臨界圖只能是K2;3色圖必然含有奇圈，而奇圈的色數(shù)是3，所以，3臨界圖只能是奇圈。例4求證：布魯克斯定理等價(jià)于下述命題：若G是k臨界圖(k≥4),且不是完全圖，則2m≥n(k-1)+1,其中m為G的邊數(shù)而n為頂點(diǎn)數(shù)。證明：(1)由布魯克斯定理推例4中命題。因G是k臨界圖,所以G是連通單圖，又k≥4,所以G不能是奇圈，再由G不是完全圖，所以由布魯克斯定理有7第七頁，共三十二頁，2022年，8月28日

k≦Δ。再由k臨界圖的性質(zhì)，有δ≥k-1.所以：

(2)由例4中命題推布魯克斯定理。因?yàn)檫B通單圖G不是奇圈，也不是完全圖。設(shè)G的k臨界子圖是H。情形1，H是奇圈。在這種情況下，由于G不是奇圈，所以，H之外必然有邊和H相連，即Δ(G)≥3,另一方面，k(G)=k(H)=3,所8第八頁，共三十二頁，2022年，8月28日以，k(G)≦Δ(G);情形2，H是完全圖Hk在這種情況下，由于G是連通的非完全圖，那么在H之外，必然有邊和H相連，即Δ≥K(H)=k(G);情形3，H既不是奇圈又不是完全圖，由例3知道，k≥4。H滿足例4中條件。所以，由例4中的結(jié)論有：所以，有：9第九頁，共三十二頁，2022年，8月28日即證明：

2、唯一可著色圖對(duì)圖的頂點(diǎn)進(jìn)行正常著色，實(shí)際上給出圖的頂點(diǎn)集合的一種劃分，不同的著色方案，給出的劃分一般不同。但是，也存在一類特殊圖，對(duì)于任意的最優(yōu)著色方案，導(dǎo)出的頂點(diǎn)劃分卻是相同的。為此，我們給出如下定義。定義2設(shè)簡單標(biāo)定圖G的點(diǎn)色數(shù)是k,如果在任意的k正常點(diǎn)著色方案下，導(dǎo)出的頂點(diǎn)集合劃分唯一，稱G是唯一k可著色圖，簡稱唯一可著色圖。10第十頁，共三十二頁，2022年，8月28日例5考察下面3色圖是否是唯一3可著色圖。v3v2v1G1v1G2v5v4v3v2G3v5v4v3v2v1解：(1)對(duì)于G1來說，G1的任意3正常著色方案導(dǎo)出的頂點(diǎn)劃分均是｛｛v1｝,｛v2｝｛v3｝｝，所以，G1是唯一3可著色圖；11第十一頁，共三十二頁，2022年，8月28日v1G2v5v4v3v2

(2)對(duì)于G2來說，G2的任意3正常著色方案導(dǎo)出的頂點(diǎn)劃分均是｛｛v1｝,｛v2，v4｝｛v3,v5｝｝，所以，G2是唯一3可著色圖；例如：v1G2v5v4v3v2v1G2v5v4v3v2

(3)對(duì)于G3來說，G3不是唯一3可著色圖；因?yàn)椋篏3v5v4v3v2v1G3v5v4v3v2v112第十二頁，共三十二頁，2022年，8月28日下面給出唯一可著色圖的幾個(gè)特征。定理2(哈拉里，1968）設(shè)G是唯一k可著色圖，k≥2,則：

(1)δ≥k-1;

(2)在G的任意一種k著色中，G的任意兩個(gè)色組的并的導(dǎo)出子圖是連通的。證明：(1)若不然，設(shè)δ<k-1,令d(u)=δ,則uN(u)13第十三頁，共三十二頁，2022年，8月28日設(shè)п是G的k著色方案，因?yàn)?，所以，在п下，至少有一種顏色u及其鄰域均沒有用到，設(shè)該色為m,改變u的顏色為m,其余點(diǎn)的著色不變，這樣得到G的k著色方案п1.顯然，п與п1導(dǎo)出的G的頂點(diǎn)劃分不同，這與G是唯一可著色圖矛盾。

(2)若不然，則存在G的k著色方案п和G的兩個(gè)色組C1與C2,使得H=G[C1∪C2]不連通。設(shè)H1與H2是H的兩個(gè)分支。因?yàn)镚是唯一可著色圖，所以，對(duì)任意點(diǎn)u和其鄰域N(u),它們在п下，必然用完了k種顏色，否則，由(1)的證明，得到G是非唯一可著色圖。這樣，H1與H2中同時(shí)含有C1和C2中的頂點(diǎn)。14第十四頁，共三十二頁，2022年，8月28日如果交換C1∩V(H1)與C2∩V(H1)中頂點(diǎn)顏色，得到G的k著色п1,顯然，п與п1的色劃分是不同的。這與G的著色唯一性矛盾。v1Gv5v4v3v2例如，在下圖G中，由黃色、紅色色組導(dǎo)出的子圖是連通的。15第十五頁，共三十二頁，2022年，8月28日定理3(夏特朗）每個(gè)唯一n(n≥2)可著色圖是(n-1)連通的。證明：設(shè)G是唯一n可著色圖(n≥2)。情形1，如果G是完全圖，則G=Kn,顯然G是n-1連通的。情形2，如果G是非完全圖，假若G不是(n-1)連通的，那么其連通度k(G)≦n-2。于是G中存在點(diǎn)集S，｜S｜=n-2,使得G-S不連通。設(shè)п是G的n著色方案。在該方案下，至少有兩種顏色c1與c2，S中的頂點(diǎn)都沒有使用。而由定理2的(2),著c1與c2色的點(diǎn)導(dǎo)出子圖必連通。所以,著c1與c2色的頂點(diǎn)在G-S中的同一個(gè)分支中，設(shè)該分支為G1.16第十六頁，共三十二頁，2022年，8月28日在G-S中取一個(gè)不在G1中的點(diǎn)u,將其染上c1色，這樣得到G的另一個(gè)n著色方案。顯然，兩種著色方案導(dǎo)出的色劃分不同，這與條件矛盾。推論：設(shè)G是唯一n(n≥2)可著色圖，п是任意一種n著色方案，則由п的任意k個(gè)色組導(dǎo)出的子圖是(k-1)連通的。證明：顯然，任意k個(gè)色組導(dǎo)出子圖是唯一k可著色圖，由定理3得到推論結(jié)論。注：(1)唯一1可著色圖是零圖；

(2)唯一2可著色圖是偶圖；除此之外，沒有簡單的結(jié)論！17第十七頁，共三十二頁，2022年，8月28日定理4每個(gè)唯一4可著色可平面圖都是極大可平面圖。證明：只需證明：m=3n-6即可。一方面：G是可平面圖，有：m≦3n-6;另一方面：設(shè)G是唯一4可著色的可平面圖，п是一種4著色方案，色組記為Vi(1≦i≦4).因?yàn)閕≠j時(shí)，G[Vi∪Vj]是連通的，所以:于是：所以，m=3n-6,即G是極大可平面圖。18第十八頁，共三十二頁，2022年，8月28日定義3若圖G的點(diǎn)色數(shù)是k，且G中不含有三角形，稱G是一個(gè)不含三角形的k色圖。

3、不含三角形的k色圖例如：不含三角形的三色圖不含三角形的4色圖19第十九頁，共三十二頁，2022年，8月28日數(shù)學(xué)家狄拉克1953年在其論文“k色圖的構(gòu)造”中提出一個(gè)問題：對(duì)于任意大的一個(gè)正整數(shù)k,是否存在一個(gè)圖，不包含三角形但色數(shù)是k？上面問題分別由勃蘭克.斯德卡茲(1954),米歇爾斯基(1955)獨(dú)立作出了回答。米歇爾斯基(1955)給出了由一個(gè)不含三角形的k色圖Gk構(gòu)造一個(gè)不含三角形的k+1色圖Gk+1的方法。構(gòu)造方法：設(shè)Gk的頂點(diǎn)是u1,u2,…,un,添加點(diǎn)v1,v2,…vn和點(diǎn)v。將vi與ui的所有鄰點(diǎn)及v相連，1≦i≦n。如此得到的圖就是一個(gè)不含三角形的k+1色圖。20第二十頁，共三十二頁，2022年，8月28日例6，利用米歇爾斯基方法構(gòu)造一個(gè)不含三角形的4色圖。解：注意到C5是不含三角形的3色圖，于是由C5可以構(gòu)造出不含三角形的4色圖。不含三角形的3色圖u4u3u2u1u5不含三角形的4色圖u1u2u3u4u5v1v2v3v4v5v21第二十一頁，共三十二頁，2022年，8月28日注：利用米歇爾斯基方法構(gòu)造一個(gè)不含三角形的k色圖時(shí)，結(jié)果圖與初始圖有關(guān)。例7，設(shè)Gk是不含三角形的k色圖，頂點(diǎn)數(shù)為f(k),而Gk+1是由米歇爾斯基方法構(gòu)造出來的不含三角形的k+1色圖，其頂點(diǎn)數(shù)設(shè)為f(k+1)。求出f(k)的遞推公式。解：定理5(米歇爾斯基)對(duì)于任意正整數(shù)k,存在不含三角形的k色圖。

1961年，數(shù)學(xué)家Erdos用概率方法證明了更一般結(jié)論：定理6(Erdos)對(duì)于任意正整數(shù)m和n,存在一個(gè)圍長超過m的n色圖。22第二十二頁，共三十二頁，2022年，8月28日

1968年，羅瓦斯構(gòu)造性地證明了上面定理6注：定理6實(shí)際上是數(shù)學(xué)家凱利提出的一個(gè)猜想。(二)、完美圖簡介

1、相關(guān)概念定義4(1)單圖G的團(tuán)：若單圖G的一個(gè)頂點(diǎn)子集S在G中的導(dǎo)出子圖是完全圖,則稱S是G的一個(gè)團(tuán)；

(2)單圖G的團(tuán)數(shù)：單圖G的最大團(tuán)包含的頂點(diǎn)數(shù)稱為G的團(tuán)數(shù)，記為cl(G),即：23第二十三頁，共三十二頁，2022年，8月28日顯然，圖G的點(diǎn)色數(shù)與團(tuán)數(shù)的關(guān)系為：定義5設(shè)G是一個(gè)圖。若對(duì)G的每個(gè)點(diǎn)導(dǎo)出子圖H，均有,則稱G為完美圖。例如Kn,偶圖是完美圖，而不含三角形但含奇圈的圖不是完美圖。因?yàn)椴缓切蔚牡嫒Φ膱D的團(tuán)數(shù)為2，但色數(shù)為3，所以，它不能是完美圖。注：完美圖問題是點(diǎn)著色的進(jìn)一步討論題材，屬于比較高深和困難的問題。24第二十四頁，共三十二頁，2022年，8月28日圖G的點(diǎn)獨(dú)立數(shù)記為α(G)或α。定義6設(shè)G是一個(gè)圖。由G中若干互不鄰接的頂點(diǎn)作成的子集稱為G的一個(gè)點(diǎn)獨(dú)立集；G中含頂點(diǎn)數(shù)最多的點(diǎn)獨(dú)立集稱為G的最大獨(dú)立集，其包含的頂點(diǎn)數(shù)稱為獨(dú)立數(shù)。對(duì)該問題的研究，早在1932年哥尼和加萊就已經(jīng)涉及，但到了1960年，完美圖概念才被貝爾熱正式提出。所以，貝爾熱是完美圖研究的代表人物。注：關(guān)于圖的覆蓋與圖的點(diǎn)獨(dú)立數(shù)之間的關(guān)系，加萊得到了一些很漂亮的結(jié)論。其中之一是：25第二十五頁，共三十二頁，2022年，8月28日定理7偶圖的補(bǔ)圖是完美圖。分析：欲證是完美圖，要證明對(duì)任意有

由于也是某偶圖的補(bǔ)，所以只需要證明補(bǔ)充定理：設(shè)G是一個(gè)偶圖，記h為G的最大匹配包含的邊數(shù)，i為G的最大獨(dú)立集包含的頂點(diǎn)數(shù)，j為構(gòu)成覆蓋G的頂點(diǎn)的G的最小點(diǎn)邊集合，則：i=j=m+n-h。

2、關(guān)于色數(shù)的完美圖的主要結(jié)論26第二十六頁，共三十二頁，2022年，8月28日定理8圖G是完美圖當(dāng)且僅當(dāng)對(duì)G的每個(gè)真導(dǎo)出子圖H,存在一個(gè)獨(dú)立集I，使得：所以：偶圖的補(bǔ)圖是完美圖。證明：在的正常著色方案下，每個(gè)色組對(duì)應(yīng)G的一個(gè)頂點(diǎn)或者K2。這樣，應(yīng)該是G的最小點(diǎn)覆蓋中包含的點(diǎn)數(shù)和邊數(shù)。由補(bǔ)充定理：它等于G中最大獨(dú)立集包含的頂點(diǎn)數(shù)，即等于的團(tuán)數(shù)。所以有：證明略。27第二十七頁，共三十二頁，2022年，8月28日定義7設(shè)S是圖G的頂點(diǎn)集合的一個(gè)劃分。如果S的每個(gè)子集在G中的導(dǎo)出子圖均是完全圖，稱S是G的一個(gè)完全分類。G的最小完全分類所包含的元素個(gè)數(shù)稱為G的完全數(shù)，記為θ(G),即：

3、關(guān)于獨(dú)立數(shù)的完美圖注：。這是因?yàn)楠?dú)立集中任意一點(diǎn)應(yīng)該屬于S中的某個(gè)頂點(diǎn)子集，同