圖論第七章 圖的著色

圖論課件第七章圖的著色1第一頁，共三十一頁，編輯于2023年，星期二第七章圖的著色一、圖的邊著色二、圖的頂點(diǎn)著色主要內(nèi)容三、與色數(shù)有關(guān)的幾類圖和完美圖四、色多項(xiàng)式五、List著色與全著色10學(xué)時(shí)講授本章2第二頁，共三十一頁，編輯于2023年，星期二本次課主要內(nèi)容(一)、相關(guān)概念(二)、幾類特殊圖的邊色數(shù)圖的邊著色(三)、邊著色的應(yīng)用3第三頁，共三十一頁，編輯于2023年，星期二現(xiàn)實(shí)生活中很多問題，可以模型為所謂的邊著色問題來處理。例如排課表問題。(一)、相關(guān)概念排課表問題：設(shè)有m位教師，n個(gè)班級，其中教師xi要給班級yj上pij節(jié)課。求如何在最少節(jié)次排完所有課。建模：令X=｛x1,x2,…,xm｝,Y=｛y1,y2,…,yn｝,xi與yj間連pij條邊，得偶圖G=(X,Y).于是，問題轉(zhuǎn)化為如何在G中將邊集E劃分為互不相交的p個(gè)匹配，且使得p最小。如果每個(gè)匹配中的邊用同一種顏色染色，不同匹配中的邊用不同顏色染色，則問題轉(zhuǎn)化為在G中給每條邊染色，相鄰邊染不同色，至少需要的顏色數(shù)。4第四頁，共三十一頁，編輯于2023年，星期二這就需要我們研究所謂的邊著色問題。定義1設(shè)G是圖，對G的邊進(jìn)行染色，若相鄰邊染不同顏色，則稱對G進(jìn)行正常邊著色；如果能用k中顏色對圖G進(jìn)行正常邊著色，稱G是k邊可著色的。正常邊著色定義2設(shè)G是圖，對G進(jìn)行正常邊著色需要的最少顏色數(shù)，稱為G的邊色數(shù)，記為：5第五頁，共三十一頁，編輯于2023年，星期二注：對圖的正常邊著色，實(shí)際上是對G的邊集合的一種劃分，使得每個(gè)劃分塊是G的一個(gè)邊獨(dú)立集(無環(huán)時(shí)是匹配);圖的邊色數(shù)對應(yīng)的是圖的最小獨(dú)立集劃分?jǐn)?shù)。因此，圖的邊著色，本質(zhì)上是對應(yīng)實(shí)際問題中的“劃分”問題或“分類”問題。6第六頁，共三十一頁，編輯于2023年，星期二在對G正常邊著色時(shí)，著相同顏色的邊集稱為該正常著色的一個(gè)色組。(二)、幾類特殊圖的邊色數(shù)

1、偶圖的邊色數(shù)定理1證明：設(shè)又設(shè)Δ=n。設(shè)顏色集合設(shè)為｛0，1，2，…，n-1｝,

п是Km,n的一種n著色方案，滿足：7第七頁，共三十一頁，編輯于2023年，星期二我們證明：上面的著色是正常邊著色。對Km,n中任意的兩條鄰接邊xiyj和xiyk。若則：i+j(modn)=i+k(modn),得到j(luò)=k，矛盾！所以，上面著色是正常作色。所以：又顯然，所以，例1用最少的顏色數(shù)對K3,4正常邊著色。8第八頁，共三十一頁，編輯于2023年，星期二定理2(哥尼，1916)若G是偶圖，則x2x1x0y3y2y1y0定義3設(shè)п是G的一種正常邊著色，若點(diǎn)u關(guān)聯(lián)的邊的著色沒有用到色i，則稱點(diǎn)u缺i色。證明：我們對G的邊數(shù)m作數(shù)學(xué)歸納。當(dāng)m=1時(shí)，Δ=1，有9第九頁，共三十一頁，編輯于2023年，星期二設(shè)G是具有m條邊的偶圖。設(shè)對于小于m條邊的偶圖來說命題成立。取uv∈E(G),考慮G1=G-uv,由歸納假設(shè)有：這說明，G1存在一種Δ(G)邊著色方案п。對于該著色方案，因?yàn)閡v未著色，所以點(diǎn)u與v均至少缺少一種色。情形1如果u與v均缺同一種色i,則在G1+uv中給uv著色i,而G1其它邊，按п方案著色。這樣得到G的Δ著色方案，所以：情形2如果u缺色i,而v缺色j，但不缺色i。10第十頁，共三十一頁，編輯于2023年，星期二設(shè)H(i,j)表示G1中由i色邊與j色邊導(dǎo)出的子圖。顯然，該圖每個(gè)分支是i色邊和j色邊交替出現(xiàn)的路或圈。對于H(i,j)中含點(diǎn)v的分支來說，因v缺色j,但不缺色i,所以，在H(i,j)中,點(diǎn)v的度數(shù)為1。這說明，H(i,j)中含v的分支是一條路P。進(jìn)一步地，我們可以說明，上面的路P不含點(diǎn)u。因?yàn)?，如果P含有點(diǎn)u,那么P必然是一條長度為偶數(shù)的路，這樣，P+uv是G中的奇圈，這與G是偶圖矛盾！既然P不含點(diǎn)u,所以我們可以交換P中著色，而不破壞G1的正常邊著色。但交換著色后，u與v均缺色i,于是由情形1,可以得到G的Δ正常邊著色，即證明：11第十一頁，共三十一頁，編輯于2023年，星期二

