【正文】 solated vertices has an Euler path but not an Euler circuit if and only if 一個(gè)沒有孤立頂點(diǎn)的有向多重圖含有歐拉通路但不含歐拉回路的充要條件是： the graph is weakly connected 弱連通的 the indegree and outdegree of each vertex are equal for all but two vertices, one that has indegree 1 larger than its outdegree and the other that has outdegree 1 larger than its indegree. 除去兩個(gè)頂點(diǎn)外每個(gè)頂點(diǎn)的出度和入度相等，其中一個(gè)頂點(diǎn)的出度比入度大 1，另一個(gè)頂點(diǎn)的入度比出度大 1. 25 2022/2/13 〖 Example 3〗 Determine whether the directed graph has an Euler path. Construct an Euler path if it exists. a c b d deg(v) deg+(v) a 1 2 b 2 2 c 2 2 d 3 2 Hence, the directed graph has an Euler path. Solution: 26 2022/2/13 Application A type of puzzle Draw a picture in a continuous motion without lifting a pencil so that no part of the picture is retraced. The equivalent problem: Whether the graph exist an Euler path or circuit. For example, 27 2022/2/13 二、 Hamilton paths and circuit 哈密頓通路和回路 Hamilton’s puzzle 28 2022/2/13 A Hamilton path in a graph G is a path which visits ever vertex in G exactly once. 哈密頓通路是一個(gè)訪問圖 G中每個(gè)頂點(diǎn)次數(shù)有且僅有一次的通路 A Hamilton circuit (or Hamilton cycle) is a cycle which visits every vertex exactly once, except for the first vertex, which is also visited at the end of the cycle. 哈密頓回路，僅訪問每個(gè)頂點(diǎn)一次，但除去始點(diǎn)，這個(gè)始點(diǎn)同樣也是終點(diǎn)。 ? 若圖 G中存在 Hamilton回路，則稱 G為 Hamilton圖 。 下面證明 Hamilton道路的存在。分別在兩部分各選一個(gè)頂點(diǎn) v v2， ∵ G是簡單圖，所以： d(v1)≤ n1－ 1 ， d(v2)≤ n2－ 1， d(v1)+d(v2) ≤ n1＋ n2－ 2＜ n－ 1。 (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的回路。 ? 中國郵路問題的圖論模型為： 設(shè) G=(V,E)是連通圖，而且對(duì)于所有的 e∈ E都賦以 權(quán)c(e)≥0，求從點(diǎn) v0∈ V出發(fā)，通過所有邊至少一次最后返回v0的回路 C，使得 達(dá)到最小。 ? 第四步 ：用 Fleury算法求出 Eluer回路。 如果曲面是平面 —— 稱 G是 可平面圖 。 再加一條邊就不是平面圖了。 邊界 面 167。 證畢。 6 平面圖－ 7 定理： K(1) ， K(2)不是平面圖。 6 平面圖－ 8 Kuratowski定理 圖 G是平面圖的 充要條件 是： G圖不存在任何子圖為 K(1) 圖或 K(2)圖。 邊色數(shù) =3 一、邊的著色問題 課程考試安排問題； 用頂點(diǎn) v1,v2,…,v n表示 n門課程，若其中兩門課 i,j被同時(shí)選，則 vi,vj間連一條邊。 頂點(diǎn)的著色問題 定義 ：給圖 G的頂點(diǎn)著色，使得相鄰的頂點(diǎn)異色的最少顏色數(shù)，稱為 圖 G頂色數(shù) ，簡稱 色數(shù) ；記作 χ(G)。 二、頂點(diǎn)的著色問題 2 ?定理 ：若圖 G=(V,E)， d=max{d(vi)},vi∈ V，則χ(G)≤d+1。 例 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} 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={c