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

圖論課件與色數(shù)有關(guān)的幾類圖和完美圖1第1頁，課件共32頁，創(chuàng)作于2023年2月本次課主要內(nèi)容(一)、與色數(shù)有關(guān)的幾類圖(二)、完美圖簡介與色數(shù)有關(guān)的幾類圖和完美圖2第2頁，課件共32頁，創(chuàng)作于2023年2月

1、臨界圖(一)、與色數(shù)有關(guān)的幾類圖定義1若對圖G的任意真子圖H，都有，則稱G是臨界圖。點色數(shù)為k的臨界圖稱為k臨界圖。3臨界圖4臨界圖非臨界圖注：臨界圖由狄拉克在1952年首先提出并研究。上面的4臨界圖是Grotzsch在1958年提出的。3第3頁，課件共32頁，創(chuàng)作于2023年2月定理1臨界圖有如下性質(zhì)

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

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

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

(2)因為刪掉環(huán)或平行邊中的一條邊并不破壞原有的頂點正常著色，所以每個臨界圖是單圖；又因為刪掉色數(shù)較小的分支，剩下部分的圖的色數(shù)和原圖色數(shù)相等，所以，臨界圖必須是連通圖。4第4頁，課件共32頁，創(chuàng)作于2023年2月

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

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

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

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

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

(3)對于G3來說，G3不是唯一3可著色圖；因為：G3v5v4v3v2v1G3v5v4v3v2v112第12頁，課件共32頁，創(chuàng)作于2023年2月下面給出唯一可著色圖的幾個特征。定理2(哈拉里，1968）設(shè)G是唯一k可著色圖，k≥2,則：

(1)δ≥k-1;

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

(2)若不然，則存在G的k著色方案п和G的兩個色組C1與C2,使得H=G[C1∪C2]不連通。設(shè)H1與H2是H的兩個分支。因為G是唯一可著色圖，所以，對任意點u和其鄰域N(u),它們在п下，必然用完了k種顏色，否則，由(1)的證明，得到G是非唯一可著色圖。這樣，H1與H2中同時含有C1和C2中的頂點。14第14頁，課件共32頁，創(chuàng)作于2023年2月如果交換C1∩V(H1)與C2∩V(H1)中頂點顏色，得到G的k著色п1,顯然，п與п1的色劃分是不同的。這與G的著色唯一性矛盾。v1Gv5v4v3v2例如，在下圖G中，由黃色、紅色色組導(dǎo)出的子圖是連通的。15第15頁，課件共32頁，創(chuàng)作于2023年2月定理3(夏特朗）每個唯一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中存在點集S，｜S｜=n-2,使得G-S不連通。設(shè)п是G的n著色方案。在該方案下，至少有兩種顏色c1與c2，S中的頂點都沒有使用。而由定理2的(2),著c1與c2色的點導(dǎo)出子圖必連通。所以,著c1與c2色的頂點在G-S中的同一個分支中，設(shè)該分支為G1.16第16頁，課件共32頁，創(chuàng)作于2023年2月在G-S中取一個不在G1中的點u,將其染上c1色，這樣得到G的另一個n著色方案。顯然，兩種著色方案導(dǎo)出的色劃分不同，這與條件矛盾。推論：設(shè)G是唯一n(n≥2)可著色圖，п是任意一種n著色方案，則由п的任意k個色組導(dǎo)出的子圖是(k-1)連通的。證明：顯然，任意k個色組導(dǎo)出子圖是唯一k可著色圖，由定理3得到推論結(jié)論。注：(1)唯一1可著色圖是零圖；

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

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

1961年，數(shù)學(xué)家Erdos用概率方法證明了更一般結(jié)論：定理6(Erdos)對于任意正整數(shù)m和n,存在一個圍長超過m的n色圖。22第22頁，課件共32頁，創(chuàng)作于2023年2月

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

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

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

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

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

3、關(guān)于獨立數(shù)的完美圖注：。這是因為獨立集中任意一點應(yīng)該屬于S中的某個頂點子