离散数学课件：5-3-1 图的基本概念（新）

1、复习思考题131. 画出以画出以(1,1,2)为度数列的两个非同构的为度数列的两个非同构的图图.2. 若若两个无向图的度数列相同，则这两个图两个无向图的度数列相同，则这两个图同构同构。( )3. 对对n阶非连通简单图阶非连通简单图G = G的的边数最多是边数最多是_； G的边数的边数最少是最少是_ 。4. 无向图无向图G的结点集的结点集V上上的连通关系的连通关系是偏序是偏序关关系系。( )5.对无向简单图对无向简单图G, e为为G中的中的桥桥当且仅当当且仅当e不不在在G的任何的任何圈圈中。中。( )复习思考题13判断下面两个图是否同构判断下面两个图是否同构: (1)度数列不同度数列不同不同构不

2、同构复习思考题13 判断下面两个图判断下面两个图是否同构是否同构: (2)入入( (出出) )度列不同度列不同不同构不同构复习思考题13判断判断下面两个图下面两个图是否同构是否同构: (3)度数列度数列相同相同不同构不同构(左边没有三角形左边没有三角形,右边有三角形右边有三角形)对无向简单图G，若eE(G)， 证明：e为G中的桥e不在G的任何圈中()必要性必要性 用反证法：用反证法：设桥设桥e=(u,v)在某圈上，在某圈上， 则删除则删除e后，后，u到到v仍有通路，即仍有通路，即G-e仍连仍连通通 这与这与e为为G中的桥矛盾；中的桥矛盾；uveuv对无向简单图G，若eE(G)， 证明：e为G中

3、的桥e不在G的任何圈中()必要性必要性 用反证法：用反证法：设桥设桥e=(u,v)在某圈上，在某圈上， 则删除则删除e后，后，u到到v仍有通路，即仍有通路，即G-e仍连仍连通通 这与这与e为为G中的桥矛盾；中的桥矛盾； ()充分性充分性 用反证法：用反证法：设设e不是桥，不是桥， 则则G-e仍连通，因而仍连通，因而e的端点的端点u到到v在在G-e中中有通路，此通路与有通路，此通路与e构成构成G中的一个圈，中的一个圈， 这与这与e不在任何圈中相矛盾。不在任何圈中相矛盾。uveuve第5章 图的基本概念 5.1 无向图及有向图5.2 通路、回路、图的连通性5.3 图的矩阵表示 5.4 最短路径及关

4、键路径无向图的关联矩阵n定义：定义：无向图无向图G=, nV=v1, v2, , vn, E=e1, e2, , em, n令令mij为为vi与与ej的关联次数的关联次数，称，称(mij)n m为为G的关的关联矩阵联矩阵，记为，记为M(G). 1110001110( )1001200000M Ge1 e2 e3 e4 e5V1V2V3v4无向图关联矩阵的性质1(2)( )(1,2,., )mijijmd vinniniimjijmjniijmvdmm111112)()3( (4) 平行边的列相同。平行边的列相同。1110001110( )1001200000M Ge1 e2 e3 e4 e5V

5、1V2V3v4(1) 每一列恰好有两个每一列恰好有两个1或一个或一个2(5) vi为孤立点当且仅当第为孤立点当且仅当第 i 行全为行全为0。有向图的关联矩阵n定义：定义： 设无环有向图设无环有向图D=, V=v1, v2, , vn, E=e1, e2, , em, 令令 则称则称(mij)n m为为D的关联矩阵的关联矩阵，记为，记为M(D). 的终点的终点为为，不关联不关联与与，的始点的始点为为jijijiijevevevm10,1M(D)=e1 e2 e3 e4 e5V1V2V3v411000101110000101110有向图关联矩阵的性质(1) 每一列恰好有一个每一列恰好有一个1和一个

6、和一个-1(2) 第第 i 行行 1 的个数等于的个数等于d+(vi), -1 的个数等于的个数等于d-(vi) (3) 1的总个数等于的总个数等于-1的总个数的总个数, 且都等于且都等于m(4) 平行边对应的列相同平行边对应的列相同M(D)=e1 e2 e3 e4 e5V1V2V3v411000101110000101110n定义定义: 设有向图设有向图D=,n V=v1, v2, , vn, E=e1, e2, , em, n令令 为为顶点顶点vi邻接邻接到到顶点顶点vj边的条数边的条数，称，称( )n n为为D的邻接矩阵的邻接矩阵, 记作记作A(D), 简记为简记为A. )1(ija)1

