离散数学图的基本概念

1、1第1页，共48页，2022年，5月20日，11点10分，星期五通路与回路 定义 给定图G=（无向或有向的），设G中顶点与边的交替序列=v0e1v1e2elvl： 若i(1il), vi1 和 vi是ei的端点(对于有向图, 要求vi1是始点, vi是终点), 则称为通路, v0是通路的起点, vl是通路的终点, l为通路的长度. 又若v0=vl，则称为回路.理解：通路或回路是点与边的交替序列，边的端点恰好是前后的两个点长度边数2第2页，共48页，2022年，5月20日，11点10分，星期五若通路(回路)中所有顶点(对于回路, 除v0=vl)各异，则称为初级通路(初级回路).初级通路又称作路径

2、, 初级回路又称作圈.路上各点不重复若通路(回路)中所有边各异, 则称为简单通路(简单回路), 否则称为复杂通路(复杂回路).路上各边不重复3第3页，共48页，2022年，5月20日，11点10分，星期五通路与回路(续)说明:在无向图中，环是长度为1的圈, 两条平行边构成长度为2的圈.无向简单图中, 所有圈的长度3在有向图中，环是长度为1的圈, 两条方向相反边构成长度为2的圈.在有向简单图中, 所有圈的长度2. 4第4页，共48页，2022年，5月20日，11点10分，星期五通路与回路(续) 定理 在n阶图G中，若从顶点vi到vj（vivj）存在通路，则从vi到vj存在长度小于等于n1的通路.

3、推论 在n阶图G中，若从顶点vi到vj（vivj）存在通路，则从vi到vj存在长度小于等于n1的初级通路.定理 在一个n阶图G中，若存在vi到自身的回路，则一定存在vi到自身长度小于等于n的回路.推论 在一个n阶图G中，若存在vi到自身的简单回路，则一定存在长度小于等于n的初级回路. 5第5页，共48页，2022年，5月20日，11点10分，星期五无向图的连通性 设无向图G=,u与v连通: u与v之间有通路.规定u与自身总连通.连通关系：R=| u,v V且uv是V上的等价关系连通图: 平凡图, 或者任意两点都连通的图连通分支: V关于R的等价类的导出子图设V/R=V1,V2,Vk, GV1,

4、 GV2, ,GVk是G的连通分支, 连通分支个数记作p(G)=k.G是连通图 p(G)=16第6页，共48页，2022年，5月20日，11点10分，星期五短程线与距离u与v之间的短程线: u与v之间长度最短的通路u与v之间的距离d(u,v): u与v之间短程线的长度若u与v不连通, 规定d(u,v)=.性质： d(u,v)0, 且d(u,v)=0 u=v d(u,v)=d(v,u)（对称性） d(u,v)+d(v,w)d(u,w) （三角不等式)7第7页，共48页，2022年，5月20日，11点10分，星期五点割集（v点；V点集；e边；E变集） 记 Gv: 从G中删除v及关联的边 GV: 从

5、G中删除V中所有的顶点及关联的边Ge : 从G中删除eGE: 从G中删除E中所有边定义 设无向图G=, 如果存在顶点子集VV, 使p(GV)p(G)，而且删除V的任何真子集V后（ VV），p(GV)=p(G), 则称V为G的点割集. 若v为点割集, 则称v为割点.理解：删除点后连通分支数可能增加，会减少吗？8第8页，共48页，2022年，5月20日，11点10分，星期五点割集(续)例 v1,v4, v6是点割集, v6是割点. v2,v5是点割集吗？ 9第9页，共48页，2022年，5月20日，11点10分，星期五边割集定义 设无向图G=, EE, 若p(GE)p(G)且EE, p(GE)=p

6、(G), 则称E为G的边割集. 若e为边割集, 则称e为割边或桥.下图中，e1,e2，e1,e3,e5,e6，e8等是边割集，e8是桥，e7,e9,e5,e6是边割集吗？10第10页，共48页，2022年，5月20日，11点10分，星期五几点说明：Kn无点割集（完全图）n阶零图既无点割集，也无边割集.若G连通，E为边割集，则p(GE)=2若G连通，V为点割集，则p(GV)211第11页，共48页，2022年，5月20日，11点10分，星期五有向图的连通性 设有向图D=u可达v: u到v有通路. 规定u到自身总是可达的.可达具有自反性和传递性D弱连通(也称连通): 基图为无向连通图有向边改为无向

