（精選）匹配理論和色數(shù)問題 -.ppt

1、1,圖論Graphic Theory,闕夏制作,2,第六章內(nèi)容回顧,2F最大流最小割切標(biāo)號算法： （1）標(biāo)號過程（任意）； （2）增流過程； EK修正算法： （1）標(biāo)號過程（按層次）； （2）增流過程；,3,第七章 匹配理論和色數(shù)問題,1 最大匹配 2 Hall定理 3 匈牙利算法及例 4 最佳匹配 5 最佳匹配算法及例 6 色數(shù)問題,4,7-1 最大匹配,匹配是圖論中一個重要內(nèi)容，它在所謂“人員分配問題”和“最優(yōu)分配問題”有重要應(yīng)用。,5,1 最大匹配1,具體問題描述： 有n個女士和n個男士參加舞會，每位女士與其中若干位男士相識，每位男士與其中若干位女士相識，問如何安排，使得盡量多配對的男女

2、舞伴相識。,6,1 最大匹配1,下圖就是一種分配方法：,(f1,m3), (f2,m1) ,(f3,m2) ,(f4,m5) ,(f5,m4),7,1 最大匹配定義,定義：若圖G=(V,E)的頂點可以分成X，Y兩個子集，每個子集里的頂點互不相鄰，這樣的圖稱為二分圖。,8,1 最大匹配定義1,定義：若M是圖G=(V,E)的邊子集，且M中的任意兩條邊在G中不相鄰，則稱M為G中的一個匹配，M中的每條邊的兩個端點稱為在M中是配對的。,M=(f1,m2),(f2,m1),(f3,m4),(f4,m5),9,1 最大匹配定義2,定義：若圖G中每個頂點均被M許配時，稱M為G中的一個完備匹配。,M=(f1,m

3、3), (f2,m1) ,(f3,m2) ,(f4,m5) ,(f5,m4),10,1 最大匹配定義3,定義：圖G中邊數(shù)最多的匹配M，稱為G中的一個最大匹配。,M=(f1,m3), (f2,m1) ,(f3,m2) ,(f5,m5),11,1 最大匹配定義4,定義：若匹配M的某邊和頂點v關(guān)聯(lián)，稱v是M-飽和的，否則就是M-不飽和的。,M=(f1,m3), (f2,m1) ,(f3,m2) ,(f5,m5),飽和的,不飽和的,12,1 最大匹配定義5,定義：若M是圖G的一個匹配，若從G中一個頂點到另一個頂點存在一條道路，此路徑由屬于M和不屬于M的邊交替出現(xiàn)組成的，則稱此路徑為交互道。,M=(f1

4、,m3), (f2,m1) ,(f3,m2) ,(f4,m5) ,(f5,m4),P=f1m3f4m5f2m1f5m4,13,1 最大匹配定義6,定義：若交互道的兩個端點為關(guān)于M的不飽和頂點時，稱此交互道為可增廣道路。,M=(f2,m5), (f3,m2) ,(f4,m3) ,(f5,m4),P=m1f2m5f4m3f1 是一條可增廣道路。,14,1 最大匹配定義8,M=(f2,m5), (f3,m2) ,(f4,m3) ,(f5,m4),P=m1f2m5f4m3f1 是一條可增廣道路。,M=(f1,m3), (f2,m1) ,(f3,m2) ,(f4,m5),(f5,m4),15,1 最大匹

5、配1,具體問題描述： 有n個女士和n個男士參加舞會，每位女士與其中若干位男士相識，每位男士與其中若干位女士相識，問如何安排，使得盡量多配對的男女舞伴相識。,16,1 最大匹配 Berge定理,定理7.1(Berge 1957)：M為最大匹配的充要條件是：圖G中不存在可增廣道路。,M=(f1,m3), (f2,m1) ,(f3,m2) ,(f5,m5),17,1 最大匹配定義7,對稱差：A、B是兩個集合， A B=(AB)-(AB),18,7-2 Hall定理,設(shè)有m個人，n項工作，每個人會做其中的若干項工作，能不能適當(dāng)安排，使得每個人都有工作做？,19,2 Hall定理,當(dāng) n m時，肯定是不

