離散數(shù)學(xué)課件第5章-文庫(kù)吧
2025-01-01 20:16 本頁(yè)面
【正文】 不能造成圖形的不連通。 (3)接著去掉 (v3,v2) v1 v2 v5 v3 v4 v6 v7 v8 v9 1 2 3 依序去掉相連的邊但必須注意下列兩條件： a、如果某邊去掉后會(huì)導(dǎo)致某點(diǎn)無(wú)連通的 邊，則此頂點(diǎn)亦可去。 b、去某邊后不能造成圖形的不連通。 …… 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)亦可去。 b、去某邊后不能造成圖形的不連通。 這時(shí)，如果去掉 (v6,v5)將導(dǎo)致圖不連通 v1 v2 v5 v3 v4 v6 v7 v8 v9 1 2 3 4 5 6 7 8 9 10 11 12 13 14 V2v4v3v2v1v4v5v9v6v8v9v7v6v5v2 Euler回路： 從上例可知， Euler回路不唯一。 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 一個(gè)沒(méi)有孤立頂點(diǎn)的有向多重圖含有歐拉回路的充要條件是： the graph is weakly connected 弱連通的 the indegree and outdegree of each vertex are equal 每個(gè)頂點(diǎn)的出度和入度相等 24 2022/2/13 A directed multigraph having no isolated vertices has an Euler path but not an Euler circuit if and only if 一個(gè)沒(méi)有孤立頂點(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è)訪問(wèn)圖 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. 哈密頓回路，僅訪問(wèn)每個(gè)頂點(diǎn)一次，但除去始點(diǎn)，這個(gè)始點(diǎn)同樣也是終點(diǎn)。 If a connected graph G has a Hamilton circuit, then G is called a Hamilton graph. 如果一個(gè)連通圖 G含有 哈密頓回路，那么 G是哈密頓圖 Note: 定義適用與所有類型的有向圖和無(wú)向圖 . 29 2022/2/13 The sufficient condition for the existence of Hamilton path and Hamilton circuit哈密頓通路和哈密頓回路存在的充分條件 【 Theorem 3】 DIRAC‘THEOREM 狄拉克定理 如果 G是帶 n個(gè)頂點(diǎn)的連通簡(jiǎn)單圖，其中 n=3，則 G有哈密頓 回路的充分條件是每個(gè)頂點(diǎn)的度都至少為 n/2 【 Theorem 4】 ORE‘THEOREM 奧爾定理 If G is a simple graph with n vertices with n=3 such that deg(u)+deg(v) = n for every pair of nonadjacent vertices u and v in G , then G has a Hamilton circuit. 如果 G是帶 n個(gè)頂點(diǎn)的連通簡(jiǎn)單圖，其中 n=3 ，并且對(duì)于 G中 每一對(duì)不相鄰的頂點(diǎn) u和 v來(lái)說(shuō)，都有 deg(u)+deg(v) = n ， 則 G有哈密頓回路。 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。 ? There are at most two vertices which degree are less than 2. The necessary condition for the existence of Hamilton circuit: ? The degree of each vertex is larger than 1. Hamilton回路 ? 定義：若圖 G存在一條回路 P，它通過(guò) G的每個(gè)頂點(diǎn)各一次又回到起點(diǎn)，則這回路稱為 G的 Hamilton回路 。 ? 若圖 G中存在 Hamilton回路，則稱 G為 Hamilton圖 。 ? 在圖 G中，若存在通過(guò)每個(gè)頂點(diǎn)各一次的道路，則稱這條道路為 Hamilton道路 。 ?定理 (充分條件 ) ：設(shè)簡(jiǎn)單圖 G的頂點(diǎn)數(shù)為 n(n3)，若 G中任
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1