7、边后是连通图D单向连通: u,vV，u可达v 或v可达u D强连通: u,vV，u与v相互可达强连通单向连通弱连通 12第12页，共48页，2022年，5月20日，11点10分，星期五有向图的连通性(续) (1)(2)(3)例 下图(1)强连通, (2)单连通, (3) 弱连通每个顶点有进有出部分顶点有进有出13第13页，共48页，2022年，5月20日，11点10分，星期五有向图的短程线与距离u到v的短程线: u到v长度最短的通路 (u可达v)u与v之间的距离d: u到v的短程线的长度若u不可达v, 规定d=.性质： d0, 且d=0 u=v d+d d 注意: 没有对称性14第14页，共4

8、8页，2022年，5月20日，11点10分，星期五7.3 图的矩阵表示 无向图的关联矩阵有向图的关联矩阵有向图的邻接矩阵有向图的可达矩阵 15第15页，共48页，2022年，5月20日，11点10分，星期五无向图的关联矩阵定义 设无向图G=, V=v1, v2, , vn, E=e1, e2, , em, 令mij为vi与ej的关联次数，称(mij)nm为G的关联矩阵，记为M(G). 性质16第16页，共48页，2022年，5月20日，11点10分，星期五v1v2v4v3e1e2e3e4e5关联次数为可能取值为0，1，217第17页，共48页，2022年，5月20日，11点10分，星期五无向图

9、的相邻矩阵v1v2v4v3e1e2e3e4e5(1)相邻矩阵是对称矩阵。(2)对角元素aii0,表示结点vi处有环。(3)如aij 1,表示vi与vj间有平行边。aij +2 18第18页，共48页，2022年，5月20日，11点10分，星期五V1V2V3V4V5 V1 V2 V3 V4 V519第19页，共48页，2022年，5月20日，11点10分，星期五有向图的关联矩阵定义 设无环有向图D=, V=v1, v2, , vn, E=e1, e2, , em, 令 则称(mij)nm为D的关联矩阵，记为M(D).20第20页，共48页，2022年，5月20日，11点10分，星期五v4v1v2

10、v3e1e2e3e4e5性质: (4) 平行边对应的列相同21第21页，共48页，2022年，5月20日，11点10分，星期五定义 设有向图D=, V=v1, v2, , vn, E=e1, e2, , em, 令 为顶点vi邻接到顶点vj边的条数，称( )nn为D的邻接矩阵, 记作A(D), 简记为A. 性质有向图的邻接矩阵 22第22页，共48页，2022年，5月20日，11点10分，星期五v2v1v4v323第23页，共48页，2022年，5月20日，11点10分，星期五D中的通路及回路数定理 设A为n阶有向图D的邻接矩阵, 则Al(l1)中元素 为D中vi到vj长度为 l 的通路数，

11、为vi到自身长度为 l 的回路数， 为D中长度为 l 的通路总数， 为D中长度为 l 的回路总数. 24第24页，共48页，2022年，5月20日，11点10分，星期五D中的通路及回路数(续)例 有向图D如图所示, 求A, A2, A3, A4, 并回答问题：(1) D中长度为1, 2, 3, 4的通路各有多 少条？其中回路分别为多少条？(2) D中长度小于或等于4的通路为多 少条？其中有多少条回路？ 推论 设Bl=A+A2+Al(l1), 则Bl中元素 为D中长度小于或等于l 的通路数， 为D中长度小于或等于l 的回路数.25第25页，共48页，2022年，5月20日，11点10分，星期五例

12、(续) 长度 通路 回路 合计 50 818 1211 3314 1417 326第26页，共48页，2022年，5月20日，11点10分，星期五有向图的可达矩阵 定义 设D=为有向图, V=v1, v2, , vn, 令 称(pij)nn为D的可达矩阵, 记作P(D), 简记为P. 性质: P(D)主对角线上的元素全为1. D强连通当且仅当P(D)的元素全为1.27第27页，共48页，2022年，5月20日，11点10分，星期五有向图的可达矩阵(续)例 右图所示的有向图D的可达矩阵为28第28页，共48页，2022年，5月20日，11点10分，星期五如何求有向图的可达矩阵设D=为有向图，|V

