图论离散数学离散数学第四版清华出版社课件.ppt

第七章第七章 图的基本概念图的基本概念§1 无向图及有向图无向图及有向图§2 通路、回路、图的连通性通路、回路、图的连通性§3 图的矩阵表示图的矩阵表示§4 最短路径及关键路径最短路径及关键路径9/22/20241第四部分：图论（授课教师：向胜军）图图(Graph)(Graph)：： 可可直直观观地地表表示示离离散散对对象象之之间间的的相相互互关关系系，，研究它们的共性和特性，以便解决具体问题研究它们的共性和特性，以便解决具体问题 图图是是一一类类相相当当广广泛泛的的实实际际问问题题的的数数学学模模型型，，有有着着极极其其丰丰富富的的内内容容，，是是数数据据结结构构等等课课程程的的先先修修内内容容学学习习时时应应掌掌握握好好图图论论的的基基本本概概念念、、基基本本方方法法、、基基本本算算法法，，善善于于把把实实际际问问题题抽抽象象为为图图论的问题，然后用图论的方法解决问题论的问题，然后用图论的方法解决问题9/22/20242第四部分：图论（授课教师：向胜军）§1 无向图及有向图无向图及有向图v 本节介绍图的一些最常用的概念本节介绍图的一些最常用的概念, ,主要有：主要有： 无向图，有向图，边，顶点无向图，有向图，边，顶点( (或结点，点或结点，点) )，弧，弧( (或有向边或有向边) )，顶点集，边集，，顶点集，边集，n n阶图，有阶图，有限图，关联，多重图，简单图，完全图，母图限图，关联，多重图，简单图，完全图，母图, ,子图子图, , 生成子图，导出子图，补图，图的同构，生成子图，导出子图，补图，图的同构，入度，出度，度，孤立点等。

入度，出度，度，孤立点等 主要定理：握手定理主要定理：握手定理9/22/20243第四部分：图论（授课教师：向胜军）[定义定义] 图图 V是是一一个个非非空空有有限限集集，，E是是V上上的的一一个个二二元元关关系系，，有有序序对对称称为为有有向向图图(Directed Graph)可记为D. 若若将将E中中的的有有序序对对看看成成是是无无序序的的（（即即将将e=看看成成e={a,b}或或(a,b)）），，则则称称为为无无向向图图(Undirected Graph)有有向向图图和和无无向向图图统称为统称为图图(Graph)，记为，记为G G =9/22/20244第四部分：图论（授课教师：向胜军）[定义定义] 顶点顶点 Ｖ中的元素称为Ｖ中的元素称为顶点顶点，用带标记的点表示，，用带标记的点表示，也称为也称为结点结点(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)9/22/20245第四部分：图论（授课教师：向胜军）[定义定义] 图的分类图的分类 对对图图G=，，若若允允许许E是是一一个个多多重重集集合合，，则则称称图图G为为多多重重图图(Multigraph)其其相相同同的的元元素素称为称为平行边平行边，平行边的条数称为，平行边的条数称为重数重数 无环的非多重图称为无环的非多重图称为简单图简单图(Simple Graph)9/22/20246第四部分：图论（授课教师：向胜军）[定义定义] 相邻和关联相邻和关联 在无向图在无向图G中，若中，若e=(a, b)∈∈E，则称，则称a与与b彼此相邻彼此相邻(adjacent)，或边，或边e关联关联 (incident)或或联结联结(connect) a, ba, b称为称为边边e的的端点端点或或结束顶点结束顶点(endpoint) 在有向图在有向图D中，若中，若e=∈∈E，即箭头，即箭头由由a到到b，称，称a邻接到邻接到b，或，或a关联关联或或联结联结b。