7、(ija有向图的邻接矩阵 A(D)=V1V2V3v4 v1 v2 v3 v41000201010011010有向图邻接矩阵的性质njiijnivda11211),.,()()()(nijijnjvda11212),.,()()()(的通路数1中长度为31Dmajiij,)()(的回路数1中长度为411Daniii)()(A(D)=V1V2V3v4 v1 v2 v3 v41000201010011010210003001()20102001A D D中的通路及回路数)(lija)(liia ninjlija11)( niliia1)(n定理定理 n设设A为为n阶有向图阶有向图D的邻接矩阵的邻接矩

8、阵, 则则Al(l 1)中元素中元素 为为D中中vi到到vj长度为长度为 l 的的通路数通路数， 为为vi到自身长度为到自身长度为 l 的的回路数回路数， 为为D中长度为中长度为 l 的的通路总数通路总数， 为为D中长度为中长度为 l 的的回路总数回路总数. 10002010()10011010A D通路和回路通路和回路可以可以是初级是初级的、简单的、简单的、的、复杂复杂的的D中的通路及回路数说明：说明：An=An-1 A (矩阵代数乘法矩阵代数乘法) ninjlijb11)( niliib1)(n推论推论 设设Bl=A+A2+Al(l 1), 则则Bl中元素中元素 为为D中长度中长度 l 的

9、的通路数通路数， 为为D中长度中长度 l 的的回路数回路数.21nikijjkjaa aA(D)=V1V2V3v4 v1 v2 v3 v41000201010011010210003001()20102001A DD中的通路及回路数举例1例例 有向图有向图D如图所示如图所示, 求求A, A2, A3, A4, 并回答诸并回答诸问题：问题：(1) D中长度为中长度为1, 2, 3, 4的通路各有多少条？其中的通路各有多少条？其中回路分别为多少条？回路分别为多少条？(2) D中长度小于或等于中长度小于或等于4的通路为多少条？其中的通路为多少条？其中有多少条回路？有多少条回路？ D中的通路及回路数举

10、例1(1) D中长度为中长度为1, 2, 3, 4的通路各有多少条？的通路各有多少条？即要分别求即要分别求A, A2, A3, A4,其矩阵中数之和即为结果其矩阵中数之和即为结果D中的通路及回路数举例1(1) D中长度为中长度为1, 2, 3, 4的通路各有多少条？的通路各有多少条？即要分别求即要分别求A, A2, A3, A4,其矩阵中数之和即为结果其矩阵中数之和即为结果D中的通路及回路数举例1(1) D中长度为中长度为1, 2, 3, 4的通路各有多少条？的通路各有多少条？即要分别求即要分别求A, A2, A3, A4,其矩阵中数之和即为结果其矩阵中数之和即为结果D中的通路及回路数举例1(

11、1) D中长度为中长度为1, 2, 3, 4的通路各有多少条？的通路各有多少条？即要分别求即要分别求A, A2, A3, A4,其矩阵中数之和即为结果其矩阵中数之和即为结果D中的通路及回路数举例1 1004010410050001010310030104000110020102100300010101100101020001432AAAA合计合计 50 818 1211 3314 1417 3 长度 通路 回路D中的通路及回路数举例2n 三枚钱币处于反、正、反面，每次只许翻动一枚钱币，问连续翻动三次后，能否出现全正面或全反面?n 解解: 引入三元组(q0,q1,q2)来描述 状态：正面为0，反

12、面为1，问题：是否可以翻动3次后， 从Q5Q0或Q5Q7？转化：状态转换图中是否存在从Q5Q0或 Q5Q7的长度为3的通路。(q0,q1,q2)Q00，0，0Q10，0，1Q20，1，0Q30，1，1Q41，0，0Q51，0，1Q61，1，0Q71，1，1D中的通路及回路数举例2 用邻接矩阵表示图：0110100010010100100100100110000110000110010010010010100100010110AQ0 Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q0 Q1 Q2 Q3 Q4 Q5 Q6 Q7 状态转换图Q5(101)Q4(100)Q7(111)Q1(001)Q6(1

13、10)Q0(000)Q2(010)Q3(011)D中的通路及回路数举例2求A的3次幂 (Q5,Q0)= 0, (Q5,Q7)= 7, 所以，连续翻动钱币三次，不能出现全正面，可以出现全反面，有7种翻动方法可以出现全反面.30770700670070760700706700770600770060770076070070670700760070770A即即Q5Q0没有没有长度为长度为3的通路的通路Q5Q7有有7条长度为条长度为3的通路的通路Q0 Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q0 Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q5(101)Q4(100)Q7(111)Q1(001)Q6(

14、110)Q0(000)Q2(010)Q3(011)有向图的可达矩阵 n定义定义 设设D=为有向图为有向图, V=v1, v2, , vn, 令令 称称(pij)n n为为D的可达矩阵的可达矩阵, 记作记作P(D), 简记为简记为P. n性质性质:n P(D)主对角线上的元素全为主对角线上的元素全为1. n D强连通当且仅当强连通当且仅当P(D)的元素全为的元素全为1.否则0可达1,jiijvvp 1101110111110001P5.4 最短路径、关键路径最短路径、关键路径n带权图带权图n最短路径与最短路径与Dijkstra标号法标号法n项目网络图与关键路径项目网络图与关键路径5.4 最短路径

15、及关键路径n 带带权图权图G=, n其中其中w:ER. e E, w(e)称作称作e的的权权. ne=(vi,vj), 记记w(e)=wij . 若若vi,vj不相邻不相邻, 记记wij = . n 通路通路L的权的权:L的所有边的权之和的所有边的权之和, 记作记作w(L).n u和和v之间的之间的最短路径最短路径:u和和v之间权最小的通路之间权最小的通路.162417235v0v3v1v4v2v5例例: L1=v0v1v3v5, w(L1)=10, L3=v0v2v4v5, w(L3)=11 L2=v0v1v4v5, w(L2)=12, 求最短路径的算法标号法n 设G=为n阶简单带权图，wi

16、j 0， n vi, vj V, 若若vi, vj不相邻，则不相邻，则wij = n求求v0到其余顶点的到其余顶点的最短路径，先给出符号定义：最短路径，先给出符号定义：顶点顶点vi的的标号：标号：( li, pi ) nli v0到到vi的距离，的距离，npi v0到到vi的最短路径上的最短路径上vi的前一个顶点，的前一个顶点，n临时标号，永久标号临时标号，永久标号n设设P =v|v已获得永久标号已获得永久标号n设设T=V-P为仍为临时标号的顶点集。为仍为临时标号的顶点集。162417235v0v3v1v4v2v5求最短路径的算法标号法设带权图设带权图G=, 其中其中 e E, w(e) 0.

17、设设V=v1,v2,vn, 求求v1到其余各顶点的最短路径到其余各顶点的最短路径1. 令令 l10, p1 , lj+ , pj , j=2,3,n, P=v1, T=V-v1, k1, t1. / 表示空表示空2. 对对 vj T且且(vk,vj) E 令令 若若l = lk+wkj, 则修改标号则修改标号ljl, pjvk.3. 求求li=minlj| vj Tt. /将将vi改为永久标号改为永久标号 令令PP vi, TT-vi, ki.4. 令令tt+1, 若若tn, 则转则转2.计算结束后，利用计算结束后，利用pj通过回溯可得到通过回溯可得到v1 到到vi的最短路径的最短路径Dijk

18、stra标号法实例例例 求求v0到到v5的最短的最短路径路径 t v0 v1 v2 v3 v4 v5 1 (0, )* (+ , ) (+ , ) (+ , ) (+ , ) (+ , ) 2 (1,v0)* (4,v0) (+ , ) (+ , ) (+ , ) 3 (3,v1)* (8,v1) (6,v1) (+ , ) 4 (8,v1) (4,v2)* (+ , )5 (7,v4)* (10,v4) 6 (9,v3)*v0到到v5的最短路径的最短路径: v0v1v2v4v3v5 , d(v0,v5)=9(0, )* (+ , ) (+ , ) (+ , ) (+ , ) (+ , )(1

19、,v0)* (4,v0) (+ , ) (+ , ) (+ , )(3,v1)* (8,v1) (6,v1) (+ , )(8,v1) (4,v2)* (+ , )(7,v4)* (10,v4) (9,v3)*算法特点： 按长度递增的次序生成从按长度递增的次序生成从v0到到其它顶点的最短路径，其它顶点的最短路径， 则当前正在生成的最短路径上除终点则当前正在生成的最短路径上除终点外，其余顶点外，其余顶点的最短路径均已生成。的最短路径均已生成。项目网络图n 项目网络图项目网络图: 表示表示项目项目的活动之间的活动之间前后顺序一致前后顺序一致的的带权有向图带权有向图.n边边表示活动表示活动, n边的

20、权边的权是活动的完成时间是活动的完成时间,n顶顶点点表表示事项示事项(项目活动的开始和结束项目活动的开始和结束).n 要求要求: (1) 有一个有一个始点始点(入度为入度为0)和一个和一个终点终点(出度为出度为0). (2) 任意两点之间只能有一条边任意两点之间只能有一条边. (3) 没有回路没有回路. (4) 每一条边每一条边始点始点的编号小于的编号小于终点终点的编号的编号.ABC引入虚活动引入虚活动ABC项目网络图实例41235678ABCDEFGHIJKL123434424611活动ABC D EFGHIJKL紧前活动 A A A,B A,B A,B C,H D,F E,IG,K时间(天

21、)1234 34424611 边边 活动活动, 权权 活动活动的完成的完成时间时间顶点顶点事项事项关键路径问题n关键路径关键路径 项目网络图中从始点到终点的最长路径。n 关键活动关键活动 关键路径上的活动。关键路径上的活动。 设设D=, V=1,2,n, 1是始点是始点, n是终点是终点.41235678ABCDEFGHIJKL123434424611关键路径问题n 事项事项i 的最早完成时间的最早完成时间: i最早可能开始的最早可能开始的时间时间，即即从始点到从始点到 i 的最长路径的长度的最长路径的长度. ES(1)=0 ES(i)=maxES(j)+wji| E, i=2,3,n n 事

22、项事项i 的最晚完成时间的最晚完成时间: 在不影响项目工期的条件下在不影响项目工期的条件下, ,事项事项 i 最晚必须完成的时间最晚必须完成的时间 LF(i)=minLF(j)-wij| E, (i=n-1,n-2,1) LF(n)=ES(n)41235678ABCDEFGHIJKL123434424611设设D=, V=1,2,n, 1是始点是始点, n是终点是终点.关键路径问题n 活动活动的最早开始时间的最早开始时间ES(i,j)n 活动活动的最早完成时间的最早完成时间EF(i,j)n 活动活动的最晚开始的最晚开始时间时间LS(i,j): 在不影响项目工期的条件在不影响项目工期的条件下下,

23、 最晚必须开始的时间最晚必须开始的时间.n 活动活动的最晚完成的最晚完成时间时间LF(i,j): 在在不影响项目工期的不影响项目工期的条件条件下下, 最晚必须完成的时间最晚必须完成的时间. 显然显然, ES(i,j) = ES(i), EF(i,j) = ES(i)+wij= ES(j) LF(i,j) = LF(j), LS(i,j) = LF(j)-wij, n 活动活动的缓冲时间的缓冲时间SL(i,j): SL(i,j) = LS(i,j) - ES(i,j) = LF(i,j) - EF(i,j) n 事项事项 j 的的缓冲时间缓冲时间SL(j) = LF(j) - ES(j) 41235678ABCDEFGHIJKL123434424611关键路径问题实例n 事项事项i 的的最早开始时间最早开始时间: i 最早可能开始的时间最早可能开始的时间,即从始点