第七章、匹配、色數(shù)問題及其它

第七章匹配理論和色數(shù)問題§1最大匹配§2Hall定理§3匈牙利算法及例§4最佳匹配§5最佳匹配算法及例§6色數(shù)問題應(yīng)用篇1§1最大匹配匹配是圖論中一個重要內(nèi)容，它在所謂“人員分配問題”和“最優(yōu)分配問題”有重要應(yīng)用。2§1最大匹配－1具體問題描述：有n個女士和n個男士參加舞會，每位女士與其中若干位男士相識，每位男士與其中若干位女士相識，問如何安排，使得盡量多配對的男女舞伴相識。f1f2m1f3f4f5m2m3m4m53§1最大匹配－1下圖就是一種分配方法：f1f2m1f3f4f5m2m3m4m5(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)4§1最大匹配－定義定義：若圖G=(V,E)的頂點可以分成X，Y兩個子集，每個子集里的頂點互不相鄰，這樣的圖稱為二分圖。f1f2m1f3f4f5m2m3m4m55§1最大匹配－定義1定義：若M是圖G=(V,E)的邊子集，且M中的任意兩條邊在G中不相鄰，則稱M為G中的一個匹配，M中的每條邊的兩個端點稱為在M中是配對的。f1f2m1f3f4f5m2m3m4m5M={(f1,m2),(f2,m1),(f3,m4),(f4,m5)}6§1最大匹配－定義2定義：若圖G中每個頂點均被M許配時，稱M為G中的一個完備匹配。f1f2m1f3f4f5m2m3m4m5M={(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)}7§1最大匹配－定義3定義：圖G中邊數(shù)最多的匹配M，稱為G中的一個最大匹配。M={(f1,m3),(f2,m1),(f3,m2),(f5,m5)}f1f2m1f3f4f5m2m3m4m58§1最大匹配－定義4定義：若匹配M的某邊和頂點v關(guān)聯(lián)，稱v是M-飽和的，否則就是M-不飽和的。M={(f1,m3),(f2,m1),(f3,m2),(f5,m5)}f1f2m1f3f4f5m2m3m4m5飽和的不飽和的9§1最大匹配－定義5定義：若M是圖G的一個匹配，若從G中一個頂點到另一個頂點存在一條道路，此路徑由屬于M和不屬于M的邊交替出現(xiàn)組成的，則稱此路徑為交互道。f1f2m1f3f4f5m2m3m4m5M={(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)}P=f1m3f4m5f2m1f5m410§1最大匹配－定義6定義：若交互道的兩個端點為關(guān)于M的不飽和頂點時，稱此交互道為可增廣道路。M={(f2,m5),(f3,m2),(f4,m3),(f5,m4)}P=m1f2m5f4m3f1是一條可增廣道路。f1f2m1f3f4f5m2m3m4m5f1f2m1f3f4f5m2m3m4m511§1最大匹配－定義8f1f2m1f3f4f5m2m3m4m5M={(f2,m5),(f3,m2),(f4,m3),(f5,m4)}P=m1f2m5f4m3f1是一條可增廣道路。f1f2m1f3f4f5m2m3m4m5M={(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)}12§1最大匹配－1具體問題描述：有n個女士和n個男士參加舞會，每位女士與其中若干位男士相識，每位男士與其中若干位女士相識，問如何安排，使得盡量多配對的男女舞伴相識。f1f2m1f3f4f5m2m3m4m513§1最大匹配－Berge定理定理7.1(Berge1957)：M為最大匹配的充要條件是：圖G中不存在可增廣道路。M={(f1,m3),(f2,m1),(f3,m2),(f5,m5)}f1f2m1f3f4f5m2m3m4m514§1最大匹配－定義7對稱差：A、B是兩個集合，AB=(A∪B)-(A∩B)?AB15§2Hall定理設(shè)有m個人，n項工作，每個人會做其中的若干項工作，能不能適當(dāng)安排，使得每個人都有工作做？w1w2m1w3w4w5m2m3m416§2Hall定理當(dāng)m>n時，肯定是不可能的，即使是m≤n也不一定。但如果每個人能做的工作越多，越容易實現(xiàn)。w1w2m1w3w4w5m2m3m417§2Hall定理－1Hall定理(1935)：二分圖G存在一匹配M，使得X的所有頂點關(guān)于M飽和的充要條件是：對于X任一子集A，及與A鄰接的點集為N(A)，恒有：|N(A)|≥|A|。w1w2m1w3w4w5m2m3m4YX18§3匈牙利算法及例1965年，匈牙利著名數(shù)學(xué)家Edmonds設(shè)計了一種求最大匹配的算法，稱為匈牙利(Hungarian)算法。19§3匈牙利算法

