离散数学课件第5章.ppt
《离散数学课件第5章.ppt》由会员分享,可在线阅读,更多相关《离散数学课件第5章.ppt(89页珍藏版)》请在三一办公上搜索。
1、1,离散数学Discrete Mathematics,汪荣贵 教授合肥工业大学软件学院专用课件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 Graph Colo
2、ring 平面图与着色5.7 Trees 树,4,2023/10/17,一、Euler Paths,Konigsberg Seven Bridge Problem 哥尼斯堡七桥问题,5,2023/10/17,Terminologies:Euler Circuit 图G里的欧拉回路是包含着G的每一条边的简单回路.Euler Path 图G里的欧拉通路是包含着G的每一条边的简单通路 Euler Graph A graph contains an Euler circuit.,判别定理:无向图G是欧拉图当且仅当G是连通图,且G中没有奇度顶点。(充要条件)证明(反证法):设C=(e1=(v0,v1),
3、e2=(v1,v2),em=(vm-1,v0)是图中最大的回路。假设C不是Euler回路。则图G如下图所示:,图是连通的,则顶点不可能出现下面的情况:,图中任意结点的度均为偶数,有如下所示:,与假设矛盾,C是Euler回路。,8,2023/10/17,Necessary and sufficient condition for Euler circuit and paths欧拉回路和欧拉通路的充要条件,【Theorem 1】连通多重图具有欧拉回路当且仅当它的每个顶点都有偶数度,Proof:Necessary condition必要条件 G has an Euler circuit Every
4、vertex in V has even degree Consider the Euler circuit.the vertex a which the Euler circuit begins with the other vertex,9,2023/10/17,(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 construc
5、ted 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,2023/10/17,【Theorem 2】连通多重图具有欧拉通路而无欧拉回路,当且仅当它恰有两个奇数度顶点,Example 1 Konigsberg Seven Bridge Problem哥尼斯堡
6、七桥问题,Solution:The graph has four vertices of odd degree.Therefore,it does not have an Euler circuit.欧拉回路,11,2023/10/17,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
7、of other vertices have even degree.Therefore,this graph has an Euler path.,12,2023/10/17,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 have even degree.Therefore,this gra
8、ph 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)可从任一点出发去掉连接此点的一边。(2)依序去掉相连的边但必须注意下列两条件:a、如果某边去掉后会导致某点无连通的边,则此顶点亦可去。b、去某边后不能造成图形的不连通。,例:求出下图的一条Euler回路。,解:首先看图中是否有Euler回路,即看每个顶点的度是否都是偶数。d(V1)=2,d(V2)=4,d(V3)=2,d(V4)=4,d(V5)=4,d(V6)=4,d(V7)=2,d(V
9、8)=2,d(V9)=4。所以存在Euler回路。可以任意一个顶点为起点,这里以v2为起点:,依序去掉相连的边但必须注意下列两条件:a、如果某边去掉后会导致某点无连通的边,则此顶点亦可去也。b、去某边后不能造成图形的不连通。,依序去掉相连的边但必须注意下列两条件:a、如果某边去掉后会导致某点无连通的 边,则此顶点亦可去。b、去某边后不能造成图形的不连通。,(1)先去掉(v2,v4),例子11解答4,依序去掉相连的边但必须注意下列两条件:a、如果某边去掉后会导致某点无连通的 边,则此顶点亦可去。b、去某边后不能造成图形的不连通。,(2)接着去掉(v4,v3),依序去掉相连的边但必须注意下列两条件
10、:a、如果某边去掉后会导致某点无连通的 边,则此顶点亦可去。b、去某边后不能造成图形的不连通。,(3)接着去掉(v3,v2),依序去掉相连的边但必须注意下列两条件:a、如果某边去掉后会导致某点无连通的 边,则此顶点亦可去。b、去某边后不能造成图形的不连通。,依序去掉相连的边但必须注意下列两条件:a、如果某边去掉后会导致某点无连通的 边,则此顶点亦可去。b、去某边后不能造成图形的不连通。,这时,如果去掉(v6,v5)将导致图不连通,V2-v4-v3-v2-v1-v4-v5-v9-v6-v8-v9-v7-v6-v5-v2,Euler回路:,从上例可知,Euler回路不唯一。,23,2023/10/
11、17,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 out-degree of each vertex are equal 每个顶点的出度和入度相等,24,2023/10/17,A directe
12、d 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 all but two vertices,one that has in-degree 1 larger than its out-degree a
13、nd the other that has out-degree 1 larger than its in-degree.除去两个顶点外每个顶点的出度和入度相等,其中一个顶点的出度比入度大1,另一个顶点的入度比出度大1.,25,2023/10/17,Example 3 Determine whether the directed graph has an Euler path.Construct an Euler path if it exists.,Hence,the directed graph has an Euler path.,Solution:,26,2023/10/17,Appl
14、ication,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,2023/10/17,二、Hamilton paths and circuit 哈密顿通路和回路,Hamiltons puzzle,28,2023/10/17,A
15、Hamilton path in a graph G is a path which visits ever vertex in G exactly once.哈密顿通路是一个访问图G中每个顶点次数有且仅有一次的通路 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.哈密顿回路,仅访问每个顶点一次,但除去始点,这个始点同样也是
16、终点。If a connected graph G has a Hamilton circuit,then G is called a Hamilton graph.如果一个连通图G含有哈密顿回路,那么G是哈密顿图 Note:定义适用与所有类型的有向图和无向图.,29,2023/10/17,The sufficient condition for the existence of Hamilton path and Hamilton circuit哈密顿通路和哈密顿回路存在的充分条件,【Theorem 3】DIRACTHEOREM 狄拉克定理如果G是带n个顶点的连通简单图,其中 n=3,则G有
17、哈密顿回路的充分条件是每个顶点的度都至少为 n/2,【Theorem 4】ORETHEOREM 奥尔定理If G is a simple graph with n vertices with n=3 such thatdeg(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有哈密顿回路。,30,2023/10/17,The nece
18、ssary 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
19、 larger than 1.,Hamilton回路,定义:若图G存在一条回路P,它通过G的每个顶点各一次又回到起点,则这回路称为G的Hamilton回路。若图G中存在Hamilton回路,则称G为Hamilton图。在图G中,若存在通过每个顶点各一次的道路,则称这条道路为Hamilton道路。,定理(充分条件):设简单图G的顶点数为n(n3),若G中任意一对顶点vi、vj,恒有d(vi)+d(vj)n-1,则图G中至少有一条Hamilton道路。推论(充分条件):若任意一对顶点vi、vj,恒有d(vi)+d(vj)n,则图G中至少有一条Hamilton回路。,下面证明Hamilton道路的存
20、在。证明:(1)先证明G是连通的。假设G不连通,则G至少有两个连通分量。设其中一部分有n1个顶点,另一部分有n2个顶点。分别在两部分各选一个顶点v1、v2,G是简单图,所以:d(v1)n11,d(v2)n21,d(v1)+d(v2)n1 n2 2n1。与假设d(vi)+d(vj)n-1矛盾,所以G连通。,(2)再证明存在Hamilton道路:假设G中有一条从v1到vL道路 T=(v1,v2,vL)是图中的最长道路,即起点v1和终点vL不和T之外的顶点相邻。(a)如果Ln,即T是包含所有顶点的道路,即T是Hamilton道路,得证。(b)若Ln且v1和vL相邻,则存在包含T的回路;,若Ln且v1



- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 课件

链接地址:https://www.31ppt.com/p-6326537.html