【正文】 歐拉回路求解方法 （ Fleury‘s algorithm ）： (1)可從任一點出發(fā)去掉連接此點的一邊。 假設(shè) C不是 Euler回路。1 離散數(shù)學(xué) Discrete Mathematics 汪榮貴 教授 合肥工業(yè)大學(xué)軟件學(xué)院專用課件 Chapter 5 graph theory 3 CHAPTER 5 Graphs Introduction to Graphs 圖的概述 Graph Terminology 圖的術(shù)語 Representing Graphs and Graph Isomorphism圖的表示和圖的同構(gòu) Connectivity 連通性 Euler and Hamilton Paths 歐拉通路和哈密頓通路 Planar Graphs and Graph Coloring 平面圖與著色 Trees 樹 4 2022/2/13 一、 Euler Paths Konigsberg Seven Bridge Problem 哥尼斯堡七橋問題 ACBDC A B D 5 2022/2/13 Terminologies: ? Euler Circuit 圖 G里的歐拉回路是包含著 G的每一條邊的簡單回路 . ? Euler Path 圖 G里的歐拉通路是包含著 G的每一條邊的簡單通路 ? Euler Graph A graph contains an Euler circuit. 判別定理：無向圖 G是歐拉圖當(dāng)且僅當(dāng) G是連通圖，且 G中沒有奇度頂點。 (充要條件 ) 證明（反證法）： 設(shè) C=(e1=(v0,v1),e2=(v1,v2),…,e m=(vm1 ,v0))是圖中最大的回路。則圖 G如下圖所示： C C 或 ∵ 圖是連通的，則頂點不可能出現(xiàn)下面的情況： C ∵ 圖中任意結(jié)點的度均為偶數(shù)， ∴ 有如下所示： C 與假設(shè)矛盾， ∴ C是 Euler回路。 (2)依序去掉相連的邊但必須注意下列兩條件： a、如果某邊去掉后會導(dǎo)致某點無連通的邊，則此頂點亦可去。 例 : 求出下圖的一條 Euler回路。 d(V1)=2， d(V2)=4， d(V3)=2， d(V4)=4， d(V5)=4， d(V6)=4， d(V7)=2， d(V8)=2， d(V9)=4。 可以任意一個頂點為起點，這里以 v2為起點 : v1 v2 v5 v3 v4 v6 v7 v8 v9 依序去掉相連的邊但必須注意下列兩條件： a、如果某邊去掉后會導(dǎo)致某點無連通的邊，則此頂點亦可去也。 v1 v2 v5 v3 v4 v6 v7 v8 v9 依序去掉相連的邊但必須注意下列兩條件： a、如果某邊去掉后會導(dǎo)致某點無連通的 邊，則此頂點亦可去。 (1)先去掉 (v2,v4) v1 v2 v5 v3 v4 v6 v7 v8 v9 1 例子 1－ 1解答－ 4 依序去掉相連的邊但必須注意下列兩條件： a、如果某邊去掉后會導(dǎo)致某點無連通的 邊，則此頂點亦可去。 (2)接著去掉 (v4,v3) v1 v2 v5 v3 v4 v6 v7 v8 v9 1 2 依序去掉相連的邊但必須注意下列兩條件： a、如果某邊去掉后會導(dǎo)致某點無連通的 邊，則此頂點亦可去。 (3)接著去掉 (v3,v2) v1 v2 v5 v3 v4 v6 v7 v8 v9 1 2 3 依序去掉相連的邊但必須注意下列兩條件： a、如果某邊去掉后會導(dǎo)致某點無連通的 邊，則此頂點亦可去。 …… 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、如果某邊去掉后會導(dǎo)致某點無連通的 邊，則此頂點亦可去。 這時，如果去掉 (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回路不唯一。 If a connected graph G has a Hamilton circuit, then G is called a Hamilton graph. 如果一個連通圖 G含有 哈密頓回路，那么 G是哈密頓圖 Note: 定義適用與所有類型的有向圖和無向圖 . 29 2022/2/13 The sufficient condition for the existence of Hamilton path and Hamilton circuit哈密頓通路和哈密頓回路存在的充分條件 【 Theorem 3】 DIRAC‘THEOREM 狄拉克定理 如果 G是帶 n個頂點的連通簡單圖，其中 n=3，則 G有哈密頓 回路的充分條件是每個頂點的度都至少為 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個頂點的連通簡單圖，其中 n=3 ，并且對于 G中 每一對不相鄰的頂點 u和 v來說，都有 deg(u)+deg(v) = n ， 則 G有哈密頓回路。 ? 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，它通過 G的每個頂點各一次又回到起點，則這回路稱為 G的 Hamilton回路 。 ? 在圖 G中，若存在通過每個頂點各一次的道路，則稱這條道路為 Hamilton道路 。 ?推論 (充分條件 ) ：若任意一對頂點 vi、 vj，恒有d(vi)+d(vj)≥n，則圖 G中至少有一條 Hamilton回路。 證明： (1)先證明 G是連通的。設(shè)其中一部分有 n1個頂點，另一部分有 n2個頂點。 與假設(shè) d(vi)+d(vj)≥n1矛盾，所以 G連通。 (a)如果 L＝ n，即 T是包含所有頂點的道路，即 T是 Hamilton道路，得證。 Hamilton定理證明－ 3 (c)證明存在比 T更長的道路： 與假設(shè)矛盾， 重復(fù)（ a）～（ c），在有限步內(nèi)一定得到 包含所有頂點的 Hamilon道路。 問題描述： 設(shè)郵遞員從郵局出發(fā)，遍歷他所管轄的每一條街道，將信件送到后返回郵局，求所走的路徑最短。 ??Ceec )(郵局 v1 v2 v3 v4 v5 v6 3 4 5