6、可能的，即使是n m 也不一定。但如果每個人能做的工作越多，越容易實現(xiàn)。,20,2 Hall定理1,Hall定理(1935)： 二分圖G存在一匹配M，使得X的所有頂點關(guān)于M飽和的充要條件是：對于X任一子集A，及與A鄰接的點集為N(A)，恒有：|N(A)|A|。,21,7-3 匈牙利算法及例,1965年，匈牙利著名數(shù)學(xué)家Edmonds設(shè)計了一種求最大匹配的算法，稱為匈牙利(Hungarian)算法。,22,3 匈牙利算法,匈牙利(Hungarian)算法： （1）任給一個初始匹配； （2）若X已經(jīng)飽和，結(jié)束；否則轉(zhuǎn)（3）； （3）在X中找一個非飽和點x0，V1=x0，V2=； （4）若N(V1)

7、=V2則停止，否則任選一點yN(V1)-V2； （5）若y已飽和， M中必有(y,z) ；作【 V1 =V1 z ， V2 =V2 y； 轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】,23,3 匈牙利算法例,用匈牙利算法求下圖的最大匹配：,例,24,3 匈牙利算法例解,（1）任給一個初始匹配； （2）若X已經(jīng)飽和，結(jié)束；否則轉(zhuǎn)（3）；,解,M=(x1,y1 ),(x3,y5),(x5,y3),25,3 匈牙利算法例解1,（3）在X中找一個非飽和點x0，V1=x0，V2= （4）若N(V1)=V2則停止，否則任選一點yN(V1)-V2,解,M=(x1,y1 ),(x

8、3,y5),(x5,y3),V1=x2,V2=,N(V1)=y2, y3,26,3 匈牙利算法例解2,（5）若y已飽和， M中必有(y,z) ；作【 V1 =V1 z ， V2 =V2 y； 轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】,解,M=(x1,y1 ),(x3,y5),(x5,y3),V1=V1x5=x2,x5；V2=V2 y3 =y3,V1=x2,V2=,27,3 匈牙利算法例解3,（4）若N(V1)=V2則停止，否則任選一點yN(V1)-V2；,解,M=(x1,y1 ),(x3,y5),(x5,y3),V1=x2,x5；V2=y3,N(V1)=y2,

9、 y3 , y5,28,3 匈牙利算法例解4,（5）若y已飽和， M中必有(y,z) ；作【 V1 =V1 z ， V2 =V2 y； 轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】,解,M=(x1,y1 ),(x3,y5),(x5,y3),V1=x2,x5；V2=y3；,V1=V1x3=x2,x5, x3；V2=V2 y5 =y3 ,y5,29,3 匈牙利算法例解5,（4）若N(V1)=V2則停止，否則任選一點yN(V1)-V2；,解,M=(x1,y1 ),(x3,y5),(x5,y3),V1=x2,x5, x3；V2 =y3 ,y5；,N(V1)=y2, y3

10、, y5,30,3 匈牙利算法例解6,（5）若y已飽和， M中必有(y,z) ；作【 V1 =V1 z ， V2 =V2 y； 轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】,解,M=(x1,y1 ),(x3,y5),(x5,y3),V1=x2,x5, x3；V2 =y3 ,y5；,31,3 匈牙利算法例解7,（2）若X已經(jīng)飽和，結(jié)束；否則轉(zhuǎn)（3）； （3）在X中找一個非飽和點x0，V1=x0，V2= （4）若N(V1)=V2則停止，否則任選一點yN(V1)-V2,解,V1=x4；V2 =,M=(x1,y1 ),(x2,y3),(x3,y2),( x5,y5),N(

11、V1)=y3,32,3 匈牙利算法例解8,（5）若y已飽和， M中必有(y,z) ；作【 V1 =V1 z ， V2 =V2 y； 轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】,解,V1=x4；V2 =,M=(x1,y1 ),(x2,y3),(x3,y2),( x5,y5),V1=V1x2=x4,x2；V2=V2y3 =y3,33,3 匈牙利算法例解9,（4）若N(V1)=V2則停止，否則任選一點yN(V1)-V2,解,M=(x1,y1 ),(x2,y3),(x3,y2),( x5,y5),V1=x4,x2,；V2 =y3 ,N(V1)=y2, y3,34,3 匈