匈牙利(Hungarian)算法：（1）任給一個初始匹配；（2）若X已經(jīng)飽和，結(jié)束；否則轉(zhuǎn)（3）；（3）在X中找一個非飽和點x0，V1={x0}，V2={}；（4）若N(V1)=V2則停止，否則任選一點y∈N(V1)-V2；（5）若y已飽和，M中必有(y,z)；作【V1=V1

∪{z}，V2=V2∪

{y}；轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】20§3匈牙利算法例用匈牙利算法求下圖的最大匹配：例x1x2y1x3x4x5y2y3y4y521§3匈牙利算法例解（1）任給一個初始匹配；（2）若X已經(jīng)飽和，結(jié)束；否則轉(zhuǎn)（3）；解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}22§3匈牙利算法例解1（3）在X中找一個非飽和點x0，V1={x0}，V2={}（4）若N(V1)=V2則停止，否則任選一點y∈N(V1)-V2解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}V1={x2},V2={}N(V1)={y2,

y3}23§3匈牙利算法例解2（5）若y已飽和，M中必有(y,z)；作【V1=V1

∪{z}，V2=V2∪

{y}；轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}V1=V1∪{x5}={x2,x5}；V2=V2∪

{y3}

={y3}V1={x2},V2={}24§3匈牙利算法例解3（4）若N(V1)=V2則停止，否則任選一點y∈N(V1)-V2；解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}V1={x2,x5}；V2={y3}N(V1)={y2,y3,y4,y5}25§3匈牙利算法例解4（5）若y已飽和，M中必有(y,z)；作【V1=V1

∪{z}，V2=V2∪

{y}；轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}V1={x2,x5}；V2={y3}；V1=V1∪{x3}={x2,x5,x3}；V2=V2∪

{y5}

={y3,y5}26§3匈牙利算法例解5（4）若N(V1)=V2則停止，否則任選一點y∈N(V1)-V2；解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}V1={x2,x5,

x3}；V2={y3,y5}；N(V1)={y2,y3,y4,y5}27§3匈牙利算法例解6（5）若y已飽和，M中必有(y,z)；作【V1=V1

∪{z}，V2=V2∪

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

∪{z}，V2=V2∪

{y}；轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】解x1x2y1x3x4x5y2y3y4y5V1={x4}；V2={}M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1=V1∪{x2}={x4,x2}；V2=V2∪{y3}

={y3}30§3匈牙利算法例解9（4）若N(V1)=V2則停止，否則任選一點y∈N(V1)-V2解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1={x4,x2,}；V2={y3}N(V1)={y2,y3}31§3匈牙利算法例解10（5）若y已飽和，M中必有(y,z)；作【V1=V1

∪{z}，V2=V2∪

{y}；轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1={x4,x2,}；V2={y3}V1=V1∪{x3}={x4,x2,x3}；V2=V2∪{y2}

={y3,y2}32§3匈牙利算法例解11（4）若N(V1)=V2則停止，否則任選一點y∈N(V1)-V2解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1={x4,x2,x3}；V2={y3,y2}N(V1)={y2,y3,y5}33§3匈牙利算法例解12（5）若y已飽和，M中必有(y,z)；作【V1=V1

∪{z}，V2=V2∪

{y}；轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1={x4,x2,x3}；V2={y3,y2}V1=V1∪{x5}={x4,x2,x3,x5}；V2=V2∪{y5}

={y3,y2,y5}34§3匈牙利算法例解13（4）若N(V1)=V2則停止，否則任選一點y∈N(V1)-V2解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1={x4,x2,x3,x5}；V2={y3,y2,y5}N(V1)={y2,y3,y5,y4}35§3匈牙利算法例解14（5）若y已飽和，M中必有(y,z)；作【V1=V1

∪{z}，V2=V2∪

{y}；轉(zhuǎn)（4）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1={x4,x2,x3,

x5}；V2={y3,y2,y5}x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5M=ME(P)={(x1,y1),(x2,y2),(x3,y5),(x4,y3),(x5,y4)}?36§3匈牙利算法例解15（2）若X已經(jīng)飽和，結(jié)束；否則轉(zhuǎn)（3）；解x1x2y1x3x4x5y2y3y4y5這時，M={(x1,y1),(x2,y2),(x3,y5),(x4,y3),(x5,y4)}就是所求的最大匹配。37§4最佳匹配公司里有n名工作人員，他們每個人都能承擔(dān)n項工作的其中若干項，因為每個人的特長不同，所以對每項工作創(chuàng)造的價值也有所不同。問如何安排，使得他們總的創(chuàng)造價值最大？38§4最佳匹配x對每項工作創(chuàng)造的價值的如右邊的矩陣所表示：x1x2y1x3x4x5y2y3y4y53554122022244100110012133