a称为称为e的的始点始点(initial vertex)，，b称为称为e的的终终点点(terminal/end vertex)9/22/20247第四部分：图论（授课教师：向胜军）[定义定义] 孤立点孤立点 若若a∈∈V，，a不与其他顶点相邻，称不与其他顶点相邻，称a为为孤立孤立点点(isolated vertex)[定义定义] 顶点的度顶点的度 在无向图在无向图G中，与中，与a相邻的顶点的数目称为相邻的顶点的数目称为a的的度度(degree)记为deg(a)或或d(a) 在有向图在有向图D中，以中，以a为终点的边的条数称为为终点的边的条数称为a的的入度入度(in-degree)记为deg–(a)或或d–(a)以a为始点的边的条数称为为始点的边的条数称为a的的出度出度(out-degree)记为记为deg+(a)或或d+(a)9/22/20248第四部分：图论（授课教师：向胜军）[定理定理1 (握手定理握手定理Handshaking)] 设无向图设无向图G=有有n个顶点，个顶点，m条边，则条边，则G中所有中所有顶点的度之和等于顶点的度之和等于m的两倍。

即的两倍即证明思路：利用数学归纳法证明思路：利用数学归纳法[定理定理2] 无向图中度为奇数的顶点个数恰有无向图中度为奇数的顶点个数恰有偶数个证明思路：将图中顶点的度分类，再利用定理证明思路：将图中顶点的度分类，再利用定理19/22/20249第四部分：图论（授课教师：向胜军）[定理定理3] 设有向图设有向图D=有有n个顶点，个顶点，m条边，则条边，则G中所有顶点的入度之和等于中所有顶点的入度之和等于所有顶点的出度之和，也等于所有顶点的出度之和，也等于m即：即：证明思路：利用数学归纳法证明思路：利用数学归纳法9/22/202410第四部分：图论（授课教师：向胜军）一些特殊的简单图：一些特殊的简单图： (1) 无向完全图无向完全图Kn(Complete Graphs) (2) 有向完全图有向完全图 (3) 零图零图：：E=. (4) 平凡图平凡图：：E=且且|V|=1. (5) 正则图正则图：若图：若图G＝＝中每个顶点中每个顶点的度均为的度均为n，称此图，称此图G是是n-正则图正则图(n-regular graph)。

9/22/202411第四部分：图论（授课教师：向胜军）完全图完全图(n=1,2,3,4,5)9/22/202412第四部分：图论（授课教师：向胜军）[定理定理4] 设无向完全图设无向完全图G有有n个顶点，个顶点，则则G有有n(n-1)/2条边证明：证明：每一顶点都与其余的每一顶点都与其余的n-1个顶点相个顶点相邻，即每一顶点的度为邻，即每一顶点的度为n-1，共有，共有n个顶个顶点，则图点，则图G的度为的度为n(n-1)，由握手定理，，由握手定理，得边数得边数m=n(n-1)/2.9/22/202413第四部分：图论（授课教师：向胜军）正则图（各顶点的度相同）正则图（各顶点的度相同）3-正则图正则图 3-正则图正则图9/22/202414第四部分：图论（授课教师：向胜军）[定义定义] 子图子图 设设G=，，G’=是是两两个个图图，，若若V’ V，， 且且 E’ E，， 则则 称称 G’为为 G的的 子子 图图(subgraph)注：注： 当当V’=V时，称时，称G’为为G的的生成子图生成子图。