12、牙利算法例解10,（5）若y已飽和， M中必有(y,z) ；作【 V1 =V1 z ， V2 =V2 y； 轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】,解,M=(x1,y1 ),(x2,y3),(x3,y2),( x5,y5),V1=x4,x2,；V2 =y3 ,V1=V1x3=x4,x2 ,x3；V2=V2y2 =y3,y2,35,3 匈牙利算法例解11,（4）若N(V1)=V2則停止，否則任選一點yN(V1)-V2,解,M=(x1,y1 ),(x2,y3),(x3,y2),( x5,y5),V1=x4,x2 ,x3；V2=y3,y2,N(V1)=y2, y3

13、 , y5,36,3 匈牙利算法例解12,（5）若y已飽和， M中必有(y,z) ；作【 V1 =V1 z ， V2 =V2 y； 轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】,解,M=(x1,y1 ),(x2,y3),(x3,y2),( x5,y5),V1=x4,x2 ,x3；V2=y3,y2,V1=V1x5=x4,x2 ,x3, x5；V2=V2y5 =y3,y2,y5,37,3 匈牙利算法例解13,（4）若N(V1)=V2則停止，否則任選一點yN(V1)-V2,解,M=(x1,y1 ),(x2,y3),(x3,y2),( x5,y5),V1=x4,x2 ,x

14、3, x5；V2 =y3,y2,y5,N(V1)=y2, y3 , y5 , y4,38,3 匈牙利算法例解14,（5）若y已飽和， M中必有(y,z) ；作【 V1 =V1 z ， V2 =V2 y； 轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】,解,M=(x1,y1 ),(x2,y3),(x3,y2),( x5,y5),V1=x4,x2 ,x3, x5；V2 =y3,y2,y5,39,3 匈牙利算法例解15,（2）若X已經(jīng)飽和，結(jié)束；否則轉(zhuǎn)（3）；,解,這時，M=(x1,y1 ),(x2,y2),(x3,y5),( x4,y3 ),(x5,y4) 就是所求的最

15、大匹配。,40,7-4 最佳匹配,公司里有n名工作人員，他們每個人都能承擔(dān)n項工作的其中若干項，因為每個人的特長不同，所以對每項工作創(chuàng)造的價值也有所不同。問如何安排，使得他們總的創(chuàng)造價值最大？,41,4 最佳匹配,x對每項工作創(chuàng)造的價值的如右邊的矩陣所表示：,42,7-5 最佳匹配算法及例,Kuhn和Munkras設(shè)計了求最佳匹配的有效算法，他們把求最佳匹配的問題轉(zhuǎn)化成可用匈牙利算法求另一個圖的完備匹配的問題。,43,5 最佳匹配算法1,為此，他們對加權(quán)的二分圖每個頂點v給一個頂標(biāo)l(v)，當(dāng)xiX，yjY，l(xi)+l(yj)cij時，稱這樣的頂標(biāo)為正常頂標(biāo)。,44,5 最佳匹配算法2,初