C=x1x2x3x4x5y1y2y3y4y539§5最佳匹配算法及例Kuhn和Munkras設(shè)計了求最佳匹配的有效算法，他們把求最佳匹配的問題轉(zhuǎn)化成可用匈牙利算法求另一個圖的完備匹配的問題。40§5最佳匹配算法1為此，他們對加權(quán)的二分圖每個頂點v給一個頂標(biāo)l(v)，當(dāng)xi∈X，yj∈Y，l(xi)+l(yj)≥cij時，稱這樣的頂標(biāo)為正常頂標(biāo)。41§5最佳匹配算法2初始的時候，令l(xi)=maxci*；l(yi)=0；x1x2y1x3x4x5y2y3y4y53554122022244100110012133

C=x1x2x3x4x5y1y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=042最佳匹配定理設(shè)二分圖Kn,n=G是具有正常頂標(biāo)l的加權(quán)圖，取G的邊子集El={eij|eij∈E(G),l(i)+l(j)=cij}。令Gl是以El為邊集的生成子圖，如果有Gl完備匹配M，則M即為G的最佳匹配。x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y543§5最佳匹配算法3KM算法：（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)，其中xi∈V1，yj∈NG(V1)-V2，使得

l(v)-αv∈V1

l(v)=l(v)+αv∈V2

l(v)其他

重新構(gòu)作圖Gl，在NGl(V1)-V2任取一點y，轉(zhuǎn)向（4）；否則在NGl(V1)-V2任取一點y，轉(zhuǎn)向（4）44§5最佳匹配算法4（4）若y已飽和，M中必有(y,z)；作【V1=V1

∪{z}，V2=V2∪

{y}；轉(zhuǎn)（3）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】45§5最佳匹配算法例求下圖的最佳匹配例x1x2y1x3x4x5y2y3y4y53554122022244100110012133

C=x1x2x3x4x5y1y2y3y4y546§5最佳匹配算法例解1（1）選定初始正常標(biāo)頂l，構(gòu)作圖Gl，在Gl中用匈牙利算法求一個最大匹配；解x1x2y1x3x4x5y2y3y4y53554122022244100110012133

C=x1x2x3x4x5y1y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0M={(x1,y2),(x2,y1),(x3,y3),

(x5,y5)}x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y547§5最佳匹配算法例解2（2）若X飽和則結(jié)束，此時所得匹配就是最佳匹配，否則在X中任選一個非飽和點x0，令V1={x0}，V2={}；解x1x2y1x3x4x5y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0M={(x1,y2),(x2,y1),(x3,y3),

(x5,y5)}V1={x4},V2={}48§5最佳匹配算法例解3（3）若NGl(V1)=V2，則……；否則在NGl(V1)-V2任取一點y，轉(zhuǎn)向（4）解x1x2y1x3x4x5y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0M={(x1,y2),(x2,y1),(x3,y3),

(x5,y5)}V1={x4},V2={}49§5最佳匹配算法例解4（4）若y已飽和，M中必有(y,z)；作【V1=V1

∪{z}，V2=V2∪

{y}；轉(zhuǎn)（3）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】解x1x2y1x3x4x5y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0M={(x1,y2),(x2,y1),(x3,y3),

(x5,y5)}V1={x4,x3},V2={y3}50§5最佳匹配算法例解5（3）若NGl(V1)=V2，則……；否則在NGl(V1)-V2任取一點y，轉(zhuǎn)向（4）解x1x2y1x3x4x5y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0M={(x1,y2),(x2,y1),(x3,y3),

(x5,y5)}V1={x4,x3},V2={y3}51§5最佳匹配算法例解6（4）若y已飽和，M中必有(y,z)；作【V1=V1

∪{z}，V2=V2∪

{y}；轉(zhuǎn)（3）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】解x1x2y1x3x4x5y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0M={(x1,y2),(x2,y1),(x3,y3),

(x5,y5)}V1={x4,x3,x1},V2={y3,y2}52§5最佳匹配算法例解7（3）若NGl(V1)=V2，取α=min(l(xi)+l(yj)-cij)，其中xi∈V1，yj∈NG(V1)-V2解x1x2y1x3x4x5y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0M={(x1,y2),(x2,y1),(x3,y3),

(x5,y5)}V1={x4,x3,x1},V2={y3,y2},3554122022244100110012133