2、簡單圖的邊色數(shù)引理：設(shè)G是簡單圖，x與y1是G中不相鄰的兩個(gè)頂點(diǎn)，п是G的一個(gè)正常k邊著色。若對該著色п，x,y1以及與x相鄰點(diǎn)均至少缺少一種顏色，則G+xy1是k邊可著色的。正常k邊著色圖Gx1y1xx2xk缺色缺色缺色缺色缺色正常k邊著色圖G1x1y1xx2xk12第十二頁，共三十一頁，編輯于2023年，星期二定理3(維津定理，1964)若G是單圖，則：證明：只需要證明即可。采用對G的邊數(shù)m作數(shù)學(xué)歸納證明。當(dāng)m=1時(shí)，Δ=1，設(shè)當(dāng)邊數(shù)少于m時(shí)，結(jié)論成立。下面考慮邊數(shù)為m≥2的單圖G。設(shè)xy∈E(G)，令G1=G-xy。由歸納假設(shè)有：13第十三頁，共三十一頁，編輯于2023年，星期二于是，存在G1的Δ(G)+1正常邊作色п。顯然G1的每個(gè)頂點(diǎn)都至少缺少一種顏色。根據(jù)引理知G1+xy是Δ(G)+1可著色的。即證明：注:(1)根據(jù)維津定理，單圖可以按邊色數(shù)分成兩類圖，一是色數(shù)等于Δ(G)的單圖，二是色數(shù)等于Δ(G)+1的單圖。

(2)維津(Vizing):1937年出生于烏克蘭的基輔。1954年開始在托木斯克大學(xué)學(xué)習(xí)數(shù)學(xué)，1959年大學(xué)畢業(yè)保送到莫斯科斯特克羅夫研究所攻讀博士學(xué)位，研究函數(shù)逼近論。但這不是他的興趣所在，因此沒有獲得學(xué)位。1966年在季科夫的指導(dǎo)下獲得博士學(xué)位。和大多數(shù)數(shù)學(xué)家一樣，維津在音樂方面具有一定才能。14第十四頁，共三十一頁，編輯于2023年，星期二維津在攻讀博士學(xué)位期間，發(fā)現(xiàn)并證明了上面的維津定理。他當(dāng)時(shí)把論文投向一家非常著名的雜志，但由于審稿人認(rèn)為問題本身沒有意義而遭到拒絕。后來在另外一家地方雜志發(fā)表時(shí)，定理早已出名。維津認(rèn)為：一名數(shù)學(xué)家應(yīng)該不斷研究與發(fā)現(xiàn)新結(jié)果，然后讓時(shí)間來檢驗(yàn)其重要性。

3、三類特殊簡單圖的邊色數(shù)定理4設(shè)G是單圖且Δ(G)>0。若G中只有一個(gè)最大度點(diǎn)或恰有兩個(gè)相鄰的最大度點(diǎn)，則：15第十五頁，共三十一頁，編輯于2023年，星期二證明:(1)若單圖G恰有一個(gè)最大度點(diǎn)u，取u的一個(gè)鄰點(diǎn)v,作G1=G-uv。那么，Δ(G1)=Δ(G)-1。由維津定理：于是G1是可Δ(G)正常邊著色的，因?yàn)镚1的每個(gè)頂點(diǎn)都至少缺少一種顏色，所以由引理：G1+uv=G是可Δ(G)正常邊著色的，即：

