《离散数学课件第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
21、和vL不相邻，则根据条件d(vi)+d(vj)n-1，有如下图示：,所以存在包含T的回路。,Hamilton定理证明3,(c)证明存在比T更长的道路：,与假设矛盾，重复（a）（c），在有限步内一定得到包含所有顶点的Hamilon道路。,则根据条件d(vi)+d(vj)n-1，有如下图示：,37,2023/10/17,Example 5 There are seven people denoted by A,B,C,D,E,F,G.Suppose that the following facts are known.A-English(A can speak English.)B-English
22、,ChineseC-English,Italian,RussianD-Japanese,ChineseE-German,ItaliaF-French,Japanese,RussianG-French,German How to arrange seat for the round desk such that the seven people can talk each other?,38,2023/10/17,Construct graph V=A,B,C,D,E,F,G,E=(u,v)|u,v can speak at least one common language.,Solution
23、:,A-English(A can speak English.)B-English,ChineseC-English,Italian,RussianD-Japanese,ChineseE-German,ItaliaF-French,Japanese,RussianG-French,German,(2)If there is a H circuit,then we can arrange seat for the round desk such that the seven people can talk each other.H circuit:A,B,D,F,G,E,C,A,中国邮路问题,
24、中国邮路问题(Chinese postman problem)，是我国数学家管梅谷于1960年首次提出的。问题描述：设邮递员从邮局出发，遍历他所管辖的每一条街道，将信件送到后返回邮局，求所走的路径最短。,中国邮路问题的图论模型为：设G=(V,E)是连通图，而且对于所有的eE都赋以权c(e)0，求从点v0V出发，通过所有边至少一次最后返回v0的回路C，使得 达到最小。,问题分析：（1）如果道路正好是一个Euler图，则容易求解，用Fleury算法求出一个Euler回路即可；（2）如果不是Euler图，则加上如干重复边，使之变成Euler图，然后求Euler回路。现在问题的关键：如何加重复边！中国
25、邮路问题是Euler回路的近似求解。,定理：设E*E是使W(E*)=达到最小 的重复边集合，当且仅当对于Ga图的任一回 路，恒有W(E*)W(E()-E*),E*是重复边集合,Ga是加重复边以后的Euler图,E*=(v2,v3)E(C)=(v1,v2),(v1,v3)(v2,v3)(v2,v4)(v3,v4),中国邮路构造算法,设已经知道度为奇数的顶点为v1,v2,v2h第一步：添加重复边：i从1到h，引从v2i-1到v2i的链Pi，并对Pi的每条边附加1条重复边；第二步：检查重复边：检查图G的每条边，使得每条边最多有1条重复边，得到图G，G中重复边集记为E(0)；,第三步：设初值k0；,(
26、a)若E(k)对于回路 有，则,E(k1)=E(k)E()，kk1，转(a)；,(b)输出E(k)，E(k)便是最优集。,第四步：用Fleury算法求出Eluer回路。,例 求出下图中以v1为起点的一条中国邮路。,解：其中v2，v3，v4，v5，v6，v7顶点的度都是奇数，引入重复边。第一步：添加重复边：i从1到h，引从v2i-1到v2i的链Pi，并对Pi的每条边附加1条重复边；,E(0)=(v2,v3),(v4,v5),(v6,v7),第二步：检查重复边：检查图G的每条边，使得每条边最多有1条重复边，得到图G，G中重复边集记为E(0)；,下面看回路：v2-v3-v7-v2 其中E()=(v2
27、,v3),(v2,v7),(v3,v7),E(0)=(v2,v3),(v4,v5),(v6,v7),5 224,E(1)E(0)E()(v2,v7),(v3,v7),(v4,v5),(v6,v7),E(1)=(v2,v7),(v3,v7),(v4,v5),(v6,v7),下面看回路：v4-v5-v6-v7-v4 其中E()=(v4,v7),(v4,v5),(v5,v6),(v6,v7),437 235,E(2)E(1)E()(v2,v7),(v3,v7),(v4,v7),(v5,v6),v5,E(2)=(v2,v7),(v3,v7),(v4,v7),(v5,v6),下面看回路：v3-v4-v7
28、-v3 其中E()=(v3,v4),(v4,v7),(v3,v7),E(3)E(2)E()(v2,v7),(v3,v4),(v5,v6),224 3,最后利用Fleury算法求出一个Euler回路：v1-v2-v3-v4-v3-v7-v2-v7-v4-v5-v7-v6-v5-v6-v1,E(3)=(v2,v7),(v3,v4),(v5,v6),练习：求下图中一条中国邮路：,52,CHAPTER 5 Graphs,5.1 Introduction to Graphs 图的概述5.2 Graph Terminology 图的术语5.3 Representing Graphs and Graph I
29、somorphism图的表示和图的同构 5.4 Connectivity 连通性5.5 Euler and Hamilton Paths 欧拉通路和哈密顿通路5.6 Planar Graphs and Graph Coloring 平面图与着色5.7 Trees 树,平面图,1、若图可以画在一个曲面上，任意两边都不相交（端点除外），称图G被嵌入在曲面上。2、如果曲面是平面称G是可平面图。3、如果图已经画在平面上，称图G为平面图。,可平面图,平面图,非平面图,6 平面图1,4、若有一个简单的平面图，再加一条边就是不可平面，则称之为最大平面图。,再加一条边就不是平面图了。,6 平面图2,5、平面图
30、的边把图G所在的平面划分为若干个区域，每个区域称为图G的面；6、包围每个面的回路称为面的边界；7、回路的边数称为面的次数。容易发现，平面图G每增加1条边，图G总的边数和面数都增加1。,边界,面,6 平面图3,8、欧拉公式定理（必要条件）：如果平面连通图G有n个顶点，m条边，d个区域，则 nmd2 证明：设图G是有n个顶点一棵树，则 mn1，d1，这时nmd2成立。G每增加1条边，即m增加1，这时d也增加1。所以(顶点数)(边数)(域数)2 不变。证毕。,6 平面图6,Kuratowski图,K(2)图又称二分图,二分图是什么？,如果图的顶点集可以分为两个互不相交的子集，子集内结点互不邻接，则此
31、图称为二部图。,6 平面图7,定理：K(1)，K(2)不是平面图。在K(1)，K(2)的边加上若干顶点所形成的图也不是平面图。,与这些图同构的图分别叫K(1)型图和K(2)型图,统称为K型图。,6 平面图8,Kuratowski定理 图G是平面图的充要条件是：G图不存在任何子图为K(1)图或K(2)图。证明较繁，在此不多述。根据Kuratowski定理，可以断定：所有树都是平面图。,边的着色问题,定义：给图G的边着色，使得有共同顶点的边异色的最少颜色数，称为边色数。,边色数=3,一、边的着色问题,课程考试安排问题；用顶点v1,v2,vn表示n门课程，若其中两门课i,j被同时选，则vi,vj间连
32、一条边。,一、边的着色问题3,定理：二分图G的边色数图中顶点的最大度。,一、边的着色问题3,定理(Vizing 1964)：若图G为简单图，图中顶点最大度为d，则G的边色数为d或d+1。,第一类图,第二类图,一、边的着色问题4,边的着色问题可以转化为顶点的着色问题。,顶点的着色问题,定义：给图G的顶点着色，使得相邻的顶点异色的最少颜色数，称为图G顶色数，简称色数；记作(G)。,(G)=2,二、顶点的着色问题,物资存储问题；四色猜想：平面图的色数不大于5。,二、顶点的着色问题1,色数的性质：（1）图G只有孤立点时，(G)=1；（2）n个顶点的完全图G有(G)=n；,二、顶点的着色问题1,（3）若
33、图G是n个顶点的回路，则(G)=2 n为偶数=3 n为奇数；,二、顶点的着色问题1,（4）图G是顶点数超过1的树时，(G)=2；,二、顶点的着色问题1,（5）若图G是二分图，则(G)=2。,二、顶点的着色问题2,定理：图G=(V,E)的色数(G)=2的充要条件是：(1)|E|1；(2)G不存在边数为奇数的回路。,二、顶点的着色问题2,定理：若图G=(V,E)，d=maxd(vi),viV，则(G)d+1。,顶点着色算法,下面给出顶点着色的算法(假定G的顶点为v1,v2,vn;用来染色的颜色为c1,c2,cn)：（1）对i=1,2,n,作Ci=c1,c2,ci；（2）标顶点vi(i=1,2,n)
34、的颜色集Ci的第一种颜色ck；（3）对顶点vi的所有邻接点vj(ji)，作Cj=Cj-ck；（4）转到（2），直到所有顶点都着色为止。,三、顶点着色的算法例,对下图顶点进行着色。,例,三、顶点着色的算法例解,（1）对i=1,2,n,作Ci=c1,c2,ci；,解,C1=c1C2=c1,c2C3=c1,c2,c3C4=c1,c2,c3,c4C5=c1,c2,c3,c4,c5C6=c1,c2,c3,c4,c5,c6C7=c1,c2,c3,c4,c5,c6,c7,三、顶点着色的算法例解1,（2）标顶点vi(i=1,2,n)的颜色集Ci的第一种颜色ck；,解,C1=c1C2=c1,c2C3=c1,c2
35、,c3C4=c1,c2,c3,c4C5=c1,c2,c3,c4,c5C6=c1,c2,c3,c4,c5,c6C7=c1,c2,c3,c4,c5,c6,c7,c1,三、顶点着色的算法例解2,（3）对顶点vi的所有邻接点vj(ji)，作Cj=Cj-ck；,解,c1,C1=c1C2=c1,c2C3=c1,c2,c3C4=c1,c2,c3,c4C5=c1,c2,c3,c4,c5C6=c1,c2,c3,c4,c5,c6C7=c1,c2,c3,c4,c5,c6,c7,C2=c2,C3=c2,c3,C7=c2,c3,c4,c5,c6,c7,C5=c2,c3,c4,c5,C6=c2,c3,c4,c5,c6,三
36、、顶点着色的算法例解3,（4）转到（2），直到所有顶点都着色为止（2）标顶点vi(i=1,2,n)的颜色集Ci的第一种颜色ck,解,c1,C1=c1C2=c2C3=c2,c3C4=c1,c2,c3,c4C5=c2,c3,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7,c2,三、顶点着色的算法例解4,（3）对顶点vi的所有邻接点vj(ji)，作Cj=Cj-ck；,解,c1,C1=c1C2=c2C3=c2,c3C4=c1,c2,c3,c4C5=c2,c3,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7,c2,C3=c3,三
37、、顶点着色的算法例解5,解,c1,C1=c1C2=c2C3=c3C4=c1,c2,c3,c4C5=c2,c3,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7,c2,（4）转到（2），直到所有顶点都着色为止（2）标顶点vi(i=1,2,n)的颜色集Ci的第一种颜色ck,c3,三、顶点着色的算法例解6,解,c1,C1=c1C2=c2C3=c3C4=c1,c2,c3,c4C5=c2,c3,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7,c2,（3）对顶点vi的所有邻接点vj(ji)，作Cj=Cj-ck；,c3,C5=c2,c
38、4,c5,C1=c1,c2,c4,三、顶点着色的算法例解7,解,c1,C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7,c2,（4）转到（2），直到所有顶点都着色为止（2）标顶点vi(i=1,2,n)的颜色集Ci的第一种颜色ck,c3,c1,三、顶点着色的算法例解8,解,c1,C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7,c2,（3）对顶点vi的所有邻接点vj(ji)，作Cj=Cj-ck；,c
39、3,c1,三、顶点着色的算法例解9,解,c1,C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7,c2,（4）转到（2），直到所有顶点都着色为止（2）标顶点vi(i=1,2,n)的颜色集Ci的第一种颜色ck,c3,c1,c2,三、顶点着色的算法例解10,解,c1,C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7,c2,（3）对顶点vi的所有邻接点vj(ji)，作Cj=Cj-ck；,c3,c1,c2,
40、C6=c3,c4,c5,c6,三、顶点着色的算法例解11,解,c1,C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7,c2,（4）转到（2），直到所有顶点都着色为止（2）标顶点vi(i=1,2,n)的颜色集Ci的第一种颜色ck,c3,c1,c2,c3,三、顶点着色的算法例解12,解,c1,C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7,c2,（3）对顶点vi的所有邻接点vj(ji)，作Cj=Cj-ck；,c3,c1,c2,C7=c2,c4,c5,c6,c7,c3,三、顶点着色的算法例解13,解,c1,C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c3,c4,c5,c6C7=c2,c4,c5,c6,c7,c2,（4）转到（2），直到所有顶点都着色为止（2）标顶点vi(i=1,2,n)的颜色集Ci的第一种颜色ck,c3,c1,c2,c3,c2,本节内容到此结束,谢谢大家！,
