离散数学高等里离散数学-课件-CHAP5

1、1,第五章 图与子图,2,5.1 图的概念,3,图的概念,图是现实世界中对象相互关联的数学抽象：点表示对象，两点之间的线表示这两点之间的关系(二元关系). 说明: 1.不关心点所代表的具体对象; 2.不关心线的长短曲直; 3.只关心点与点之间是否有连线.,4,图的定义,5,图的例子,6,关于点与边的术语,(一条边的两个端点。),(有共同端点的两条边。),7,关于图的术语,8,单图与伪图,9,完全图,下面给出了完全图K3，K4和K5：,10,二分图,11,二分图的例子,下面是图G及其二分图：,V1:,V2 :,a1,a2,b1,c1,d1,b2,c2,d2,a1,b1,c1,d1,a2,b2,c

2、2,d2,G,G的二分图,12,补图,（顶点集相等）,（边集互补）,两个简单图互为补图的例子：,G,13,两种特殊的图,14,5.2图的同构(一),15,图的同构,图描述客观对象间的关系，几何形状不是重要的。 同一个图的图形不是唯一的，其差异可以是很大。 比如，下面的三个图在图形上是完全不相同的：,a,b,c,d,G,a,d,c,b,H,a,b,c,d,K,但是我们不难看出这三个图描述的是四个对象之间的相同关系，实质上是同一个图。 它们也就是同构的图。,16,图同构的定义,17,图同构的例子,u1,u5,u2,u3,u4,v1,v4,v3,v5,v2,e1,e2,e3,e4,e5,a1,a2,

3、a3,a4,a5,G：,H：,18,图的等价类,显然，同构关系是一个等价关系。 所以可以将所有的p阶图的集合按图的同构关系划分成等价类。 例如，3阶图的等价类有如下四种：,无标记图：在每个等价类中任选一个图，去掉顶点和边的名称，作为该类的代表。这种图成为无标记图。上面这四个图就是无标记图。,19,5.3顶点的度,20,顶点的度,21,图的几种顶点,度为奇数的点称为奇点； 度为偶数的点称为偶点； 度为1的点称为悬挂点； 度为0的点称为孤立点。,在一个图中：,22,正则图,23,顶点的度数之和是边数的两倍,即一个图的所有顶点的度数之和为偶数。,此定理很容易证明，因为在计算顶点的度时，每一条边都被计

4、算了两次，也只被计算了两次。,24,图的奇点个数必为偶数,此推论可以用来解决许多实际问题，如“握手问题”：任何一群人中，与奇数个人握过手的人必为偶数个。,推论5.3.1： 任何一个图的奇点个数必为偶数。,由定理5.3.1可得出如下的推论：,假设图中奇点个数为奇数，则它们的度数之和为奇数，偶点的度数之和当然是偶数，这样所有顶点的度数之和为奇数。与定理5.3.1矛盾。,25,5.4 子图及图的运算,26,子图,27,子图的例子,v1,G,v1,v4,v2,v3,e6,H2,28,几个约定,29,实例,v1,G,v1,v4,v2,v3,e6,H2,30,点导出子图,【取其两端点必取其边】,31,点导

5、出子图的例子,例如：,32,边导出子图,【有顶点必有边关联】,【点导出子图：取其两端点必取其边】,说白了，图G的边导出子图就是G的一些边和这些边的端点所构成的子图。,边导出子图中不会有孤立点，也不会是零图；但是点导出子图却可以含有孤立点，甚至是一个零图。,33,边导出子图的例子,34,关于导出子图,35,导出子图例子（1）,v1,G,v1,v4,v2,v3,e6,H2,36,导出子图例子（2）,v1,G,H1,v1,H2,37,点不相交边不重,显然互不相交的两个图必是边不重的，反之不然。,38,图的运算并,两个图的并是它们的顶点集、边集分别相并，关联函数各管各。,39,图的并运算举例,4,3,

6、2,1,a,b,c,d,e,f,1,2,3,5,a,h,k,e,g,b,G1,G2,G1 G2：,1,2,3,4,5,a,h,k,c,d,f,e,b,g,40,图的运算交,41,图的交运算举例,4,3,2,1,a,b,c,d,e,f,1,2,3,5,a,h,k,e,g,b,G1,G2,G1G2,1,2,3,a,e,b,42,图的运算差与对称差,43,图的差和对称差运算举例,4,3,2,1,a,b,c,d,e,f,1,2,3,5,a,h,k,e,g,b,G1,G2,G1G2=G1c,d,f,1,3,4,d,f,c,G2G1=G2g,h,k,2,5,3,g,h,k,1,2,3,5,4,f,d,c,