当当E’ E，或，或V’ V时，称时，称G’为为G的的真子图真子图9/22/202415第四部分：图论（授课教师：向胜军）[定义定义] 补图补图 设设G=是是n阶无向简单图，以阶无向简单图，以V为顶为顶点集，以所有能使点集，以所有能使G成为完全图成为完全图Kn的添加边的添加边组成的集合为边集的图，称为组成的集合为边集的图，称为G相对于完全相对于完全图图Kn的补图，简称的补图，简称G的的补图补图，记为，记为 图图G与其补图与其补图G’具有相同的顶点集，其边集具有相同的顶点集，其边集不相交，构成相应完全图边集的划分不相交，构成相应完全图边集的划分9/22/202416第四部分：图论（授课教师：向胜军）图图 A图图 B图图 C图图 D图图 E图图 F9/22/202417第四部分：图论（授课教师：向胜军）图Ａ是一个无向完全图图Ａ是一个无向完全图图Ｂ，Ｃ，Ｄ，Ｅ，Ｆ均是Ａ的子图图Ｂ，Ｃ，Ｄ，Ｅ，Ｆ均是Ａ的子图图Ｃ的顶点ａ是孤立顶点图Ｃ的顶点ａ是孤立顶点图Ｂ的边图Ｂ的边(ａ，ｂａ，ｂ)是孤立边是孤立边图Ｄ是图Ｃ的子图图Ｄ是图Ｃ的子图图Ｅ是图Ｃ的补图图Ｅ是图Ｃ的补图9/22/202418第四部分：图论（授课教师：向胜军）9/22/202419第四部分：图论（授课教师：向胜军）例：例：9/22/202420第四部分：图论（授课教师：向胜军）例：例：9/22/202421第四部分：图论（授课教师：向胜军）例：例：9/22/202422第四部分：图论（授课教师：向胜军）有向图有向图例：例：abcde2(a)1(b)3(d)4(c)5(e)9/22/202423第四部分：图论（授课教师：向胜军）例：例：(1) 画出画出4个顶点个顶点3条边的所有可能非同构的条边的所有可能非同构的无向简单图。

无向简单图2) 画出画出3个顶点个顶点2条边的所有可能非同构的条边的所有可能非同构的有向简单图有向简单图• (1)(2)9/22/202424第四部分：图论（授课教师：向胜军）§2 通路、回路、图的连通性通路、回路、图的连通性连通性连通性(Connectivity)[定义定义] 通路通路(path) 给给定定图图G=，，设设图图G中中顶顶点点和和边边的的交交替替序序列列为为T=v0e1v1e2…ekvk，，若若T满满足足如如下下条条件件：：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)9/22/202425第四部分：图论（授课教师：向胜军）“巧渡河巧渡河”问题问题v问题：人、狼、羊、菜用一条只能同时载两位问题：人、狼、羊、菜用一条只能同时载两位的小船渡河，的小船渡河，“狼羊狼羊”、、“羊菜羊菜”不能在无人不能在无人在场时共处，当然只有人能架船。

在场时共处，当然只有人能架船v图模型：顶点表示图模型：顶点表示“原岸的状态原岸的状态”，两点之间，两点之间有边当且仅当一次合理的渡河有边当且仅当一次合理的渡河“操作操作”能够实能够实现该状态的转变现该状态的转变v起始状态是起始状态是“人狼羊菜人狼羊菜”，结束状态是，结束状态是“空空”v问题的解：找到一条从起始状态到结束状态的问题的解：找到一条从起始状态到结束状态的尽可能短的通路尽可能短的通路9/22/202426第四部分：图论（授课教师：向胜军）“巧渡河巧渡河”问题的解问题的解v注意：在注意：在“人狼羊菜人狼羊菜”的的16种组合中允种组合中允许出现的只有许出现的只有10种9/22/202427第四部分：图论（授课教师：向胜军）[定义定义] 简单通路简单通路(Simple Path) 若若通通路路中中所所有有边边互互不不相相同同，，称称此此道道路路为为简简单单通通路路若若回回路路中中的的所所有有边边互互不不相相同同，，称称为为简简单回路单回路(Simple Circuit)[定义定义] 基本通路基本通路(Element Path) 一一条条通通路路中中，，除除了了始始点点和和终终点点可可以以相相同同，，其其余余顶顶点点均均互互不不相相同同，，称称此此通通路路为为基基本本通通路路( (初初级级通通路路) )。