16、始的時候，令 l(xi)=max ci*； l(yi)=0；,45,最佳匹配定理,設(shè)二分圖Kn,n=G是具有正常頂標(biāo)l的加權(quán)圖，取G的邊子集El=eij|eijE(G),l(i)+l(j)=cij。令Gl是以El為邊集的生成子圖，如果有Gl完備匹配M，則M即為G的最佳匹配。,46,5 最佳匹配算法3,KM算法： （1）選定初始正常標(biāo)頂l，構(gòu)作圖Gl，在Gl中用匈牙利算法求一個最大匹配； （2）若X飽和則結(jié)束，此時所得匹配就是最佳匹配，否則在X中任選一個非飽和點x0，令V1=x0 ，V2=； （3）若NGl(V1)=V2，則取=min(l(xi)+l(yj)-cij)，其中xiV1，yjNG(V

17、1)- V2，使得 l(v)- vV1 l(v)= l(v)+ vV2 l(v) 其他重新構(gòu)作圖Gl，在NGl(V1)-V2任取一點y，轉(zhuǎn)向（4）； 否則在NGl(V1)-V2任取一點y，轉(zhuǎn)向（4）,47,5 最佳匹配算法4,（4）若y已飽和， M中必有(y,z) ；作【 V1 =V1 z ， V2 =V2 y； 轉(zhuǎn)（3）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】,48,5 最佳匹配算法例,求下圖的最佳匹配,例,49,5 最佳匹配算法例解1,（1）選定初始正常標(biāo)頂l，構(gòu)作圖Gl，在Gl中用匈牙利算法求一個最大匹配；,解,M=(x1,y2), (x2,y1), (x3,y

18、3), (x5,y5),50,5 最佳匹配算法例解2,（2）若X飽和則結(jié)束，此時所得匹配就是最佳匹配，否則在X中任選一個非飽和點x0，令V1=x0 ，V2=；,解,M=(x1,y2), (x2,y1), (x3,y3), (x5,y5),V1=x4,V2=,51,5 最佳匹配算法例解3,（3）若NGl(V1)=V2，則； 否則在NGl(V1)-V2任取一點y，轉(zhuǎn)向（4）,解,M=(x1,y2), (x2,y1), (x3,y3), (x5,y5),V1=x4,V2=,52,5 最佳匹配算法例解4,（4）若y已飽和， M中必有(y,z) ；作【 V1 =V1 z ， V2 =V2 y； 轉(zhuǎn)（3）

19、】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】,解,M=(x1,y2), (x2,y1), (x3,y3), (x5,y5),V1=x4,x3,V2=y3,53,5 最佳匹配算法例解5,（3）若NGl(V1)=V2，則； 否則在NGl(V1)-V2任取一點y，轉(zhuǎn)向（4）,解,M=(x1,y2), (x2,y1), (x3,y3), (x5,y5),V1=x4,x3,V2=y3,54,5 最佳匹配算法例解6,（4）若y已飽和， M中必有(y,z) ；作【 V1 =V1 z ， V2 =V2 y； 轉(zhuǎn)（3）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】,解,

20、M=(x1,y2), (x2,y1), (x3,y3), (x5,y5),V1=x4,x3,x1,V2=y3,y2,55,5 最佳匹配算法例解7,（3）若NGl(V1)=V2，取=min(l(xi)+l(yj)-cij)，其中xiV1，yjNG(V1)- V2,解,M=(x1,y2), (x2,y1), (x3,y3), (x5,y5),V1=x4,x3,x1,V2=y3,y2,=1,NG(V1)=y1,y2,y3,y4,y5,56,5 最佳匹配算法例解8,l(v)- vV1 l(v)= l(v)+ vV2 l(v) 其他,解,M=(x1,y2), (x2,y1), (x3,y3), (x5,

21、y5),V1=x4,x3,x1,V2=y3,y2,=1,57,5 最佳匹配算法例解9,重新構(gòu)作圖Gl，在NGl(V1)-V2任取一點y，轉(zhuǎn)向（4）,解,M=(x1,y2), (x2,y1), (x3,y3), (x5,y5),V1=x4,x3,x1,V2=y3,y2,l(xi)+l(yj)cij,58,5 最佳匹配算法例解10,（4）若y已飽和， M中必有(y,z) ；作【 V1 =V1 z ， V2 =V2 y； 轉(zhuǎn)（3）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】,解,V1=x4,x3,x1,V2=y3,y2,M=(x1,y2), (x2,y1), (x3,y3),

