【正文】 例 v1 v2 v3 v4 v5 v7 v6 三、頂點(diǎn)著色的算法例解 （ 1）對(duì) i=1,2,… ,n,作 Ci={c1,c2,… ,ci}； 解 v1 v2 v3 v4 v5 v7 v6 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} 三、頂點(diǎn)著色的算法例解 1 （ 2）標(biāo)頂點(diǎn) 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} v1 v2 v3 v4 v5 v7 v6 c1 三、頂點(diǎn)著色的算法例解 2 （ 3）對(duì)頂點(diǎn) vi的所有鄰接點(diǎn) vj(ji)，作 Cj= Cj{ck}； 解 v1 v2 v3 v4 v5 v7 v6 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} 7 2,c3,c4,c5,c6,c7} 5 2,c3,c4,c5} 2 3 4 5 6} 三、頂點(diǎn)著色的算法例解 3 （ 4）轉(zhuǎn)到（ 2），直到所有頂點(diǎn)都著色為止 （ 2）標(biāo)頂點(diǎn) vi (i=1,2,… ,n)的顏色集 Ci的第一種顏色 ck 解 v1 v2 v3 v4 v5 v7 v6 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 三、頂點(diǎn)著色的算法例解 4 （ 3）對(duì)頂點(diǎn) vi的所有鄰接點(diǎn) vj(ji)，作Cj= Cj{ck}； 解 v1 v2 v3 v4 v5 v7 v6 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 3} 三、頂點(diǎn)著色的算法例解 5 解 v1 v2 v3 v4 v5 v7 v6 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 （ 4）轉(zhuǎn)到（ 2），直到所有頂點(diǎn)都著色為止 （ 2）標(biāo)頂點(diǎn) vi (i=1,2,… ,n)的顏色集 Ci的第一種顏色 ck c3 三、頂點(diǎn)著色的算法例解 6 解 v1 v2 v3 v4 v5 v7 v6 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）對(duì)頂點(diǎn) vi的所有鄰接點(diǎn) vj(ji)，作 Cj= Cj{ck}； c3 4 5} 1 4} 三、頂點(diǎn)著色的算法例解 7 解 v1 v2 v3 v4 v5 v7 v6 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 （ 4）轉(zhuǎn)到（ 2），直到所有頂點(diǎn)都著色為止 （ 2）標(biāo)頂點(diǎn) vi (i=1,2,… ,n)的顏色集 Ci的第一種顏色 ck c3 c1 三、頂點(diǎn)著色的算法例解 8 解 v1 v2 v3 v4 v5 v7 v6 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）對(duì)頂點(diǎn) vi的所有鄰接點(diǎn) vj(ji)，作 Cj= Cj{ck}； c3 c1 三、頂點(diǎn)著色的算法例解 9 解 v1 v2 v3 v4 v5 v7 v6 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 （ 4）轉(zhuǎn)到（ 2），直到所有頂點(diǎn)都著色為止 （ 2）標(biāo)頂點(diǎn) vi (i=1,2,… ,n)的顏色集 Ci的第一種顏色 ck c3 c1 c2 三、頂點(diǎn)著色的算法例解 10 解 v1 v2 v3 v4 v5 v7 v6 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）對(duì)頂點(diǎn) vi的所有鄰接點(diǎn) vj(ji)，作 Cj= Cj{ck}； c3 c1 c2 3 4 5 6} 三、頂點(diǎn)著色的算法例解 11 解 v1 v2 v3 v4 v5 v7 v6 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），直到所有頂點(diǎn)都著色為止 （ 2）標(biāo)頂點(diǎn) vi (i=1,2,… ,n)的顏色集 Ci的第一種顏色 ck c3 c1 c2 c3 三、頂點(diǎn)著色的算法例解 12 解 v1 v2 v3 v4 v5 v7 v6 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）對(duì)頂點(diǎn) vi的所有鄰接點(diǎn) vj(ji)，作 Cj= Cj{ck}； c3 c1 c2 7 2,c4,c5,c6,c7} c3 三、頂點(diǎn)著色的算法例解 13 解 v1 v2 v3 v4 v5 v7 v6 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），直到所有頂點(diǎn)都著色為止 （ 2）標(biāo)頂點(diǎn) vi (i=1,2,… ,n)的顏色集 Ci的第一種顏色 ck c3 c1 c2 c3 c2 三、頂點(diǎn)著色的算法 注 ：上述算法并 不能 保證求出的著色方案用的顏色是最少的。用來染色的顏色為 c1,c2,… )： （ 1）對(duì) i=1,2,… ,n,作 Ci={c1,c2,… ,ci}； （ 2）標(biāo)頂點(diǎn) vi (i=1,2,… ,n)的顏色集 Ci的第一種顏色 ck； （ 3）對(duì)頂點(diǎn) vi的所有鄰接點(diǎn) vj(ji)，作 Cj= Cj{ck}； （ 4）轉(zhuǎn)到（ 2），直到所有頂點(diǎn)都著色為止。 二、頂點(diǎn)的著色問題 2 ? 定理 ：若圖 G=(V,E)， d=max{d(vi)},vi∈ V，則χ(G)≤d+1。 二、頂點(diǎn)的著色問題 1 ? 色數(shù)的性質(zhì)： （ 1）圖 G只有孤立點(diǎn)時(shí)， χ(G)=1； （ 2） n個(gè)頂點(diǎn)的完全圖 G有 χ(G)=n； 二、頂點(diǎn)的著色問題 1 （ 3）若圖 G是 n個(gè)頂點(diǎn)的回路，則 χ(G)=2 n為偶數(shù) =3 n為奇數(shù)； 二、頂點(diǎn)的著色問題 1 （ 4）圖 G是頂點(diǎn)數(shù)超過 1的樹時(shí)， χ(G)=2； 二、頂點(diǎn)的著色問題 1 （ 5）若圖 G是二分圖，則 χ(G)=2。 Shmir（ 1976）證明：在教師和班級(jí)提出條件時(shí)，判定課表的存在性問題是個(gè) NPplete問題。 ? ? 注 在實(shí)際應(yīng)用中，教師和班級(jí)往往會(huì)提出一些，例如所上節(jié)次時(shí)間的要求，問題變得很