13、|=n, A为D的邻接矩阵；先求R（rij）A+A2+.+An再求可达矩阵P（pij）29第29页，共48页，2022年，5月20日，11点10分，星期五7.4 最短路径及关键路径对于有向图或无向图G的每条边，附加一个实数w(e)，则称w(e)为边e上的权.G连同附加在各边上的实数，称为带权图.设带权图G=,G中每条边的权都大于等于0.u,v为G中任意两个顶点，从u到v的所有通路中带权最小的通路称为u到v的最短路径.求给定两个顶点之间的最短路径，称为最短路径问题.30第30页，共48页，2022年，5月20日，11点10分，星期五算法：Dijkstra(标号法)31第31页，共48页，2022

14、年，5月20日，11点10分，星期五v2v0v1v3v4v5141762253例：求图中v0与v5的最短路径32第32页，共48页，2022年，5月20日，11点10分，星期五 vikv0v1v2v3v4v50 0 141 138623 8437 4104 7959013749v0v1v2v4v333第33页，共48页，2022年，5月20日，11点10分，星期五2.关键路径问题PERT图 设D=是n阶有向带权图D是简单图D中无环路有一个顶点出度为0，称为发点；有一个顶点入度为0，称为收点记边的权为wij,它常常表示时间34第34页，共48页，2022年，5月20日，11点10分，星期五Per

15、t图的应用用Pert中有向边表示工序，边上权表示完成工序的时间；用pert图中结点vi表示某个事项，表示某些工序的完工，同时表示某些工序可以开工。习惯上所有的有向边均从左向右。PertProgram Evaluation and Review Technic，计划评审技术35第35页，共48页，2022年，5月20日，11点10分，星期五关键路径从始点到终点的一条最长路径（发点到收点的一条最长路径 ）通过求各点的最早完成时间来求关键路径最早完成时间：自发点v1开始，沿最长路径（按权计算）到达vi所需时间，称为vi的最早完成时间，记为TE（vi） ，i=1,2,n。TE(vi)表示在前面所有工序

16、均没有耽误的情况下，该事项最早可能完成的时间，此时前面的工序均必须完成。也是后续工程最早开始的时间。36第36页，共48页，2022年，5月20日，11点10分，星期五这样从始点出发，TE(v0)0，一直计算到收点 vn，TE(vn)就是工程的最早完工时间。37第37页，共48页，2022年，5月20日，11点10分，星期五1234657824423326324026671315节点的最早完工时间38第38页，共48页，2022年，5月20日，11点10分，星期五2事项的最晚完成时间 TL(vi)：在保证收点vn的最早完成时间不增加的条件下，该事项vi最晚必须完成的时间，称为该点vi最晚完成时

17、间，记为TL(vi)。因为有些工序不在关键路上,这些工序有个缓冲时间,稍迟一些时间动工，不会导致整个工程的完工时间，但这也有个限度，TL(vi)就是不耽误整个工程的最早完工条件下，该工序最迟的开工时间，过了这时间开工将影响整个工程。39第39页，共48页，2022年，5月20日，11点10分，星期五其算法是从收点开始向后计算：因v0和vn均在关键路上,TE（vn）=TL（vn），TE（v0）=TL（v0）= 040第40页，共48页，2022年，5月20日，11点10分，星期五12346578244233263240510971315节点的最迟完工时间41第41页，共48页，2022年，5月2

18、0日，11点10分，星期五缓冲时间该事项在不影响整个工程的前提下，可以延滞的时间。TS(vi)TL(vi)TE(vi)42第42页，共48页，2022年，5月20日，11点10分，星期五关键路径从发点v0出发到收点vn的一条路径，这条路上任何工序的延滞必导致整个工程的延滞。关键路是整个工程计划的主要矛盾。关键路至少一条，也能是不止一条 ，在关键路上TS（vi）=043第43页，共48页，2022年，5月20日，11点10分，星期五节点12345678TE(vi)0426671315TL(vi)04410971315TS(vi)00243000其关键路径是v1, v2, v5, v7, v844第44页，共48页，2022年，5月20日，11点10分，星期五v2v7v1v8v5v4v3v612023441344161. 最早完成时间：45第45页，共48页，2022年，5月20日，11点10分，星期五v2v7v1v8v5v4v3v612023441