当当其其是是回回路路时时，，称称为为基基本本回回路路(Element Circuit初级回路初级回路或或圈圈)9/22/202428第四部分：图论（授课教师：向胜军） e5, e1, e2, e3, e4是简单通路，不是基本通是简单通路，不是基本通路，因为路，因为c, a, b, c, d, b中中b, c均出现了两次均出现了两次但但c, d, b, c是基本通路，也是基本回路是基本通路，也是基本回路9/22/202429第四部分：图论（授课教师：向胜军）[定定理理] 在在一一个个n阶阶图图中中，，若若从从顶顶点点u到到v (u v)存存在在通通路路，，则则从从u到到v存存在在长长度度小小于于等等于于n-1的的基基本本通通路路若若存存在在v到到自自身身的的简简单单回回路路，，则则从从v到到自自身身存存在在长长度度不不超超过过n的的基基本本回回路证证明明：：设设T=v0e1v1…ekvk(v0=u, vk=v)为为u到到v的的通通路路，，若若T上上无无重重复复出出现现的的顶顶点点，，则则T为为基基本本通通路路否否则则必必存存在在t

若若T上上还还有有重重复复出出现现的的顶顶点点，，就就做做同同样样的的处处理理，，直直到到无无重重复复出出现现的的顶顶点点为为止止最最后后得得到到的的通通路路是是u到到v的的基基本本通通路路，，显显然然它它的的长度应小于等于长度应小于等于n-1类似地可证定理的后半部分类似地可证定理的后半部分9/22/202430第四部分：图论（授课教师：向胜军）[定义定义] 连通性连通性(connectivity) 设设G=，若从，若从vi到到vj存在一条通存在一条通路，则称路，则称vi到到vj连通连通(connective)或或可达可达说明说明：对无向图而言，若：对无向图而言，若vi到到vj可达，则可达，则vj到到vi也可达对有向图而言则未必对有向图而言则未必9/22/202431第四部分：图论（授课教师：向胜军）[定定理理] 任任意意一一个个连连通通无无向向图图的的任任意意两两个个不不同同顶点都存在一条简单通路顶点都存在一条简单通路[定义定义] 无向图的连通性无向图的连通性 若若G=中任意两个顶点都连通，则称中任意两个顶点都连通，则称此无向图是此无向图是连通的连通的(connected)。

[定定 义义 ] 连连 通通 分分 图图 (connected components) 图图G可可分分为为几几个个不不相相连连通通的的子子图图，，每每一一子子图图本本身身都都是是连连通通的的称称这这几几个个子子图图为为G的的连连通通分分图图9/22/202432第四部分：图论（授课教师：向胜军）[定义定义] 有向图的连通性有向图的连通性(1) 弱连通弱连通：： 若若D=对对应应的的无无向向图图是是连连通通图图，，则称则称G为为弱连通弱连通(weakly connected)2) 强连通强连通：： 若若D=中中任任意意两两点点间间都都有有通通路路，，即即对对a和和b，，a到到b可可达达，，b到到a可可达达，，称称G为为强连通强连通(strongly connected) 9/22/202433第四部分：图论（授课教师：向胜军）9/22/202434第四部分：图论（授课教师：向胜军）[定义定义] 割点割点 设设G=是是无无向向图图，，v∈∈V，，若若从从G中中删删除除顶顶点点v后后所所得得的的连连通通分分支支数数p(G-v)>p(G), 则称则称v是是G中的中的割点割点。