22、(x5,y5),M=(x1,y4), (x2,y1), (x3,y3), (x4,y4), (x5,y5),59,5 最佳匹配算法例解11,（2）若X飽和則結(jié)束，此時所得匹配就是最佳匹配，否則在X中任選一個非飽和點x0，令V1=x0 ，V2=；,解,M=(x1,y4), (x2,y1), (x3,y3), (x4,y4), (x5,y5),W=4+2+4+1+3=14,60,課堂練習(xí),1、用匈牙利算法求下圖的最大匹配。,61,課堂練習(xí),2、若二分圖K5,5的權(quán)值矩陣如下，求其最佳匹配。,62,7-6 色數(shù)問題,平面圖的著色問題 邊的著色問題 頂點的著色問題,63,一、平面圖的著色問題,一個平面

23、圖的任意二個區(qū)域若有一條公共邊，則稱這二個區(qū)域是相鄰的。 一個平面圖的著色問題是對平面圖的區(qū)域著上顏色，至少要用幾種不同顏色才能使得任何相鄰兩個區(qū)域有不同的顏色。,64,一、平面圖的著色問題,65,四色定理,在1852年，一個英國青年名叫蓋思里（Francis Guthrie）提出：任何連通的平面圖，可以用不多于4種顏色對每一個區(qū)域著色，使相鄰區(qū)域著不同顏色。 18781880年兩年間，數(shù)學(xué)家肯普和泰勒兩人分別宣布證明了四色定理。后來，人們發(fā)現(xiàn)他們實際上證明了一個較弱的命題五色定理。就是說對平面圖著色，用五種顏色就夠了。 1976年美國伊利諾州立大學(xué)的兩位教授，阿佩爾（Kenneth Appe

24、l）和?？希╓olfgang Haken）宣布，用計算機證明了這個問題。他們的證明需要對1900多種情況進行詳盡的分析，在一臺高速計算機上耗時超過1200小時。對數(shù)學(xué)家來說總還是希望能找到數(shù)學(xué)方法的證明。,66,黎鳴：三元邏輯就可以破解四色定理,新京報記者 李健亞 近期，“哲學(xué)烏鴉”黎鳴宣稱自己已經(jīng)破解了四色猜想?！暗郎?，一生二，二生三，三生萬物。中國的傳統(tǒng)智慧啟發(fā)了我，我就用三生萬物作為我理論的基點，”黎鳴指出，自己破解的方法完全不同于一般數(shù)學(xué)家破解的方法。 黎鳴更是指出，由于中國地圖中各省分布并不復(fù)雜，所以在填色時，只需要3種顏色就能完成。 黎鳴還相信，自己的定理對其他的一些有關(guān)的數(shù)學(xué)難

25、題，例如哥德巴赫猜想等等的破解或許也可能會有所幫助，當(dāng)然，也難說一定，畢竟把二元邏輯提高到三元邏輯，的確是大大進了一步。又例如前段時間吸引眼球的龐加萊猜想，在黎鳴看來，也可能運用他的破解四色定理的方法，即使不去求解也顯然會有這樣直觀的結(jié)果，“任意一個曲面縮成最小，肯定只能是個球，用我的原理來解釋，這的確是顯然的?！?從理論物理再到控制系統(tǒng)理論專業(yè)，黎鳴從中國科技大學(xué)研究生院畢業(yè)出來之后，更多的卻是研究哲學(xué)。黎鳴的三元邏輯有三個坐標(biāo)系，太極、陰陽、三行。,67,哲學(xué)狂人賭命方舟子,黎鳴 南昌人，1950年12月出生，自稱“思想狂徒”、“哲學(xué)烏鴉”。1961年畢業(yè)于江西大學(xué)物理系，后進入中國科技大