C=x1x2x3x4x5y1y2y3y4y5α=1NG(V1)={y1,y2,y3,y4,y5}53§5最佳匹配算法例解8

l(v)-αv∈V1

l(v)=l(v)+αv∈V2

l(v)其他解x1x2y1x3x4x5y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0M={(x1,y2),(x2,y1),(x3,y3),

(x5,y5)}V1={x4,x3,x1},V2={y3,y2}α=1l(x1)=4l(x3)=3l(x4)=0l(y2)=1l(y3)=154§5最佳匹配算法例解9重新構(gòu)作圖Gl，在NGl(V1)-V2任取一點y，轉(zhuǎn)向（4）解x1x2y1x3x4x5y2y3y4y5l(x1)=4l(x2)=2l(x3)=3l(x4)=0l(x5)=3l(y5)=0l(y1)=0l(y2)=1l(y3)=1l(y4)=0M={(x1,y2),(x2,y1),(x3,y3),

(x5,y5)}V1={x4,x3,x1},V2={y3,y2}3554122022244100110012133

C=x1x2x3x4x5y1y2y3y4y5x1x2y1x3x4x5y2y3y4y5l(xi)+l(yj)＝cij55§5最佳匹配算法例解10（4）若y已飽和，M中必有(y,z)；作【V1=V1

∪{z}，V2=V2∪

{y}；轉(zhuǎn)（3）】，否則【求一條從x0到y(tǒng)的可增廣道路P，對之進行增廣；轉(zhuǎn)（2）】x1x2y1x3x4x5y2y3y4y5解V1={x4,x3,x1},V2={y3,y2}l(x1)=4l(x2)=2l(x3)=3l(x4)=0l(x5)=3l(y5)=0l(y1)=0l(y2)=1l(y3)=1l(y4)=0x1x2y1x3x4x5y2y3y4y5M={(x1,y2),(x2,y1),(x3,y3),

(x5,y5)}M={(x1,y4),(x2,y1),(x3,y3),

(x4,y4),

(x5,y5),}56§5最佳匹配算法例解11（2）若X飽和則結(jié)束，此時所得匹配就是最佳匹配，否則在X中任選一個非飽和點x0，令V1={x0}，V2={}；x1x2y1x3x4x5y2y3y4y5解M={(x1,y4),(x2,y1),(x3,y3),

(x4,y4),

(x5,y5),}l(x1)=4l(x2)=2l(x3)=3l(x4)=0l(x5)=3l(y5)=0l(y1)=0l(y2)=1l(y3)=1l(y4)=0W=4+2+4+1+3=1457課堂練習(xí)1、用匈牙利算法求下圖的最大匹配。x1x2y1x3x4x5y2y3y4y558課堂練習(xí)2、若二分圖K5,5的權(quán)值矩陣如下，求其最佳匹配。0554033033144301220113144C=x1x2x3x4x5y1y2y3y4y559§6色數(shù)問題邊的著色問題頂點的著色問題60一、邊的著色問題定義：給圖G的邊著色，使得有共同頂點的邊異色的最少顏色數(shù)，稱為邊色數(shù)。邊色數(shù)=3邊色數(shù)=561一、邊的著色問題妖怪圖（snarkgraph）妖怪圖每個點都關(guān)聯(lián)著3條邊，用4種顏色可以把每條邊涂上顏色，使得有公共端點的邊異色，而用3種顏色辦不到，切斷任意3條邊不會使它斷裂成2個有邊的圖。62一、邊的著色問題1單星妖怪和雙星妖怪：單星妖怪雙星妖怪63一、邊的著色問題時間表問題；設(shè)x1,x2,…,xm為m個工作人員，y1,y2,…,yn表為n種設(shè)備，工作人員對設(shè)備提出要求，使用時間均假定以單位時間計算，自然每一個工作人員在同一個時間只能使用一種設(shè)備，某一種設(shè)備在同一時間里只能為一個工作人員使用，問應(yīng)如何合理安排，使得盡可能短時間里滿足工作人員的要求？問題轉(zhuǎn)換為X={x1,x2,…,xm}，Y={y1,y2,…,yn}的二分圖G，工作人員xi要求使用設(shè)備yj，每單位時間對應(yīng)一條從xi到y(tǒng)j的邊，這樣所得的二分圖過xi，yj的邊可能不止一條。問題變?yōu)閷λ枚謭DG的邊著色問題。有相同顏色的邊可以安排在同一時間里。64一、邊的著色問題3定理：二分圖G的邊色數(shù)＝圖中頂點的最大度。x1x2y1x3x4x5y2y3y4y565一、邊的著色問題3定理(Vizing1964)：若圖G為簡單圖，圖中頂點最大度為d，則G的邊色數(shù)為d或d+1。x1x2y1x3x4x5y2y3y4y5單星妖怪第一類圖第二類圖目前仍無有效區(qū)分(判別)任給定圖屬第幾類圖的有效方法。66一、邊的著色問題4邊的著色問題可以轉(zhuǎn)化為頂點的著色問題。67二、頂點的著色問題定義：給圖G的頂點著色，使得相鄰的頂點異色的最少顏色數(shù)，稱為圖G頂色數(shù)，簡稱色數(shù)；記作χ(G)。χ(G)=268二、頂點的著色問題四色猜想：平面圖的色數(shù)不大于5。69一、邊的著色問題課程考試安排；用頂點v1,v2,…,vn表示n門課程，若其中兩門課i,j被同時選，則vi,vj間連一條邊。考試安排問題相當(dāng)于圖的頂點染色問題，著同一顏色的頂點對應(yīng)的課程可以同時進行考試，使圖的相鄰頂點有不同顏色的最少顏色數(shù)目，便是進行考試的最少場次。物資存儲問題；70二、頂點的著色問題1色數(shù)的性質(zhì)：（1）圖G只有孤立點時，χ(G)=1；（2）n個頂點的完全圖G有χ(G)=n；71二、頂點的著色問題1（3）若圖G是n個頂點的回路，則

