【正文】 頂點(diǎn)著色算法 下面給出頂點(diǎn)著色的算法 (假定 G的頂點(diǎn)為 v1,v2,…,v n。 一、邊的著色問(wèn)題 3 定理 ：二分圖 G的邊色數(shù)＝圖中頂點(diǎn)的最大度。在 K(1) ，K(2)的邊加上若干頂點(diǎn)所形成的圖也不是平面圖 。 6 平面圖－ 3 歐拉公式定理（ 必要條件 ）：如果平面連通圖 G有 n個(gè)頂點(diǎn)， m條邊， d個(gè)區(qū)域，則 n－ m＋ d＝ 2 證明：設(shè)圖 G是有 n個(gè)頂點(diǎn)一棵樹，則 m＝ n－ 1， d＝ 1，這時(shí) n－ m＋ d＝ 2成立。 如果圖已經(jīng)畫在平面上，稱圖 G為 平面圖 。 ??Ceec )(郵局 v1 v2 v3 v4 v5 v6 3 4 5 2 1 4 2 6 3 5 1 v0 ? 問(wèn)題分析： （ 1）如果道路正好是一個(gè) Euler圖，則容易求解，用 Fleury算法求出一個(gè) Euler回路即可； （ 2）如果不是 Euler圖，則加上如干重復(fù)邊，使之變成 Euler圖，然后求 Euler回路。 與假設(shè) d(vi)+d(vj)≥n1矛盾，所以 G連通。 ? 在圖 G中，若存在通過(guò)每個(gè)頂點(diǎn)各一次的道路，則稱這條道路為 Hamilton道路 。 …… v1 v2 v5 v3 v4 v6 v7 v8 v9 1 2 3 v1 v2 v5 v3 v4 v6 v7 v8 v9 1 2 3 4 5 6 7 8 依序去掉相連的邊但必須注意下列兩條件： a、如果某邊去掉后會(huì)導(dǎo)致某點(diǎn)無(wú)連通的 邊，則此頂點(diǎn)亦可去。 v1 v2 v5 v3 v4 v6 v7 v8 v9 依序去掉相連的邊但必須注意下列兩條件： a、如果某邊去掉后會(huì)導(dǎo)致某點(diǎn)無(wú)連通的 邊，則此頂點(diǎn)亦可去。 (2)依序去掉相連的邊但必須注意下列兩條件： a、如果某邊去掉后會(huì)導(dǎo)致某點(diǎn)無(wú)連通的邊，則此頂點(diǎn)亦可去。 假設(shè) C不是 Euler回路。 所以存在 Euler回路。 b、去某邊后不能造成圖形的不連通。 30 2022/2/13 The necessary condition for Hamilton path and Hamilton circuit For undirected graph: The necessary condition for the existence of Hamilton path: ? G is connected。 假設(shè) G不連通，則 G至少有兩個(gè)連通分量。 v1 v2 vp1 vL vp vk 則根據(jù)條件 d(vi)+d(vj)≥n1，有如下圖示： 37 2022/2/13 〖 Example 5〗 There are seven people denoted by A, B, C, D, E, F, G. Suppose that the following facts are known. AEnglish (A can speak English.) BEnglish, Chinese CEnglish, Italian, Russian DJapanese, Chinese EGerman, Italia FFrench, Japanese, Russian GFrench, German How to arrange seat for the round desk such that the seven people can talk each other? 38 2022/2/13 (1) Construct graph V={A,B,C,D,E,F,G}, E={(u,v)|u,v can speak at least one mon language.} Solution: AEnglish (A can speak English.) BEnglish, Chinese CEnglish, Italian, Russian DJapanese, Chinese EGerman, Italia FFrench, Japanese, Russian GFrench, German A B C D E F G (2) If there is a H circuit, then we can arrange seat for the round desk such that the seven people can talk each other. H circuit: A,B,D,F,G,E,C,A A B D F G E C 中國(guó)郵路問(wèn)題 中國(guó)郵路問(wèn)題 (Chinese postman problem)， 是我國(guó)數(shù)學(xué)家管梅谷于 1960年首次提出的。 v1 v2 v3 v4 v6 v5 v7 5 1 3 2 2 3 2 5 4 3 3 解：其中 v2， v3， v4， v5， v6， v7頂點(diǎn)的度都是奇數(shù)，引入重復(fù)邊。 6 平面圖－ 2 平面圖的邊把圖 G所在的平面劃分為若干個(gè)區(qū)域，每個(gè)區(qū)域稱為圖 G的 面 ； 包圍每個(gè)面的回路稱為面的 邊界 ； 回路的邊數(shù)稱為面的 次數(shù) 。 6 平面圖－ 6 Kuratowski圖 K(2)圖 K(2)圖又稱 二分圖 二分圖是什么？ 如果圖的頂點(diǎn)集可以分為兩個(gè)互不相交的子集，子集內(nèi)結(jié)點(diǎn)互不鄰接，則此圖稱為 二部圖 。 根據(jù) Kuratowski定理，可以斷定：所有 樹 都是平面圖。 二、頂點(diǎn)的著色問(wèn)題 1 ? 色數(shù)的性質(zhì)： （ 1）圖 G只有孤立點(diǎn)時(shí)， χ(G)=1； （ 2） n個(gè)頂點(diǎn)的完全圖 G有 χ(G)=n； 二、頂點(diǎn)的著色問(wèn)題 1 （ 3）若圖 G是 n個(gè)頂點(diǎn)的回路，則 χ(G)=2 n為偶數(shù) =3 n為奇數(shù)； 二、頂點(diǎn)的著色問(wèn)題 1 （ 4）圖 G是頂點(diǎn)數(shù)超過(guò) 1的樹時(shí)， χ(G)=2； 二、頂點(diǎn)的著色問(wèn)題 1 （ 5）若圖 G是二分圖，則 χ(G)=2。 例 v1 v2 v3 v4 v5 v7 v6 三、頂點(diǎn)著色的算法例解 （ 1）對(duì) i=1,2,…,n, 作 Ci={c1,c2,…,c i}； 解 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}