7、g,k,h,G1 G2,44,5.5通路与连通图,45,途径与链,46,通路,47,回路,不是途径 是途径，不是链 是链，不是通路 是(1,3)通路，不是回路 是回路,48,连通,49,连通分支,50,非连通图的补图必连通,51,二分图的充要条件,52,二分图的充要条件（续前）,u,P,Q,u1,P1,Q1,v,w,53,5.6 图的矩阵表示,54,关联矩阵,55,邻接矩阵,邻接矩阵表示图G中各顶点的邻接关系。 显然A(G)是个对称矩阵。 A(G)的对角线均为0当且仅当G中无环。 当G为简单图， A(G)为0-1矩阵。,56,关联矩阵和邻接矩阵的示例,对如下的图G，其M(G)和A(G)如右所示

8、。,v1,v4,v2,e1,e2,e3,e4,e5,M(G)=,e1 e2 e3 e4 e5 v1 2 1 1 1 0 v2 0 1 1 0 1 v3 0 0 0 0 0 v4 0 0 0 1 1,v3,A(G)=,v1 v2 v3 v4 v1 1 2 0 1 v2 2 0 0 1 v3 0 0 0 0 v4 1 1 0 0,57,关联矩阵、邻接矩阵和关系矩阵,58,邻接矩阵的应用,59,邻接矩阵的应用,60,用邻接矩阵计算顶点的度,61,5.7 应 用,62,赋权图,63,单源最短通路的长度,64,Dijkstra 算法的思想,Dijkstra 算法的思想是由近到远逐步计算，每次最近的顶点的

9、距离就是它的最短通路长度。然后再从这个最近者出发。即依据最近者修订到各顶点的距离，然后再选出新的最近者。如此走下去，直到所有顶点都走到。 我们只要对步数做归纳证明就可以证明每次最近者的通路长度一定是最短者：,1,v,(最近距离),l1,l,lk,因为l已是到v的最近者， 所以经过其它顶点再到达v的通路不可能更短。,65,Dijkstra 算法,Procedure Dijkstra; begin (1) S:=1; 初始化S (2) for i:= 2 to n do 初始化D (3) Di =C1, i ; Di为当前从源到顶点i的最短通路长度 (4) for i :=1 to n-1 do

10、begin (5) 从V-S中选取一个顶点w使得Dw最小； (6) 将w加入到S中；选出最近者 (7) 对vV-S do依据最近者重新修订Dv (8) Dv := min Dv , Dw+Cw ,v end end,66,Dijkstra 算法举例,迭代 S w D2 D3 D4 D5 初始 1 - 10 30 100 1 1,2 2 10 60 30 100 2 1,2,4 4 10 50 30 90 3 1,2,4,3 3 10 50 30 60 4 1,2,4,3,5 5 10 50 30 60,1,2,5,4,3,10,20,50,100,30,10,60,赋权图G,由数组Di可知：从

11、顶点1到顶点2、3、4、5的最短通路的长度分别为10、50、30和60。,67,对Dijkstra 算法做适当的修改(增加1个一维数组)便可求出最短通路。 (书上P56 和P57),如果还要求出源到各顶点的最短通路,可以设一个一维数组Pn。定义Pi是从源到i的最短通路上i的前一个顶点。初始时令Pi=1，i=2,3,n。每次执行完Dijkstra算法中的第（8）行之后，如果Dv=Dw+Cw,v,则说明当前源到v的最短特殊是通过w到达v的，此时置Pv=w,到算法结束时，就可以根据数组P找到源到v的最短通路上每个顶点的前一个顶点，从而得到从源到v的最短通路。,68,对于上例的图，我们有P2=1,P3