割点割点9/22/202435第四部分：图论（授课教师：向胜军） 设设G=是是无无向向图图，，e∈∈E，，若若从从G中中删删除除边边e后后所所得得的的连连通通分分支支数数p(G-e)>p(G), 则称则称e是是G中的中的割边割边[定义定义] 割边割边割边割边9/22/202436第四部分：图论（授课教师：向胜军）§3 图的矩阵表示图的矩阵表示v 本节主要考虑三种矩阵，即关联矩阵，本节主要考虑三种矩阵，即关联矩阵，邻接矩阵与可达矩阵关联矩阵反映的邻接矩阵与可达矩阵关联矩阵反映的是顶点与边（弧）的关系；邻接矩阵反是顶点与边（弧）的关系；邻接矩阵反映的是顶点与顶点之间的关系；可达矩映的是顶点与顶点之间的关系；可达矩阵反映了图的联通情况有向图与无向阵反映了图的联通情况有向图与无向图将分别讨论图将分别讨论9/22/202437第四部分：图论（授课教师：向胜军）关联矩阵（关联矩阵（incidence matrix））1. 无向图的关联矩阵无向图的关联矩阵 设设无无向向图图G=，，V={v1,v2,…,vn}, E={e1,e2,…,em}，，令令mij为为顶顶点点vi与与边边ej的的关关联联次次数数，，则则称称(mij)n m为为G的的关联矩阵关联矩阵，记为，记为M(G)。

显显然然mij的的可可能能取取值值为为0(vi与与ej不不关关联联)，，1(vi与与ej关关联联1次次)，，2(vi与与ej关关联联2次次，，即即ej是是以以vi为端点的环为端点的环)9/22/202438第四部分：图论（授课教师：向胜军）表示如下的无向图：表示如下的无向图：v1v2v3e1e2e3e4e5v49/22/202439第四部分：图论（授课教师：向胜军）关联矩阵关联矩阵（（（（incidence matrixincidence matrix））））要求要求D D中无环存在中无环存在2. 有向图的关联矩阵有向图的关联矩阵 设设有有向向图图D=，，V={v1,v2,…,vn}, E={e1,e2,…,em}，令，令则称则称(mij)n m为为D的的关联矩阵关联矩阵，记为，记为M(D)9/22/202440第四部分：图论（授课教师：向胜军）其关联矩阵为：其关联矩阵为：v1v2v3e1e2e3e4v4e59/22/202441第四部分：图论（授课教师：向胜军）邻接矩阵邻接矩阵（（（（adjacency matrixadjacency matrix））））有向图的邻接矩阵有向图的邻接矩阵 设设有有向向图图D=，，V={v1,v2,…,vn}, |E|=m，，令令aij(1)为为vi邻邻接接到到vj的的边边的的条条数数，，称称(aij(1))n n为为D的的邻邻接矩阵接矩阵，记为，记为A(D)。

9/22/202442第四部分：图论（授课教师：向胜军）其邻接矩阵为：其邻接矩阵为：v1v2v3v49/22/202443第四部分：图论（授课教师：向胜军）9/22/202444第四部分：图论（授课教师：向胜军）接上例，计算接上例，计算A2, A3, A4如下：如下：9/22/202445第四部分：图论（授课教师：向胜军）• 观察各矩阵发现，观察各矩阵发现，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的回路各有的回路各有1条9/22/202446第四部分：图论（授课教师：向胜军）[定定理理] 设设A为为有有向向图图D的的邻邻接接矩矩阵阵，，V={v1, v2, …, vn}，则，则Al(l≥1)中元素中元素aij(l)为为vi到到vj长度长度为为l的通路数，的通路数， 为为D中长度为中长度为l的通路总数，的通路总数，其中其中 为为D中长度为中长度为l的回路数。

的回路数[推推论论] 设设Br=A+A2+…+Ar(r≥1)，，则则Br中中元元素素bij(r)为为D中中vi到到vj长度小于等于长度小于等于r的通路数，的通路数，为为D中长度小于等于中长度小于等于r的通路总数，其中的通路总数，其中为为D中长度小于等于中长度小于等于r的回路总数的回路总数9/22/202447第四部分：图论（授课教师：向胜军）可达矩阵可达矩阵（（（（reachable matrixreachable matrix））））有向图的可达矩阵有向图的可达矩阵 设设有有向向图图D=，，V={v1,v2,…,vn}, 令令称称(pij)n n为为D的的可达矩阵可达矩阵，记为，记为P(D)定义可改为：定义可改为：9/22/202448第四部分：图论（授课教师：向胜军）接上例：接上例：即即D的可达矩阵可通的可达矩阵可通过邻接矩阵求得过邻接矩阵求得9/22/202449第四部分：图论（授课教师：向胜军）§4 最短路径及关键路径最短路径及关键路径[定义定义] 带权图带权图v 对对于于有有向向图图或或无无向向图图G的的每每条条边边附附加加一一个个实实数数w(e)，，则则称称w(e)为为边边e上上的的权权。

