第7章图论离散数学离散数学第四版课件.ppt

1、第七章第七章 图的基本概念图的基本概念1 无向图及有向图无向图及有向图2 通路、回路、图的连通性通路、回路、图的连通性3 图的矩阵表示图的矩阵表示4 最短路径及关键路径最短路径及关键路径1/3/20231图图(Graph)(Graph)：可直观地表示离散对象之间的相互关系，可直观地表示离散对象之间的相互关系，研究它们的共性和特性，以便解决具体问题。研究它们的共性和特性，以便解决具体问题。图是一类相当广泛的实际问题的数学模型，图是一类相当广泛的实际问题的数学模型，有着极其丰富的内容，是数据结构等课程的先有着极其丰富的内容，是数据结构等课程的先修内容。学习时应掌握好图论的基本概念、基修内容。学习时

2、应掌握好图论的基本概念、基本方法、基本算法，善于把实际问题抽象为图本方法、基本算法，善于把实际问题抽象为图论的问题，然后用图论的方法解决问题。论的问题，然后用图论的方法解决问题。1/3/202321 无向图及有向图无向图及有向图v 本节介绍图的一些最常用的概念本节介绍图的一些最常用的概念,主要有：主要有：无向图，有向图，边，顶点无向图，有向图，边，顶点(或结点，点或结点，点)，弧弧(或有向边或有向边)，顶点集，边集，顶点集，边集，n n阶图，有限阶图，有限图，关联，多重图，简单图，完全图，母图图，关联，多重图，简单图，完全图，母图,子图子图,生成子图，导出子图，补图，图的同构，生成子图，导出子

3、图，补图，图的同构，入度，出度，度，孤立点等。入度，出度，度，孤立点等。主要定理：握手定理。主要定理：握手定理。1/3/20233定义定义 图图 V是一个非空有限集，是一个非空有限集，E是是V上的一个二元上的一个二元关系，有序对关系，有序对称为称为有向图有向图(Directed Graph)。可记为。可记为D.若将若将E中的有序对看成是无序的（即将中的有序对看成是无序的（即将e=看成看成e=a,b或或(a,b)），则称），则称为为无向图无向图(Undirected Graph)。有向图和无向图。有向图和无向图统称为统称为图图(Graph)，记为，记为G。G=1/3/20234定义定义 顶点顶点

4、 中的元素称为中的元素称为顶点顶点，用带标记的点表示，用带标记的点表示，也称为也称为结点结点(Vertices)。定义定义 边边 在有向图在有向图D中，若中，若e=E，e称为称为D的的有向边有向边(directed edge)。用由。用由a到到b带箭头的线带箭头的线把把a和和b连起来；连起来；在无向图在无向图G中，若中，若e=(a,b)E，e称为称为G的的无向边无向边(undirected edge)。a,b间用连线连结。间用连线连结。有向边和无向边统称为有向边和无向边统称为G的的边边(edge)。1/3/20235定义定义 图的分类图的分类 对图对图G=，若允许，若允许E是一个多重集合，是一

5、个多重集合，则称图则称图G为为多重图多重图(Multigraph)。其相同的元素。其相同的元素称为称为平行边平行边，平行边的条数称为，平行边的条数称为重数重数。无环的非多重图称为无环的非多重图称为简单图简单图(Simple Graph)。1/3/20236定义定义 相邻和关联相邻和关联 在无向图在无向图G中，若中，若e=(a,b)E，则称，则称a与与b彼此相邻彼此相邻(adjacent)，或边，或边e关联关联(incident)或或联结联结(connect)a,b。a,b称为边称为边e的的端点端点或或结束顶点结束顶点(endpoint)。在有向图在有向图D中，若中，若e=E，即箭头，即箭头由由