26、學(xué)研究生院控制論與系統(tǒng)工程專業(yè)。長期進行哲學(xué)方面的研究。 方舟子本名方是民，1967年生于福建。1985年考入中國科技大學(xué)生物系。1995年獲美國密歇根州立大學(xué)生物化學(xué)博士學(xué)位。2000年創(chuàng)辦中文網(wǎng)上第一個學(xué)術(shù)打假網(wǎng)站“立此存照”。 2006年4月20日，哲學(xué)狂人黎鳴在其博客上發(fā)表了一篇文章，題為感謝老子，我發(fā)現(xiàn)了“四色”難題終獲簡潔而絕妙的證明！。 8月9日，哲學(xué)狂人黎鳴在自己的博客方舟子先生，還是讓我們來對決吧！一文中，向“偽科學(xué)斗士”方舟子提出以命相搏的生死對決協(xié)議。 “如果破解四色定理失敗，黎鳴先生愿按照協(xié)議，文明地進行自殺；如果破解四色定理成功，方舟子先生愿按照協(xié)議，文明地進行自殺。

27、” 對此挑戰(zhàn)，方舟子表示“沒必要理他，這是他自我炒作，一場鬧劇而已！”,68,69,70,二、頂點的著色問題,平面圖的色數(shù)不大于5。 平面圖的著色問題可以轉(zhuǎn)化頂點著色問題。,71,二、邊的著色問題,定義：給圖G的邊著色，使得有共同頂點的邊異色的最少顏色數(shù)，稱為邊色數(shù)。,邊色數(shù)=3,72,一、邊的著色問題,課程考試安排： 用頂點v1,v2,vn表示n門課程，若其中兩門課i,j被同時選，則vi,vj間連一條邊。,73,一、邊的著色問題,妖怪圖（snark graph） 妖怪圖每個點都關(guān)聯(lián)著3條邊，用4種顏色可以把每條邊涂上顏色，使得有公共端點的邊異色，而用3種顏色辦不到，切斷任意3條邊不會使它斷裂

28、成2個有邊的圖。,74,一、邊的著色問題1,單星妖怪和雙星妖怪：,75,一、邊的著色問題3,定理：二分圖G的邊色數(shù)圖中頂點的最大度。,76,一、邊的著色問題3,定理(Vizing 1964)：若圖G為簡單圖，圖中頂點最大度為d，則G的邊色數(shù)為d或d+1。,第一類圖,第二類圖,目前仍無區(qū)分 (判別)任給定圖屬 第幾類圖的有效方法。,77,一、邊的著色問題4,邊的著色問題可以轉(zhuǎn)化為頂點的著色問題。,78,三、頂點的著色問題,定義：給圖G的頂點著色，使得相鄰的頂點異色的最少顏色數(shù)，稱為圖G頂色數(shù)，簡稱色數(shù)；記作(G)。,(G)=2,79,二、頂點的著色問題,物資存儲問題： 設(shè)有n種物資要存放在倉庫里

29、，但有的物資不能放在同一房間里，否則引起損壞，甚至?xí)l(fā)生危險。問存放這n種物資最少需要幾個房間？,80,二、頂點的著色問題1,色數(shù)的性質(zhì)： （1）圖G只有孤立點時，(G)=1； （2）n個頂點的完全圖G有(G)=n；,81,二、頂點的著色問題1,（3）若圖G是n個頂點的回路，則 (G)=2 n為偶數(shù) =3 n為奇數(shù)；,82,二、頂點的著色問題1,（4）圖G是頂點數(shù)超過1的樹時，(G)=2；,83,二、頂點的著色問題1,（5）若圖G是二分圖，則(G)=2。,84,二、頂點的著色問題2,定理：圖G=(V,E)的色數(shù)(G)=2的充要條件是：(1)|E|1；(2)G不存在邊數(shù)為奇數(shù)的回路。,85,二、