12、=4, P4=1,P5=3，如果要找出顶点1到3的最短通路，则根据P得到3的前一个顶点是4，而4的前一个顶点是1，因而从1到3的最短通路是1，4，3。 （完）,69,Dijkstra 算法的评价（）,Dijkstra 算法有两层循环，外层循环为n次，内层有两个循环：一个是选出最小的w(第5行)，另一个是修订Dv(第7、8行)。它们的次数都是n/2，所以内层循环的次数为n，因此其总运算次数为n2，即算法的时间复杂度为 O(n2)。 Dijkstra 算法能求出从某一顶点到其它各顶点的最短通路的长度，但是却并没有给出其最短通路。 对Dijkstra 算法做适当的修改便可求出最短通路。(书上P56

13、和P57),70,求所有顶点对之间的最短距离(不讲),Dijkstra 算法能求出从某个顶点到其它顶点的最短距离。 现在的问题是求所有顶点对之间的最短距离。 这个问题当然可以通过使用Dijkstra 算法逐个计算每个顶点来求的。 下面我们介绍一种更直接的方法：Floyd算法。,71,Foloyd算法的思想,将顶点集排序，按照顶点的顺序k，逐个计算每对顶点之间经由该顶点k的通路长度。 假定 A(k-1)i,j 的值是从i 到j只经过编号不大于k-1的顶点的最短通路长度。轮到第k个顶点时： A (k)i,j = min A(k-1)i,j , A(k-1)i,k + A(k-1)k,j ,i,k,

14、j,A(k-1)i,j,A(k-1)i,k,A(k-1)k,j,即原来的(不经过顶点k)通路和新的 (经过顶点k)通路中长度最小者。,显然，经过此轮后的A(k)i,j的值仍是从i 到j且不经过编号大于k的顶点的最短通路长度。对k进行归纳即可证明算法的正确性。,72,Foloyd算法描述,从k=1开始，按照顶点的编号逐个进行： 对每个顶点对(i, j) ，若从i经由k到达j的距离更近，则修订Ai，j = Ai, k + Ak, j 。 重复进行，直到k=n 时算法终止。此时Ai, j 就是从i 到j的最短通路长度。 如果要求出从i 到j的最短通路，可以设置二维数组P，当算法执行Ai,j = Ai

15、,k + Ak,j时，说明从i 到j的最短通路必经过点k，置Pi, j=k , 而Pi,j = 0表示当前从i 到j的最短通路就是图中的边(i, j) 。,73,Floyd算法的程序（1）,procedure Shortest; begin for i :=1 to n do for j :=1 to n do begin Ai,j:=Ci,j; Pi,j:= 0 end; for i :=1 to n do Ai,i:= 0; for k :=1 to n do for i :=1 to n do for j :=1 to n do If Ai,k + Ak,j Ai,j then begi

16、n Ai,j := Ai,k + Ak,j P i,j := k end end;Shortest,初始化,按顶点的编号进行迭代,对矩阵按行和列逐个元素修订距离,若经过顶点k的距离更短，则 修改距离， 并记下该顶点k。,计算顶点之间的最近距离,不难看出此程序的时间复杂度为O(n3)。,74,Floyd算法的程序（2）,这是一个递归过程，利用矩阵P i , j 计算i 到j的最短通路: procedure Path(i ,j: integer); var k: integer; begin k:= P i, j ; 取出从 i 到 j 的最短通路上的顶点k If k=0 then return;

17、 i 和 j 邻接，没有中间的顶点 Path(i ,k); 给出从 i 到 k 的最短通路 writeln(k); 输出顶点 k Path(k ,j) 给出从 k 到 j 的最短通路 end;Path,此程序也可不采用递归的方法来实现。请同学们自己设计它的非递归程序，并编程实现。,75,Foloyd算法举例,初始化：,A(0) =,P=,第一轮：,A(1) =,A(1)2,4:= A(0) 2,1+ A(0) 1,4 = 40 A(0) 2, 4,40,40,A(1)2,5:= A(0) 2,1+ A(0) 1,5 = 110 A(0) 2, 5,110,110,P 2,5 := 1 ;,P

18、2,4 := 1 ;,76,Foloyd算法举例,第二轮：,A(2) =,A(2)1,3=A(1) 1,2+A(1)2,3 = 60 A(1) 1,3,60,60,P 1,3:= 2;,第三轮：,A(3) =,A(3) 1,5=A(2)1,3+A(2)3,5 = 70 A(2) 1,5,70,70,P 1,5:= 3;,A(3) 2,5=A(2)2,3+A(2)3,5 = 60 A(2) 2,5,60,60,P 2,5:= 3;,A(3) 4,5=A(2)4,3+A(2)3,5 = 30 A(2) 4,5,30,30,P 4,5:= 3;,77,Foloyd算法举例,第四轮：,A(4) =,A(4) 1,3=A(3)1,4+A(3)4,3; = 50 A(3) 1,3,50,50,P1,3:= 4,A(4) 1,5=A(3)1,4+A(3)4,5 = 60 A(3) 1, 5,60,60,P1,5:= 4;,第五轮：,A(5) =,P