6、a到到b，称，称a邻接到邻接到b，或，或a关联关联或或联结联结b。a称为称为e的的始点始点(initial vertex)，b称为称为e的的终点终点(terminal/end vertex)。1/3/20237定义定义 孤立点孤立点 若若aV，a不与其他顶点相邻，称不与其他顶点相邻，称a为为孤立孤立点点(isolated vertex)。定义定义 顶点的度顶点的度 在无向图在无向图G中，与中，与a相邻的顶点的数目称为相邻的顶点的数目称为a的的度度(degree)。记为。记为deg(a)或或d(a)。在有向图在有向图D中，以中，以a为终点的边的条数称为为终点的边的条数称为a的的入度入度(in-d

7、egree)。记为。记为deg(a)或或d(a)。以。以a为为始点的边的条数称为始点的边的条数称为a的的出度出度(out-degree)。记。记为为deg+(a)或或d+(a)。1/3/20238定理定理1(握手定理握手定理Handshaking)设无向图设无向图G=有有n个顶点，个顶点，m条边，则条边，则G中所有中所有顶点的度之和等于顶点的度之和等于m的两倍。即的两倍。即证明思路：利用数学归纳法。证明思路：利用数学归纳法。定理定理2 无向图中度为奇数的顶点个数恰有无向图中度为奇数的顶点个数恰有偶数个。偶数个。证明思路：将图中顶点的度分类，再利用定理证明思路：将图中顶点的度分类，再利用定理1。

