【正文】 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} 三、頂點著色的算法例解 3 （ 4）轉(zhuǎn)到（ 2），直到所有頂點都著色為止 （ 2）標(biāo)頂點 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 三、頂點著色的算法例解 4 （ 3）對頂點 vi的所有鄰接點 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} 三、頂點著色的算法例解 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），直到所有頂點都著色為止 （ 2）標(biāo)頂點 vi (i=1,2,…,n) 的顏色集 Ci的第一種顏色 ck c3 三、頂點著色的算法例解 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）對頂點 vi的所有鄰接點 vj(ji)，作 Cj= Cj{ck}； c3 4 5} 1 4} 三、頂點著色的算法例解 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），直到所有頂點都著色為止 （ 2）標(biāo)頂點 vi (i=1,2,…,n) 的顏色集 Ci的第一種顏色 ck c3 c1 三、頂點著色的算法例解 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）對頂點 vi的所有鄰接點 vj(ji)，作 Cj= Cj{ck}； c3 c1 三、頂點著色的算法例解 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），直到所有頂點都著色為止 （ 2）標(biāo)頂點 vi (i=1,2,…,n) 的顏色集 Ci的第一種顏色 ck c3 c1 c2 三、頂點著色的算法例解 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）對頂點 vi的所有鄰接點 vj(ji)，作 Cj= Cj{ck}； c3 c1 c2 3 4 5 6} 三、頂點著色的算法例解 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），直到所有頂點都著色為止 （ 2）標(biāo)頂點 vi (i=1,2,…,n) 的顏色集 Ci的第一種顏色 ck c3 c1 c2 c3 三、頂點著色的算法例解 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）對頂點 vi的所有鄰接點 vj(ji)，作 Cj= Cj{ck}； c3 c1 c2 7 2,c4,c5,c6,c7} c3 三、頂點著色的算法例解 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），直到所有頂點都著色為止 （ 2）標(biāo)頂點 vi (i=1,2,…,n) 的顏色集 Ci的第一種顏色 ck c3 c1 c2 c3 c2 本節(jié)內(nèi)容到此結(jié)束 。 頂點的著色問題 定義 ：給圖 G的頂點著色，使得相鄰的頂點異色的最少顏色數(shù)，稱為 圖 G頂色數(shù) ，簡稱 色數(shù) ；記作 χ(G)。 6 平面圖－ 8 Kuratowski定理 圖 G是平面圖的 充要條件 是： G圖不存在任何子圖為 K(1) 圖或 K(2)圖。 證畢。 再加一條邊就不是平面圖了。 ? 第四步 ：用 Fleury算法求出 Eluer回路。 (b)若 L＜ n且 v1和 vL相鄰，則存在包含 T的回路； v1 v2 vp vL vL1 若 L＜ n且 v1和 vL不相鄰，則根據(jù)條件 d(vi)+d(vj)≥n1，有如下圖示： v1 v2 vp1 vL vp 所以存在包含 T的回路。 下面證明 Hamilton道路的存在。 23 2022/2/13 Euler circuit and paths in directed graphs 有向圖中的歐拉回路與歐拉通路 A directed multigraph having no isolated vertices has an Euler circuit if and only if 一個沒有孤立頂點的有向多重圖含有歐拉回路的充要條件是： the graph is weakly connected 弱連通的 the indegree and