30、頂點的著色問題2,定理：若圖G=(V,E)，d=maxd(vi),viV，則(G)d+1。,86,四、頂點著色的算法,（一）下面給出頂點著色的算法(假定G的頂點為v1,v2,vn;用來染色的顏色為c1,c2,cn)： （1）對i=1,2,n,作Ci=c1,c2,ci； （2）標(biāo)頂點vi (i=1,2,n)的顏色集Ci的第一種顏色ck； （3）對頂點vi的所有鄰接點vj(ji)，作Cj= Cj-ck； （4）轉(zhuǎn)到（2），直到所有頂點都著色為止。,87,三、頂點著色的算法例,對下圖頂點進行著色。,例,88,三、頂點著色的算法例解,（1）對i=1,2,n,作Ci=c1,c2,ci；,解,C1=c1

31、C2=c1,c2 C3=c1,c2,c3 C4=c1,c2,c3,c4 C5=c1,c2,c3,c4,c5 C6=c1,c2,c3,c4,c5,c6 C7=c1,c2,c3,c4,c5,c6,c7,89,三、頂點著色的算法例解1,（2）標(biāo)頂點vi (i=1,2,n)的顏色集Ci的第一種顏色ck；,解,C1=c1 C2=c1,c2 C3=c1,c2,c3 C4=c1,c2,c3,c4 C5=c1,c2,c3,c4,c5 C6=c1,c2,c3,c4,c5,c6 C7=c1,c2,c3,c4,c5,c6,c7,c1,90,三、頂點著色的算法例解2,（3）對頂點vi的所有鄰接點vj(ji)，作Cj=

32、 Cj-ck；,解,c1,C1=c1 C2=c1,c2 C3=c1,c2,c3 C4=c1,c2,c3,c4 C5=c1,c2,c3,c4,c5 C6=c1,c2,c3,c4,c5,c6 C7=c1,c2,c3,c4,c5,c6,c7,C2=c2,C3=c2, c3,C7=c2,c3,c4,c5,c6,c7,C5=c2,c3,c4,c5,C6=c2,c3,c4,c5,c6,91,三、頂點著色的算法例解3,（4）轉(zhuǎn)到（2），直到所有頂點都著色為止 （2）標(biāo)頂點vi (i=1,2,n)的顏色集Ci的第一種顏色ck,解,c1,C1=c1 C2=c2 C3=c2,c3 C4=c1,c2,c3,c4 C

33、5=c2,c3,c4,c5 C6=c2,c3,c4,c5,c6 C7=c2,c3,c4,c5,c6,c7,c2,92,三、頂點著色的算法例解4,（3）對頂點vi的所有鄰接點vj(ji)，作Cj= Cj-ck；,解,c1,C1=c1 C2=c2 C3=c2,c3 C4=c1,c2,c3,c4 C5=c2,c3,c4,c5 C6=c2,c3,c4,c5,c6 C7=c2,c3,c4,c5,c6,c7,c2,C3=c3,93,三、頂點著色的算法例解5,解,c1,C1=c1 C2=c2 C3=c3 C4=c1,c2,c3,c4 C5=c2,c3,c4,c5 C6=c2,c3,c4,c5,c6 C7=c

34、2,c3,c4,c5,c6,c7,c2,（4）轉(zhuǎn)到（2），直到所有頂點都著色為止 （2）標(biāo)頂點vi (i=1,2,n)的顏色集Ci的第一種顏色ck,c3,94,三、頂點著色的算法例解6,解,c1,C1=c1 C2=c2 C3=c3 C4=c1,c2,c3,c4 C5=c2,c3,c4,c5 C6=c2,c3,c4,c5,c6 C7=c2,c3,c4,c5,c6,c7,c2,（3）對頂點vi的所有鄰接點vj(ji)，作Cj= Cj-ck；,c3,C5=c2,c4,c5,C4=c1,c2,c4,95,三、頂點著色的算法例解7,解,c1,C1=c1 C2=c2 C3=c3 C4=c1,c2,c4 C

