【正文】 j{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。 頂點(diǎn)的著色問題 定義 ：給圖 G的頂點(diǎn)著色，使得相鄰的頂點(diǎn)異色的最少顏色數(shù)，稱為 圖 G頂色數(shù) ，簡稱 色數(shù) ；記作 χ(G)。 x1 x2 y1 x3 x4 x5 y2 y3 y4 y5 一、邊的著色問題 3 ? 定理 (Vizing 1964)：若圖 G為簡單圖，圖中頂點(diǎn)最大度為 d，則 G的邊色數(shù)為 d或 d+1。 邊色數(shù) =3 一、邊的著色問題 課程考試安排問題； 用頂點(diǎn) v1,v2,…,v n表示 n門課程，若其中兩門課 i,j被同時(shí)選，則 vi,vj間連一條邊。 根據(jù) Kuratowski定理，可以斷定：所有 樹 都是平面圖。 6 平面圖－ 8 Kuratowski定理 圖 G是平面圖的 充要條件 是： G圖不存在任何子圖為 K(1) 圖或 K(2)圖。 與這些圖同構(gòu)的圖分別叫 K(1)型圖和 K(2)型圖 , 統(tǒng)稱為 K型圖。 6 平面圖－ 7 定理： K(1) ， K(2)不是平面圖。 6 平面圖－ 6 Kuratowski圖 K(2)圖 K(2)圖又稱 二分圖 二分圖是什么？ 如果圖的頂點(diǎn)集可以分為兩個(gè)互不相交的子集，子集內(nèi)結(jié)點(diǎn)互不鄰接，則此圖稱為 二部圖 。 證畢。 G每增加 1條邊，即 m增加 1，這時(shí) d也增加 1。 邊界 面 167。 6 平面圖－ 2 平面圖的邊把圖 G所在的平面劃分為若干個(gè)區(qū)域，每個(gè)區(qū)域稱為圖 G的 面 ； 包圍每個(gè)面的回路稱為面的 邊界 ； 回路的邊數(shù)稱為面的 次數(shù) 。 再加一條邊就不是平面圖了。 圖 a 圖 b 圖 c 可平面圖 平面圖 非平面圖 167。 如果曲面是平面 —— 稱 G是 可平面圖 。 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ù)邊。 ? 第四步 ：用 Fleury算法求出 Eluer回路。 現(xiàn)在問題的 關(guān)鍵： 如何加重復(fù)邊！ 中國郵路問題是 Euler回路的近似求解。 ? 中國郵路問題的圖論模型為： 設(shè) G=(V,E)是連通圖，而且對(duì)于所有的 e∈ E都賦以 權(quán)c(e)≥0，求從點(diǎn) v0∈ V出發(fā)，通過所有邊至少一次最后返回v0的回路 C，使得 達(dá)到最小。 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 中國郵路問題 中國郵路問題 (Chinese postman problem)， 是我國數(shù)學(xué)家管梅谷于 1960年首次提出的。 (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的回路。 (2)再證明存在 Hamilton道路： 假設(shè) G中有一條從 v1到 vL道路 T=(v1,v2,…,v L)是圖中的最長道路，即起點(diǎn) v1和終點(diǎn) vL不和 T之外的頂點(diǎn)相鄰。分別在兩部分各選一個(gè)頂點(diǎn) v v2， ∵ G是簡單圖，所以： d(v1)≤ n1－ 1 ， d(v2)≤ n2－ 1， d(v1)+d(v2) ≤ n1＋ n2－ 2＜ n－ 1。 假設(shè) G不連通，則 G至少有兩個(gè)連通分量。 下面證明 Hamilton道路的存在。 ?定理 (充分條件 ) ：設(shè)簡單圖 G的頂點(diǎn)數(shù)為 n(n3)，若 G中任意一對(duì)頂點(diǎn) vi、 vj，恒有 d(vi)+d(vj)≥n1，則圖 G中至少有一條 Hamilton道路。 ? 若圖 G中存在 Hamilton回路，則稱 G為 Hamilton圖 。 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。 23 2022/2/13 Euler circuit and paths in directed graphs 有向圖中的歐拉回路與歐拉通路 A directed multigraph having no isolated vertices has an Euler circuit if and o