(2)若單圖G恰有2個(gè)鄰接的最大度點(diǎn)u與v。設(shè)G1=G-uv。那么，Δ(G1)=Δ(G)-1。由維津定理：16第十六頁，共三十一頁，編輯于2023年，星期二于是G1是可Δ(G)正常邊著色的，因?yàn)镚1的每個(gè)頂點(diǎn)都至少缺少一種顏色，所以由引理：G1+uv=G是可Δ(G)正常邊著色的，即：例2確定下圖的邊色數(shù)。G1G2解：由定理4知道：G317第十七頁，共三十一頁，編輯于2023年，星期二定理5設(shè)G是單圖。若點(diǎn)數(shù)n=2k+1且邊數(shù)m>kΔ,則：證明：若不然，由維津定理，設(shè)п是G的Δ(G)正常邊著色方案，對于G的每個(gè)色組來說，包含的邊數(shù)至多(n-1)/2=k。這樣：，與條件矛盾。例3確定下圖的邊色數(shù)。G解：由定理5：18第十八頁，共三十一頁，編輯于2023年，星期二定理6設(shè)G是奇數(shù)階Δ正則單圖,若Δ>0,則：證明：設(shè)n=2k+1。因G是Δ正則單圖，且Δ>0，所以：例4設(shè)n=2k+1,k>0。求由定理5：解：由定理6知：19第十九頁，共三十一頁，編輯于2023年，星期二例5求出彼得森圖的邊色數(shù)。解：一方面，彼得森圖中去掉任意一個(gè)1因子后，剩下兩個(gè)5點(diǎn)圈，所以，不能進(jìn)行1因子分解，所以：另一方面：通過驗(yàn)證，G可以4正常作色。所以：G20第二十頁，共三十一頁，編輯于2023年，星期二例6(1)設(shè)G=(X,Y)是一個(gè)最大度為Δ的偶圖，求證，G是某個(gè)Δ正則偶圖G*的子圖。

(2)用(1)證明：偶圖的邊色數(shù)等于其最大度。證明(1)按如下方式構(gòu)造G*。如果G不是Δ正則偶圖，先將G按下圖所示方式構(gòu)造成為G1XXYYG(1)G(2)G121第二十一頁，共三十一頁，編輯于2023年，星期二

G(1)與G(2)分別是G的拷貝。紅色邊表示xi與xi(yi與yi)之間的一條連線，要求是d(xi)<Δ(d(yi)<Δ),這樣得到的新偶圖就是G1。XXYYG(1)G(2)G1如果G1是Δ正則偶圖，則G*=G1否則，在G1的基礎(chǔ)上，重復(fù)上面的過程，可得到G2,這樣不斷下去，最終得到包含G的Δ正則偶圖G*。

(2)由(1)對于任意最大度為Δ的偶圖G,均存在G的Δ正則母圖G*。又由于正則偶圖存在1因子分解，所以，G*可以劃分為Δ個(gè)1因子，從而其邊色數(shù)為Δ。這樣G的邊色數(shù)也為Δ。22第二十二頁，共三十一頁，編輯于2023年，星期二例7證明：每個(gè)哈密爾頓3正則圖都有泰特(Tait)著色。3正則圖的正常3邊著色稱為泰特著色。證明：設(shè)G是3正則H圖，C是G的一個(gè)H圈，則C是偶圈，所以C是2可正常邊著色的。因G-C是G的一個(gè)1因子，所以，可1正常邊著色。因此，G是可以3邊正常著色的，即G有泰特著色。注：數(shù)學(xué)家泰特提出泰特著色主要是基于他想由此證明“四色定理”。因?yàn)槿绻C明了每個(gè)3連通3正則平面圖的邊色數(shù)是3，那么“四色定理”就得到證明。泰特認(rèn)為：每個(gè)3連通3正則平面圖是H圖，所以由上面例7，泰特深信他已經(jīng)證明了“四色定理”?？墒牵浅＿z憾，數(shù)學(xué)家托特通過構(gòu)圖方式否定了每個(gè)3連通3正則平面圖是H圖的斷言?？梢圆榭吹谒恼抡n件。23第二十三頁，共三十一頁，編輯于2023年，星期二定理7（Vizing定理）設(shè)無環(huán)圖G中邊的最大重?cái)?shù)為μ，則例8下圖是一個(gè)邊色數(shù)達(dá)到Δ+μ的圖，其中Δ=4,μ=2。

24第二十四頁，共三十一頁，編輯于2023年，星期二邊著色對應(yīng)的實(shí)際問題就是圖的匹配分解問題。邊色數(shù)對應(yīng)的是最小匹配分解問題。所以，生活中的許多問題都可模型為邊著色問題來解決。(三)、邊著色的應(yīng)用例1(排課表問題)在一個(gè)學(xué)校中，有7個(gè)教師12個(gè)班級。在每周5天教學(xué)日條件下，教課的要求由如下矩陣給出：x1x2x3x4x6x5x7y2y1y8y7y6y5y4y3y10y9y11y1225第二十五頁，共三十一頁，編輯于2023年，星期二其中，pij表示xi必須教yj班的節(jié)數(shù)。求：

(1)一天分成幾節(jié)課，才能滿足所提出的要求？x1x2x3x4x6x5x7y2y1y8y7y6y5y4y3y10y9y11y12

(2)若安排出每天8節(jié)課的時(shí)間表，需要多少間教室？解：問題可模型為一個(gè)偶圖。一節(jié)課對應(yīng)邊正常著色的一個(gè)色組。由于G是偶圖，所以邊色數(shù)為G的最大度35。這樣，最少總課時(shí)為35節(jié)課。平均每天要安排7節(jié)課。如果每天安排8節(jié)課，因?yàn)镚的總邊數(shù)為240，所以需要的教室數(shù)為240/40=6