【正文】 nly if 一個沒有孤立頂點的有向多重圖含有歐拉回路的充要條件是： the graph is weakly connected 弱連通的 the indegree and outdegree of each vertex are equal 每個頂點的出度和入度相等 24 2022/2/13 A directed multigraph having no isolated vertices has an Euler path but not an Euler circuit if and only if 一個沒有孤立頂點的有向多重圖含有歐拉通路但不含歐拉回路的充要條件是： 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. 除去兩個頂點外每個頂點的出度和入度相等，其中一個頂點的出度比入度大 1，另一個頂點的入度比出度大 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中每個頂點次數(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. 哈密頓回路，僅訪問每個頂點一次，但除去始點，這個始點同樣也是終點。 b、去某邊后不能造成圖形的不連通。 b、去某邊后不能造成圖形的不連通。 b、去某邊后不能造成圖形的不連通。 b、去某邊后不能造成圖形的不連通。 b、去某邊后不能造成圖形的不連通。 b、去某邊后不能造成圖形的不連通。 所以存在 Euler回路。 v1 v2 v5 v3 v4 v6 v7 v8 v9 解：首先看圖中是否有 Euler回路，即看每個頂點的度是否都是偶數(shù)。 b、去某邊后不能造成圖形的不連通。 C 8 2022/2/13 Necessary and sufficient condition for Euler circuit and paths 歐拉回路和歐拉通路的充要條件 【 Theorem 1】 連通多重圖具有歐拉回路當且僅當它的每個頂 點都有偶數(shù)度 Proof: (1) Necessary condition必要條件 G has an Euler circuit ? Every vertex in V has even degree Consider the Euler circuit. ? the vertex a which the Euler circuit begins with ? the other vertex 9 2022/2/13 (2) sufficient condition We will form a simple circuit that begins at an arbitrary vertex a of G. ? Build a simple path x0=a, x1, x2,…, xn=a. ? An Euler circuit has been constructed if all the edges have been used. otherwise, ? Consider the subgraph H obtained from G. Let w be a vertex which is the mon vertex of the circuit and H. Beginning at w, construct a simple path in H. 10 2022/2/13 【 Theorem 2】 連通多重圖具有歐拉通路而無歐拉回路， 當且僅當它恰有兩個奇數(shù)度頂點 〖 Example 1〗 Konigsberg Seven Bridge Problem 哥尼斯堡七橋問題 C A B D Solution: The graph has four vertices of odd degree. Therefore, it does not have an Euler 11 2022/2/13 〖 Example 2〗 Determine whether the following graph has an Euler path. Construct such a path if it 具有歐拉通路，如果存在構(gòu)建一條通路 B C D E F G H I J A Solution: The graph has 2 vertices of odd degree, and all of other vertices have even degree . Therefore, this graph has an Euler path. 12 2022/2/13 〖 Example 2〗 Determine whether the following graph has an Euler path. Construct such a path if it exists. B C D E F G H I J A Solution: The graph has 2 vertices of odd degree, and all of other vertices have even degree . Therefore, this graph has an Euler path. The Euler path: A,C,E,F,G,I,J,E,A,B,C,D,E,G, H,I,G,J