8、n1iim2vd.)(1/3/20239定理定理3 设有向图设有向图D=有有n个顶点，个顶点，m条边，则条边，则G中所有顶点的入度之和等于中所有顶点的入度之和等于所有顶点的出度之和，也等于所有顶点的出度之和，也等于m。即：即：证明思路：利用数学归纳法。证明思路：利用数学归纳法。n1in1iiimvdvd.)()(1/3/202310一些特殊的简单图：一些特殊的简单图：(1)无向完全图无向完全图Kn(Complete Graphs)(2)有向完全图有向完全图 (3)零图零图：E=.(4)平凡图平凡图：E=且且|V|=1.(5)正则图正则图：若图：若图G中每个顶点中每个顶点的度均为的度均为n，称此

9、图，称此图G是是n-正则图正则图(n-regular graph)。1/3/202311完全图完全图(n=1,2,3,4,5)K1 K2 K3 K5 K4 1/3/202312定理定理4 设无向完全图设无向完全图G有有n个顶点，个顶点，则则G有有n(n-1)/2条边。条边。证明：证明：每一顶点都与其余的每一顶点都与其余的n-1个顶点相个顶点相邻，即每一顶点的度为邻，即每一顶点的度为n-1，共有，共有n个顶个顶点，则图点，则图G的度为的度为n(n-1)，由握手定理，由握手定理，得边数得边数m=n(n-1)/2.1/3/202313 正则图（各顶点的度相同）正则图（各顶点的度相同）3-正则图正则图

10、 3-正则图正则图1/3/202314定义定义 子图子图 设设G=，G=是两个图，是两个图，若若V V，且，且E E，则称，则称G为为G的的子图子图(subgraph)。注：注：当当V=V时，称时，称G为为G的的生成子图生成子图。当当E E，或，或V V时，称时，称G为为G的的真真子图子图。1/3/202315定义定义 补图补图 设设G=是是n阶无向简单图，以阶无向简单图，以V为顶为顶点集，以所有能使点集，以所有能使G成为完全图成为完全图Kn的添加边的添加边组成的集合为边集的图，称为组成的集合为边集的图，称为G相对于完全相对于完全图图Kn的补图，简称的补图，简称G的的补图补图，记为，记为 。G

11、图图G与其补图与其补图G具有相同的顶点集，其边集具有相同的顶点集，其边集不相交，构成相应完全图边集的划分。不相交，构成相应完全图边集的划分。1/3/202316a e d c b e d c b a 图图 A图图 B d b a e c e d c b 图图 C图图 D a e d c b d b 图图 E图图 F1/3/202317图是一个无向完全图图是一个无向完全图图，均是的子图图，均是的子图图的顶点是孤立顶点图的顶点是孤立顶点图的边图的边(，)是孤立边是孤立边图是图的子图图是图的子图图是图的补图图是图的补图1/3/202318定义定义 图的同构图的同构 图图 G1，G2，如果，如果能建立

12、能建立V1与与V2间的一一对应，在此对应下，间的一一对应，在此对应下，E1与与 E2中的边也一一对应，对有向图还保中的边也一一对应，对有向图还保持关联方向的对应，则称图持关联方向的对应，则称图 G1与与 G2同构，同构，记作记作 G1 G2。1/3/202319a d c b 无无 向向 图图 b(b)a(a)c(c)d(d)例：例：1/3/202320a c d e 无无 向向 图图 b 3(c)4(d)5(e)2(b)1(a)例：例：1/3/202321a c d e 无无 向向 图图 b f g h i j 例：例：1(a)3(c)4(h)6(e)2(b)5(f)8(g)10(i)9(d

13、)7(j)1/3/202322有向图有向图例：例：abcde2(a)1(b)3(d)4(c)5(e)1/3/202323例：例：(1)画出画出4个顶点个顶点3条边的所有可能非同构的条边的所有可能非同构的无向简单图。无向简单图。(2)画出画出3个顶点个顶点2条边的所有可能非同构的条边的所有可能非同构的有向简单图。有向简单图。(1)(2)1/3/2023242 通路、回路、图的连通性通路、回路、图的连通性连通性连通性(Connectivity)定义定义 通路通路(path)给定图给定图G=，设图，设图G中顶点和边的交替中顶点和边的交替序列为序列为T=v0e1v1e2ekvk，若，若T满足如下条件：

14、满足如下条件：vi-1和和vi是是ei的端点的端点(当当G为有向图时，为有向图时，vi-1是是ei的始点，的始点，vi是是ei的终点的终点)，i=1,2,k，则称，则称T为顶点为顶点v0到到vk的的通路通路。此通路的长度为。此通路的长度为k。也可以用。也可以用v0,v1,vk表示通路，表示通路，v0为始点，为始点，vk为终点。为终点。当当v0=vk时，该通路称为时，该通路称为回路回路(circuit)。1/3/202325“巧渡河巧渡河”问题问题问题：人、狼、羊、菜用一条只能同时载两位问题：人、狼、羊、菜用一条只能同时载两位的小船渡河，的小船渡河，“狼羊狼羊”、“羊菜羊菜”不能在无人不能在无人

15、在场时共处，当然只有人能架船。在场时共处，当然只有人能架船。图模型：顶点表示图模型：顶点表示“原岸的状态原岸的状态”，两点之间，两点之间有边当且仅当一次合理的渡河有边当且仅当一次合理的渡河“操作操作”能够实能够实现该状态的转变。现该状态的转变。起始状态是起始状态是“人狼羊菜人狼羊菜”，结束状态是，结束状态是“空空”。问题的解：找到一条从起始状态到结束状态的问题的解：找到一条从起始状态到结束状态的尽可能短的通路。尽可能短的通路。1/3/202326“巧渡河巧渡河”问题的解问题的解注意：在注意：在“人狼羊菜人狼羊菜”的的16种组合中允种组合中允许出现的只有许出现的只有10种。种。空空(成功成功)人

16、羊狼菜人羊狼菜 人狼菜人狼菜 人羊狼人羊狼 人羊菜人羊菜 狼菜狼菜 狼狼 菜菜 人羊人羊 羊羊 1/3/202327定义定义 简单通路简单通路(Simple Path)若通路中所有边互不相同，称此道路为若通路中所有边互不相同，称此道路为简简单通路单通路。若回路中的所有边互不相同，称为。若回路中的所有边互不相同，称为简简单回路单回路(Simple Circuit)。定义定义 基本通路基本通路(Element Path)一条通路中，除了始点和终点可以相同，其一条通路中，除了始点和终点可以相同，其余顶点均互不相同，称此通路为余顶点均互不相同，称此通路为基本通路基本通路(初级初级通路通路)。当其是回路

17、时，称为。当其是回路时，称为基本回路基本回路(Element Circuit初级回路初级回路或或圈圈)。1/3/202328e3 e5 e2 e1 d c b a e4 e5,e1,e2,e3,e4是简单通路，不是基本通路，是简单通路，不是基本通路，因为因为c,a,b,c,d,b中中b,c均出现了两次。但均出现了两次。但c,d,b,c是基本通路，也是基本回路。是基本通路，也是基本回路。1/3/202329定理定理 在一个在一个n阶图中，若从顶点阶图中，若从顶点u到到v(u v)存在通路，则从存在通路，则从u到到v存在长度小于等于存在长度小于等于n-1的基本通路。若存在的基本通路。若存在v到自身

18、的简单回路，到自身的简单回路，则从则从v到自身存在长度不超过到自身存在长度不超过n的基本回路。的基本回路。证明：证明：设设T=v0e1v1ekvk(v0=u,vk=v)为为u到到v的通路，的通路，若若T上无重复出现的顶点，则上无重复出现的顶点，则T为基本通路。否则必为基本通路。否则必存在存在ts，vt=vs，在，在T中去掉中去掉vt到到vs的一段，所得通路的一段，所得通路仍为仍为u到到v的通路，不妨仍记为的通路，不妨仍记为T。若。若T上还有重复出上还有重复出现的顶点，就做同样的处理，直到无重复出现的顶点现的顶点，就做同样的处理，直到无重复出现的顶点为止。最后得到的通路是为止。最后得到的通路是u

19、到到v的基本通路，显然它的的基本通路，显然它的长度应小于等于长度应小于等于n-1。类似地可证定理的后半部分。类似地可证定理的后半部分。1/3/202330定义定义 连通性连通性(connectivity)设设G=，若从，若从vi到到vj存在一条通存在一条通路，则称路，则称vi到到vj连通连通(connective)或或可达可达。说明说明：对无向图而言，若：对无向图而言，若vi到到vj可达，则可达，则vj到到vi也可达。对有向图而言则未必。也可达。对有向图而言则未必。1/3/202331定理定理 任意一个连通无向图的任意两个不同顶任意一个连通无向图的任意两个不同顶点都存在一条简单通路。点都存在一

20、条简单通路。定义定义 无向图的连通性无向图的连通性 若若G=中任意两个顶点都连通，则称中任意两个顶点都连通，则称此无向图是此无向图是连通的连通的(connected)。定义定义 连通分图连通分图(connected components)图图G可分为几个不相连通的子图，每一子可分为几个不相连通的子图，每一子图本身都是连通的。称这几个子图为图本身都是连通的。称这几个子图为G的的连通连通分图分图。1/3/202332定义定义 有向图的连通性有向图的连通性(1)弱连通弱连通：若若D=对应的无向图是连通图，对应的无向图是连通图，则称则称G为为弱连通弱连通(weakly connected)。(2)强连

21、通强连通：若若D=中任意两点间都有通路，中任意两点间都有通路，即对即对a和和b，a到到b可达，可达，b到到a可达，称可达，称G为为强连通强连通(strongly connected)。1/3/202333连连通通无无向向图图 弱弱连连通通 强强连连通通 1/3/202334定义定义 割点割点 设设G=是无向图，是无向图，vV，若从，若从G中中删除顶点删除顶点v后所得的连通分支数后所得的连通分支数p(G-v)p(G),则称则称v是是G中的中的割点割点。割点割点1/3/202335 设设G=是无向图，是无向图，eE，若从，若从G中中删除边删除边e后所得的连通分支数后所得的连通分支数p(G-e)p(

22、G),则称则称e是是G中的中的割边割边。定义定义 割边割边割边割边1/3/2023363 图的矩阵表示图的矩阵表示v 本节主要考虑三种矩阵，即关联矩阵，本节主要考虑三种矩阵，即关联矩阵，邻接矩阵与可达矩阵。关联矩阵反映的邻接矩阵与可达矩阵。关联矩阵反映的是顶点与边（弧）的关系；邻接矩阵反是顶点与边（弧）的关系；邻接矩阵反映的是顶点与顶点之间的关系；可达矩映的是顶点与顶点之间的关系；可达矩阵反映了图的联通情况。有向图与无向阵反映了图的联通情况。有向图与无向图将分别讨论。图将分别讨论。1/3/2023371.无向图的关联矩阵无向图的关联矩阵 设无向图设无向图G=，V=v1,v2,vn,E=e1,e

23、2,em，令，令mij为顶点为顶点vi与边与边ej的的关联次数，则称关联次数，则称(mij)n m为为G的的关联矩阵关联矩阵，记为记为M(G)。显然显然mij的可能取值为的可能取值为0(vi与与ej不关联不关联)，1(vi与与ej关联关联1次次)，2(vi与与ej关联关联2次，即次，即ej是以是以vi为为端点的环端点的环)。1/3/20233800000210010111000111GM)(表示如下的无向图：表示如下的无向图：v1v2v3e1e2e3e4e5v4。（环环关关联联的的顶顶点点重重合合）点点说说明明每每条条边边关关联联两两个个顶顶，),.,(m21j2mn1iij的度数）。的度数）

24、。行元素之和为行元素之和为（第（第iim1jijvivdm)(（符合握手定理）。（符合握手定理）。n1iin1im1jijm1jn1iijvdmmm2)(为孤立点。为孤立点。，当且仅当，当且仅当im1jijv0m 为为平平行行边边。与与列列相相同同，则则说说明明列列与与第第若若第第kjeekj1/3/202339要求要求D D中无环存在中无环存在2.有向图的关联矩阵有向图的关联矩阵 设有向图设有向图D=，V=v1,v2,vn,E=e1,e2,em，令，令则称则称(mij)n m为为D的的关联矩阵关联矩阵，记为，记为M(D)。的终点。的终点。为为，不关联，不关联，与与，的始点，的始点，为为，ji

25、jijiijev1ev0ev1m1/3/20234001110100001110100011GM)(其关联矩阵为：其关联矩阵为：。中中所所有有元元素素的的代代数数和和为为，所所以以)(),.,(0DM0mm21j0mm1jn1iijn1iij.)()()().()()()(n1im1jijn1iin1im1jijim1jijim1jij1mmvd1mvd1mvd1m所所以以有有，v1v2v3e1e2e3e4v4e51/3/202341有向图的邻接矩阵有向图的邻接矩阵 设有向图设有向图D=，V=v1,v2,vn,|E|=m，令，令aij(1)为为vi邻接到邻接到vj的边的条数，的边的条数，称称(

26、aij(1)n n为为D的的邻接矩阵邻接矩阵，记为，记为A(D)。1/3/2023420100100001000121DA)(其邻接矩阵为：其邻接矩阵为：n1in1iin1j1ijin1j1ijmvdavda.)()()()(，.)()()()(mvdavdan1jjm1jn1i1ijjn1i1ij，v1v2v3v4n1i1iin1in1j1ijaa2的的回回路路总总数数。中中长长度度为为中中环环的的个个数数，即即为为通通路路总总数数，而而的的中中长长度度为为中中边边的的总总数数，也也可可看看成成为为可可知知，由由1DD1DD)(1),)()(1/3/202343的的回回路路数数。各各顶顶点点

27、的的长长度度为为或或终终于于中中始始于于为为中中对对角角线线上上元元素素之之和和而而的的通通路路数数，中中长长度度为为为为中中所所有有元元素素之之和和的的回回路路数数。到到自自身身长长度度为为为为的的通通路路数数，长长度度为为到到为为顶顶点点则则，这这里里简简记记为为考考虑虑laAlaAlvalvvaaaalaAADAiliiljilijliliijilijkjkliklijnnlijlll)()()()(,)()()()()()()(DD2(),111/3/202344接上例，计算接上例，计算A2,A3,A4如下：如下：.,1000010010004621010010000100012101

28、00100001003421010010000100342101001000010001211000010010001321100001001000132101001000010001210100100001000121432AAA1/3/202345 观察各矩阵发现，观察各矩阵发现，a13(2)=3,a13(3)=4,a13(4)=6，可，可知，知，D中中v1到到v3长度为长度为2的通路有的通路有3条，长度为条，长度为3的的通路有通路有4条，长度为条，长度为4的通路有的通路有6条。条。a11(2)=1,a11(3)=1,a11(4)=1，可知，可知，v1到自身长度为到自身长度为2,3,4的回

29、路各有的回路各有1条。条。条条回回路路。，其其中中有有为为的的通通路路总总数数中中长长度度为为，所所以以由由于于1133D133jiija,)(1/3/202346定理定理 设设A为有向图为有向图D的邻接矩阵，的邻接矩阵，V=v1,v2,vn，则，则Al(l1)中元素中元素aij(l)为为vi到到vj长度长度为为l的通路数，的通路数，为为D中长度为中长度为l的通路总数，的通路总数，其中其中 为为D中长度为中长度为l的回路数。的回路数。jilija,)(iliia)(推论推论 设设Br=A+A2+Ar(r1)，则，则Br中元素中元素bij(r)为为D中中vi到到vj长度小于等于长度小于等于r的通

30、路数，的通路数，为为D中长度小于等于中长度小于等于r的通路总数，其中的通路总数，其中为为D中长度小于等于中长度小于等于r的回路总数。的回路总数。jirijb,)(iriib)(1/3/202347有向图的可达矩阵有向图的可达矩阵 设有向图设有向图D=，V=v1,v2,vn,令令称称(pij)n n为为D的的可达矩阵可达矩阵，记为，记为P(D)。.,.,).(nipjivpiijiij2110v1，否则，否则可达可达，定义可改为：定义可改为：.,.,).()(nipjibpiinijij2110011，否则，否则，1/3/202348接上例：接上例：.1200210012004862010010

31、000100342110000100100013210100100001000121323AAAB1100110011101111P即即D的可达矩阵可通的可达矩阵可通过邻接矩阵求得。过邻接矩阵求得。1/3/2023494 最短路径及关键路径最短路径及关键路径定义定义 带权图带权图v 对于有向图或无向图对于有向图或无向图G的每条边附加一个实数的每条边附加一个实数w(e)，则称，则称w(e)为边为边e上的上的权权。G连同附加在各边上的实数称为连同附加在各边上的实数称为带权图带权图(weighted graph)。记为。记为G=.v Let P be a nonempty path in a wei

32、ghted graph G=(V,E,W)consisting of k edges xv1,v1v2,vk-1y(possibly v1=y).The weight of P,denoted as W(P)is the sum of the weights w(xv1),w(v1v2),w(vk-1y).v 当无向边当无向边e=(vi,vj)或有向边或有向边e=时，时，w(e)也可记为也可记为wij.1/3/202350 设带权图设带权图G=，G中每条边带的权均大于等于中每条边带的权均大于等于0，x,y为为G中任意两个顶点，从中任意两个顶点，从x到到y的所有通路中带权最小的所有通路中带权最小

33、的通路称为的通路称为x到到y的的最短路径最短路径，求给定两顶点间的最短路径，求给定两顶点间的最短路径问题称为问题称为最短路径问题最短路径问题。(If no path between x and y has weight less than W(P),then P is called a shortest path.)单源最短路径单源最短路径(Single-source shortest paths)We are given a weighted graph G=and a source vertex s.The problem is to find a shortest path from s

34、 to each vertex v.1/3/202351Dijstra,Edsgar Wybe(1930-)荷兰计算机科学家，荷兰计算机科学家，1972年图林奖得主。年图林奖得主。最著名的成果最著名的成果：首先指出程序设计语言中的：首先指出程序设计语言中的goto语句是有害的，并首创了结构化程序设计方法。语句是有害的，并首创了结构化程序设计方法。至今仍被广泛应用的算法至今仍被广泛应用的算法：解决机器人运动路径：解决机器人运动路径规划问题的规划问题的“最短路径算法最短路径算法”。被引用最多的论断被引用最多的论断：“程序测试只能用来证明有程序测试只能用来证明有错，绝不能证明无错。错，绝不能证明无错

35、。”被引用作为其被引用作为其60岁生日纪念论文集书名的岁生日纪念论文集书名的另一句另一句名言名言：Beauty is our business1/3/202352求最短路径的求最短路径的Dijstra算法算法输入：连通带权图输入：连通带权图G，|V|=n,指定顶点指定顶点s V输出：每个顶点输出：每个顶点v的标注的标注(l(v),u),其中：其中：l(v)即从即从s到到v的最短路径长度。的最短路径长度。u是该路径上是该路径上v的前一个顶点。的前一个顶点。1/3/202353求最短路径的求最短路径的Dijstra算法算法 算法步骤：算法步骤：1.初始化：初始化：i=0,S0=s,l(s)=0,对

36、其它一切对其它一切v VG,将将l(v)置为置为。若。若n=1，结束。，结束。2.v Si=VG-Si,比较比较l(v)和和l(ui)+w(ui,v)的值的值(ui Si)，如，如果果l(ui)+w(ui,v)l(v),则将则将v的标注更新为的标注更新为(l(ui)+w(ui,v),ui)，即：，即：l(v)=minl(v),minu Sil(u)+w(u,v).3.对所有对所有Si中的顶点，找出具有最小中的顶点，找出具有最小l(v)的顶点的顶点v,作为作为ui+1.4.Si+1=Si ui+1.5.i=i+1;若若i=n-1,终止。否则，转到第终止。否则，转到第2步。步。1/3/202354

37、求最短路径的一个例子求最短路径的一个例子 s 7 7 2 1 2 3 1 2 4 4 8 3 5 3 3 6 5 0 s 7 7 2 1 2 3 1 2 4 4 8 3 5 3 3 6 5 0 1 2 8 4 7 s 7 7 2 1 2 3 1 2 4 4 8 3 5 3 3 6 5 0 1 2 8 4 7 4 s 7 7 2 1 2 3 1 2 4 4 8 3 5 3 3 6 5 0 1 2 8 4 7 3 a f b c e g d 1/3/202355求最短路径的一个例子求最短路径的一个例子(续续)s 7 7 2 1 2 3 1 2 4 4 8 3 5 3 3 6 5 0 1 2 8 9

38、 4 6 3 s 7 7 2 1 2 3 1 2 4 4 8 3 5 3 3 6 5 0 1 2 6 9 4 6 3 s 7 7 2 1 2 3 1 2 4 4 8 3 5 3 3 6 5 0 1 2 6 9 4 6 3 s 7 7 2 1 2 3 1 2 4 4 8 3 5 3 3 6 5 0 1 2 6 9 4 6 3 1/3/202356求最短路径的一个例子求最短路径的一个例子(续续)将计算过程用一张表描述出来：将计算过程用一张表描述出来：vksabcdefg01234567(0)1(1,s)22(2,s)43(3,b)9999(9,c)4444(4,s)88886(6,e)777666

39、(6,c)W(T)01239466T=sT=saT=sbT=sbcT=sbcdT=seT=sefT=sbcg1/3/202357vPERT图图 设设D=是有向带权图，是有向带权图，|V|=n，若，若D是简单图（无是简单图（无平行边、无环），无回路。有一个顶点入度为平行边、无环），无回路。有一个顶点入度为0，称为，称为发发点点，有一个顶点出度为，有一个顶点出度为0，称为，称为收点收点。边。边的权的权wij表表示时间。则称示时间。则称D为为PERT图图(Plan Evaluate Revise Technology Graph)。v 关键路径关键路径(Key paths)在在PERT图中求图中求关

40、键路径关键路径，就是求从发点到收点的一条，就是求从发点到收点的一条最最长路径长路径，通过求各顶点的，通过求各顶点的最早完成时间最早完成时间来求关键路径。来求关键路径。1/3/202358v最早完成时间最早完成时间 自发点自发点v1开始沿最长路径到达开始沿最长路径到达vi所需时间，称为所需时间，称为vi的的最早完成时间最早完成时间，记作，记作TE(vi),i=1,2,n.显然，显然，TE(v1)=0,vi(i 1)的最早完成时间按如下的最早完成时间按如下公式计算：公式计算：TE(vi)=maxTE(vj)+wij,i=2,3,n.vj TD-(vi)收点的收点的TE(vn)就是从就是从v1到到v

41、n的最长路径的权。的最长路径的权。1/3/202359v最晚完成时间最晚完成时间 在保证收点在保证收点vn的最早完成时间不增加的条件下，的最早完成时间不增加的条件下，自自v1最迟到达最迟到达vi的时间，称为的时间，称为vi的的最晚完成时间最晚完成时间，记作记作TL(vi).显然，显然，TL(vn)=TE(vn).i n时的最晚完成时间按时的最晚完成时间按如下公式计算：如下公式计算：TL(vi)=minTL(vj)-wij,i=n-1,2,1.vj TD+(vi)1/3/202360v缓冲时间缓冲时间ES(vi)=TL(vi)-TE(vi),i=1,2,n.注：在关键路径上，任何工序如果耽误了时

42、间注：在关键路径上，任何工序如果耽误了时间t，整个工程就耽误了时间，整个工程就耽误了时间t，因而在关键路，因而在关键路径上各顶点的缓冲时间均为径上各顶点的缓冲时间均为0。即若。即若vi为关键为关键路径上的顶点，则路径上的顶点，则TL(vi)=TE(vi)。1/3/202361求关键路径的一个例子求关键路径的一个例子 414046323411v2v5v1v3v7v8v4v621/3/202362求关键路径的一个例子求关键路径的一个例子(续续)v各顶点的最早完成各顶点的最早完成时间如下：时间如下：TE(v1)=0;TE(v2)=max0+1=1;TE(v3)=max0+2,1+0=2;TE(v4)

43、=max0+3,2+2=4;TE(v5)=max1+3,4+4=8;TE(v6)=max2+4,8+1=9;TE(v7)=max1+4,2+4=6;TE(v8)=max9+1,6+6=12.v各顶点的最晚完成时间各顶点的最晚完成时间如下：如下：TL(v8)=12;TL(v7)=min12-6=6;TL(v6)=min12-1=11;TL(v5)=min11-1=10;TL(v4)=min10-4=6;TL(v3)=min6-2,11-4,6-4=2;TL(v2)=min2-0,10-3,6-4=2;TL(v1)=min2-1,2-2,6-3=0.1/3/202363求关键路径的一个例子求关键路径的一个例子(续续)v各顶点的缓冲时间如下：各顶点的缓冲时间如下：TS(v1)=0-0=0;TS(v2)=2-1=1;TS(v3)=2-2=0;TS(v4)=6-4=2;TS(v5)=10-8=2;TS(v6)=11-9=2;TS(v7)=6-6=0;TS(v8)=12-12=0.v关键路径为：关键路径为：v1v3v7v8.1/3/202364作业作业 编一个程序实现编一个程序实现Dijstra算法算法1/3/202365