G连连同同附附加加在在各各边边上上的的实实数数称称为为带带权权图图(weighted graph) 记为记为G=. v Let P be a nonempty path in a weighted 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.9/22/202450第四部分：图论（授课教师：向胜军）最短路径问题最短路径问题（（（（shortest paths problemshortest paths problem））））v 设设带带权权图图G=，，G中中每每条条边边带带的的权权均均大大于于等等于于0，，x, y为为G中中任任意意两两个个顶顶点点，，从从x到到y的的所所有有通通路路中中带带权权最最小小的的通通路路称称为为x到到y的的最最短短路路径径，，求求给给定定两两顶顶点点间间的的最最短短路路径径问问题题称称为为最最短短路路径径问问题题。

If no path between x and y has weight less than W(P), then P is called a shortest path. )v 单源最短路径单源最短路径(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 to each vertex v. 9/22/202451第四部分：图论（授课教师：向胜军）Dijstra, Edsgar Wybe(1930-)v荷兰计算机科学家，荷兰计算机科学家，1972年图林奖得主年图林奖得主v最著名的成果最著名的成果：首先指出程序设计语言中的：首先指出程序设计语言中的goto语句是有害的，并首创了结构化程序设计方法语句是有害的，并首创了结构化程序设计方法v至今仍被广泛应用的算法至今仍被广泛应用的算法：解决机器人运动路径：解决机器人运动路径规划问题的规划问题的“最短路径算法最短路径算法”。

v被引用最多的论断被引用最多的论断：：“程序测试只能用来证明有程序测试只能用来证明有错，绝不能证明无错错，绝不能证明无错v被引用作为其被引用作为其60岁生日纪念论文集书名的岁生日纪念论文集书名的另一句另一句名言名言：：Beauty is our business9/22/202452第四部分：图论（授课教师：向胜军）求最短路径的求最短路径的Dijstra算法算法v输输入入：：连连通通带带权权图图G，，|V|=n, 指指定定顶顶点点s Vv输出：每个顶点输出：每个顶点v的标注的标注(l(v), u), 其中：其中：–l(v)即从即从s到到v的最短路径长度的最短路径长度–u是该路径上是该路径上v的前一个顶点的前一个顶点9/22/202453第四部分：图论（授课教师：向胜军）求最短路径的求最短路径的Dijstra算法算法v 算法步骤：算法步骤：1. 初始化：初始化：i=0, S0={s}, l(s)=0, 对其它一切对其它一切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)=min{l(v), minu Si{l(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步 9/22/202454第四部分：图论（授课教师：向胜军）求最短路径的一个例子求最短路径的一个例子 9/22/202455第四部分：图论（授课教师：向胜军）求最短路径的一个例子求最短路径的一个例子(续续) 9/22/202456第四部分：图论（授课教师：向胜军）求最短路径的一个例子求最短路径的一个例子(续续)v将计算过程用一张表描述出来：将计算过程用一张表描述出来： vksabcdefg01234567(0)1(1,s)22(2,s) 43(3,b)   9999(9,c)4444(4,s)88886(6,e)777666(6,c)W(T)01239466T=sT=saT=sbT=sbcT=sbcdT=seT=sefT=sbcg9/22/202457第四部分：图论（授课教师：向胜军）关键路径问题关键路径问题（（（（key paths problemkey paths problem））））vPERT图图 设设D=是是有有向向带带权权图图，，|V|=n，，若若D是是简简单单图图（（无无平平行行边边、、无无环环）），，无无回回路路。

有有一一个个顶顶点点入入度度为为0，，称称为为发发点点，，有有一一个个顶顶点点出出度度为为0，，称称为为收收点点边边的的权权wij表表示示 时时 间间 则则 称称 D为为 PERT图图 (Plan Evaluate Revise Technology Graph)v 关键路径关键路径(Key paths) 在在PERT图图中中求求关关键键路路径径，，就就是是求求从从发发点点到到收收点点的的一一条条最最长路径长路径，通过求各顶点的，通过求各顶点的最早完成时间最早完成时间来求关键路径来求关键路径9/22/202458第四部分：图论（授课教师：向胜军）v最早完成时间最早完成时间 自自发发点点v1开开始始沿沿最最长长路路径径到到达达vi所所需需时时间间，，称称为为vi的的最早完成时间最早完成时间，记作，记作TE(vi), i=1,2,…,n. 显显然然，，TE(v1)=0, vi(i 1)的的最最早早完完成成时时间间按按如如下公式计算：下公式计算：TE(vi)=max{TE(vj)+wij}, i=2,3,…,n. vj TD-(vi) 收点的收点的TE(vn)就是从就是从v1到到vn的最长路径的权。

的最长路径的权9/22/202459第四部分：图论（授课教师：向胜军）v最晚完成时间最晚完成时间 在在保保证证收收点点vn的的最最早早完完成成时时间间不不增增加加的的条条件件下下，，自自v1最最迟迟到到达达vi的的时时间间，，称称为为vi的的最最晚晚完完成成时时间间，，记作记作TL(vi). 显显然然，，TL(vn)=TE(vn). i n时时的的最最晚晚完完成成时时间间按如下公式计算：按如下公式计算：TL(vi)=min{TL(vj)-wij}, i=n-1,…,2,1. vj TD+(vi)9/22/202460第四部分：图论（授课教师：向胜军）v缓冲时间缓冲时间ES(vi)=TL(vi)-TE(vi), i=1,2,…,n.注注：：在在关关键键路路径径上上，，任任何何工工序序如如果果耽耽误误了了时时间间t，，整整个个工工程程就就耽耽误误了了时时间间t，，因因而而在在关关键键路路径径上上各各顶顶点点的的缓缓冲冲时时间间均均为为0即即若若vi为为关关键键路径上的顶点，则路径上的顶点，则TL(vi)=TE(vi)9/22/202461第四部分：图论（授课教师：向胜军）求关键路径的一个例子求关键路径的一个例子 414046323411v2v5v1v3v7v8v4v629/22/202462第四部分：图论（授课教师：向胜军）求关键路径的一个例子求关键路径的一个例子(续续)v各顶点的最早完成各顶点的最早完成时间如下：时间如下：TE(v1)=0; TE(v2)=max{0+1}=1;TE(v3)=max{0+2, 1+0}=2;TE(v4)=max{0+3, 2+2}=4;TE(v5)=max{1+3, 4+4}=8;TE(v6)=max{2+4, 8+1}=9;TE(v7)=max{1+4, 2+4}=6;TE(v8)=max{9+1, 6+6}=12.v各顶点的最晚完成时间各顶点的最晚完成时间如下：如下：TL(v8)=12; TL(v7)=min{12-6}=6;TL(v6)=min{12-1}=11;TL(v5)=min{11-1}=10;TL(v4)=min{10-4}=6;TL(v3)=min{6-2, 11-4, 6-4}=2;TL(v2)=min{2-0, 10-3, 6-4}=2;TL(v1)=min{2-1, 2-2, 6-3}=0.9/22/202463第四部分：图论（授课教师：向胜军）求关键路径的一个例子求关键路径的一个例子(续续)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.9/22/202464第四部分：图论（授课教师：向胜军）作业作业–编一个程序实现编一个程序实现Dijstra算法算法9/22/202465第四部分：图论（授课教师：向胜军）。