χ(G)=2n為偶數(shù)

=3n為奇數(shù)；72二、頂點的著色問題1（4）圖G是頂點數(shù)超過1的樹時，χ(G)=2；73二、頂點的著色問題1（5）若圖G是二分圖，則χ(G)=2。x1x2y1x3x4x5y2y3y4y574二、頂點的著色問題2定理：圖G=(V,E)的色數(shù)χ(G)=2的充要條件是：(1)|E|≥1；(2)G不存在邊數(shù)為奇數(shù)的回路。75二、頂點的著色問題2定理：若圖G=(V,E)，d=max{d(vi)},vi∈V，則χ(G)≤d+1。76三、頂點著色的算法下面給出頂點著色的算法(假定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(j>i)，作Cj=Cj-{ck}；（4）轉(zhuǎn)到（2），直到所有頂點都著色為止。77三、頂點著色的算法例對下圖頂點進行著色。例v1v2v3v4v5v7v678三、頂點著色的算法例解（1）對i=1,2,…,n,作Ci={c1,c2,…,ci}；解v1v2v3v4v5v7v6C1={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}79三、頂點著色的算法例解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}v1v2v3v4v5v7v6c180三、頂點著色的算法例解2（3）對頂點vi的所有鄰接點vj(j>i)，作Cj=Cj-{ck}；解v1v2v3v4v5v7v6c1C1={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}81三、頂點著色的算法例解3（4）轉(zhuǎn)到（2），直到所有頂點都著色為止（2）標(biāo)頂點vi(i=1,2,…,n)的顏色集Ci的第一種顏色ck解v1v2v3v4v5v7v6c1C1={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}c282三、頂點著色的算法例解4（3）對頂點vi的所有鄰接點vj(j>i)，作Cj=Cj-{ck}；解v1v2v3v4v5v7v6c1C1={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}c2C3={c3}83三、頂點著色的算法例解5解v1v2v3v4v5v7v6c1C1={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（4）轉(zhuǎn)到（2），直到所有頂點都著色為止（2）標(biāo)頂點vi(i=1,2,…,n)的顏色集Ci的第一種顏色ckc384三、頂點著色的算法例解6解v1v2v3v4v5v7v6c1C1={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(j>i)，作Cj=Cj-{ck}；c3C5={c2,c4,c5}C1={c1,c2,c4}85三、頂點著色的算法例解7解v1v2v3v4v5v7v6c1C1={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（4）轉(zhuǎn)到（2），直到所有頂點都著色為止（2）標(biāo)頂點vi(i=1,2,…,n)的顏色集Ci的第一種顏色ckc3c186三、頂點著色的算法例解8解v1v2v3v4v5v7v6c1C1={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(j>i)，作Cj=Cj-{ck}；c3c187三、頂