35、5=c2,c4,c5 C6=c2,c3,c4,c5,c6 C7=c2,c3,c4,c5,c6,c7,c2,（4）轉(zhuǎn)到（2），直到所有頂點都著色為止 （2）標(biāo)頂點vi (i=1,2,n)的顏色集Ci的第一種顏色ck,c3,c1,96,三、頂點著色的算法例解8,解,c1,C1=c1 C2=c2 C3=c3 C4=c1,c2,c4 C5=c2,c4,c5 C6=c2,c3,c4,c5,c6 C7=c2,c3,c4,c5,c6,c7,c2,（3）對頂點vi的所有鄰接點vj(ji)，作Cj= Cj-ck；,c3,c1,97,三、頂點著色的算法例解9,解,c1,C1=c1 C2=c2 C3=c3 C4=c

36、1,c2,c4 C5=c2,c4,c5 C6=c2,c3,c4,c5,c6 C7=c2,c3,c4,c5,c6,c7,c2,（4）轉(zhuǎn)到（2），直到所有頂點都著色為止 （2）標(biāo)頂點vi (i=1,2,n)的顏色集Ci的第一種顏色ck,c3,c1,c2,98,三、頂點著色的算法例解10,解,c1,C1=c1 C2=c2 C3=c3 C4=c1,c2,c4 C5=c2,c4,c5 C6=c2,c3,c4,c5,c6 C7=c2,c3,c4,c5,c6,c7,c2,（3）對頂點vi的所有鄰接點vj(ji)，作Cj= Cj-ck；,c3,c1,c2,C6=c3,c4,c5,c6,99,三、頂點著色的算法

37、例解11,解,c1,C1=c1 C2=c2 C3=c3 C4=c1,c2,c4 C5=c2,c4,c5 C6=c3,c4,c5,c6 C7=c2,c3,c4,c5,c6,c7,c2,（4）轉(zhuǎn)到（2），直到所有頂點都著色為止 （2）標(biāo)頂點vi (i=1,2,n)的顏色集Ci的第一種顏色ck,c3,c1,c2,c3,100,三、頂點著色的算法例解12,解,c1,C1=c1 C2=c2 C3=c3 C4=c1,c2,c4 C5=c2,c4,c5 C6=c3,c4,c5,c6 C7=c2,c3,c4,c5,c6,c7,c2,（3）對頂點vi的所有鄰接點vj(ji)，作Cj= Cj-ck；,c3,c1,

38、c2,C7=c2,c4,c5,c6,c7,c3,101,三、頂點著色的算法例解13,解,c1,C1=c1 C2=c2 C3=c3 C4=c1,c2,c4 C5=c2,c4,c5 C6=c3,c4,c5,c6 C7=c2,c4,c5,c6,c7,c2,（4）轉(zhuǎn)到（2），直到所有頂點都著色為止 （2）標(biāo)頂點vi (i=1,2,n)的顏色集Ci的第一種顏色ck,c3,c1,c2,c3,c2,102,三、頂點著色的算法,注：上述算法并不能保證求出的著色方案用的顏色是最少的。,103,（二）韋爾奇鮑威爾(WelchPowell)著色算法,步驟如下： （1）將圖G中的頂點按度數(shù)遞減次序排列； （2）用第一

39、種顏色對第一頂點著色，并將與已著色頂點不鄰接的頂點也著第一種顏色； （3）按排列次序用第二種顏色對未著色的頂點重復(fù)（2）；用第三種顏色繼續(xù)以上做法，直到所有的頂點均著上色為止。,104,韋爾奇鮑威爾法例,用韋爾奇鮑威爾法對圖的頂點著色。,例,105,韋爾奇鮑威爾法例,（1）各頂點按度數(shù)遞減次序排列： c，a，e，f，b，h，g，d。 （2）對c和與c不鄰接的e，b著第一種顏色。,解,106,韋爾奇鮑威爾法例,（1）各頂點按度數(shù)遞減次序排列： c，a，e，f，b，h，g，d。 （2）對c和與c不鄰接的e，b著第一種顏色。 （3）對a和與a不鄰接的g，d著第二種顏色。,解,107,韋爾奇鮑威爾法例,（1）各頂點按度數(shù)遞減次序排列： c，a，e，f，b，h，g，d； （2）對c和與c不鄰接的e，b著第一種顏