離散數(shù)學課件第5章.ppt

1、1,離散數(shù)學 Discrete Mathematics,汪榮貴 教授 合肥工業(yè)大學軟件學院專用課件 2011.06,Chapter 5,graph theory,3,CHAPTER 5 Graphs,5.1 Introduction to Graphs 圖的概述 5.2 Graph Terminology 圖的術語 5.3 Representing Graphs and Graph Isomorphism圖的表示和圖的同構 5.4 Connectivity 連通性 5.5 Euler and Hamilton Paths 歐拉通路和哈密頓通路 5.6 Planar Graphs and Gra

2、ph Coloring 平面圖與著色 5.7 Trees 樹,4,2020/9/6,一、Euler Paths,Konigsberg Seven Bridge Problem 哥尼斯堡七橋問題,5,2020/9/6,Terminologies: Euler Circuit 圖G里的歐拉回路是包含著G的每一條邊的簡單回路. Euler Path 圖G里的歐拉通路是包含著G的每一條邊的簡單通路 Euler Graph A graph contains an Euler circuit.,判別定理：無向圖G是歐拉圖當且僅當G是連通圖，且G中沒有奇度頂點。 (充要條件) 證明（反證法）： 設C=(e1

3、=(v0,v1),e2=(v1,v2),em=(vm-1 ,v0)是圖中最大的回路。 假設C不是Euler回路。則圖G如下圖所示：, 圖是連通的，則頂點不可能出現(xiàn)下面的情況：,圖中任意結點的度均為偶數(shù)，有如下所示：,與假設矛盾， C是Euler回路。,8,2020/9/6,Necessary and sufficient condition for Euler circuit and paths 歐拉回路和歐拉通路的充要條件,【 Theorem 1】連通多重圖具有歐拉回路當且僅當它的每個頂 點都有偶數(shù)度,Proof: Necessary condition必要條件 G has an Euler

4、 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,2020/9/6,(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 circui

5、t 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 common vertex of the circuit and H. Beginning at w, construct a simple path in H.,10,2020/9/6,【 Theorem 2】 連通多重圖具有歐拉通路而無歐拉回路， 當且僅當它恰有兩個奇數(shù)度頂點,Example 1 Konigsberg

6、 Seven Bridge Problem 哥尼斯堡七橋問題,Solution: The graph has four vertices of odd degree. Therefore, it does not have an Euler circuit.歐拉回路,11,2020/9/6,Example 2 Determine whether the following graph has an Euler path. Construct such a path if it exists.判斷下圖是否具有歐拉通路，如果存在構建一條通路,Solution: The graph has 2 ve

7、rtices of odd degree, and all of other vertices have even degree . Therefore, this graph has an Euler path.,12,2020/9/6,Example 2 Determine whether the following graph has an Euler path. Construct such a path if it exists.,Solution: The graph has 2 vertices of odd degree, and all of other vertices h

8、ave 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,歐拉回路求解方法,（Fleurys algorithm ）： (1)可從任一點出發(fā)去掉連接此點的一邊。 (2)依序去掉相連的邊但必須注意下列兩條件： a、如果某邊去掉后會導致某點無連通的邊，則此頂點亦可去。 b、去某邊后不能造成圖形的不連通。,例: 求出下圖的一條Euler回路。,解：首先看圖中是否有Euler回路，即看每個頂點的度是否都是偶數(shù)。 d(V1)=2， d(V2

9、)=4， d(V3)=2， d(V4)=4， d(V5)=4， d(V6)=4， d(V7)=2， d(V8)=2， d(V9)=4。 所以存在Euler回路。 可以任意一個頂點為起點，這里以v2為起點:,依序去掉相連的邊但必須注意下列兩條件： a、如果某邊去掉后會導致某點無連通的邊，則此頂點亦可去也。 b、去某邊后不能造成圖形的不連通。,依序去掉相連的邊但必須注意下列兩條件： a、如果某邊去掉后會導致某點無連通的 邊，則此頂點亦可去。 b、去某邊后不能造成圖形的不連通。,(1)先去掉(v2,v4),例子11解答4,依序去掉相連的邊但必須注意下列兩條件： a、如果某邊去掉后會導致某點無連通的

10、邊，則此頂點亦可去。 b、去某邊后不能造成圖形的不連通。,(2)接著去掉(v4,v3),依序去掉相連的邊但必須注意下列兩條件： a、如果某邊去掉后會導致某點無連通的 邊，則此頂點亦可去。 b、去某邊后不能造成圖形的不連通。,(3)接著去掉(v3,v2),依序去掉相連的邊但必須注意下列兩條件： a、如果某邊去掉后會導致某點無連通的 邊，則此頂點亦可去。 b、去某邊后不能造成圖形的不連通。,依序去掉相連的邊但必須注意下列兩條件： a、如果某邊去掉后會導致某點無連通的 邊，則此頂點亦可去。 b、去某邊后不能造成圖形的不連通。,這時，如果去掉(v6,v5)將導致圖不連通,V2-v4-v3-v2-v1-

11、v4-v5-v9-v6-v8-v9-v7-v6-v5-v2,Euler回路：,從上例可知， Euler回路不唯一。,23,2020/9/6,Euler circuit and paths in directed graphs 有向圖中的歐拉回路與歐拉通路,A directed multigraph having no isolated vertices has an Euler circuit if and only if 一個沒有孤立頂點的有向多重圖含有歐拉回路的充要條件是： - the graph is weakly connected 弱連通的 - the in-degree and o

12、ut-degree of each vertex are equal 每個頂點的出度和入度相等,24,2020/9/6,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 in-degree and out-degree of each vertex are equal for

13、all but two vertices, one that has in-degree 1 larger than its out-degree and the other that has out-degree 1 larger than its in-degree. 除去兩個頂點外每個頂點的出度和入度相等，其中一個頂點的出度比入度大1，另一個頂點的入度比出度大1.,25,2020/9/6,Example 3 Determine whether the directed graph has an Euler path. Construct an Euler path if it exist

14、s.,Hence, the directed graph has an Euler path.,Solution:,26,2020/9/6,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,2020/

15、9/6,二、Hamilton paths and circuit 哈密頓通路和回路,Hamiltons puzzle,28,2020/9/6,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

16、, which is also visited at the end of the cycle. 哈密頓回路，僅訪問每個頂點一次，但除去始點，這個始點同樣也是終點。 If a connected graph G has a Hamilton circuit, then G is called a Hamilton graph. 如果一個連通圖G含有哈密頓回路，那么G是哈密頓圖 Note: 定義適用與所有類型的有向圖和無向圖.,29,2020/9/6,The sufficient condition for the existence of Hamilton path and Hamilton

17、circuit哈密頓通路和哈密頓回路存在的充分條件,【 Theorem 3】 DIRACTHEOREM 狄拉克定理 如果G是帶n個頂點的連通簡單圖，其中 n=3，則G有哈密頓 回路的充分條件是每個頂點的度都至少為 n/2,【 Theorem 4】ORETHEOREM 奧爾定理 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.

18、如果G是帶n個頂點的連通簡單圖，其中n=3 ，并且對于G中 每一對不相鄰的頂點u和v來說，都有deg(u)+deg(v) = n ， 則G有哈密頓回路。,30,2020/9/6,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，它通過G的每個頂點各一次又回到起點，則這回路稱為G的Hamilton回路。 若圖G中存在Hamilton回路，則稱G為Hamilton圖。 在圖G中，若存在通過每個頂點各一