第七图的基本概念

第七图的基本概念第1页，课件共104页，创作于2023年2月

图论（graphictheory）的起源可追溯到18世纪，数学家欧拉1736年发表了关于图论的第一篇论文，解决了著名的哥尼斯堡七桥问题。但直到20世纪中后期，尤其是计算机科学与技术的发展，图的理论研究和应用研究才得到广泛的重视，图论作为一个重要的数学分支，才真正确立了自己的地位。第2页，课件共104页，创作于2023年2月图论的内容十分丰富,是一门交叉性很强、应用很广泛的学科。计算机科学、网络理论、信息论、运筹学、语言学、物理、化学等都以图作为工具,来解决理论问题和实际问题。离散数学研究的图是不同于几何图形、机械图形的另一种数学结构,不关心图中顶点的位置、边的长短和形状,只关心顶点与边的联结关系。第3页，课件共104页，创作于2023年2月目录7.1无向图及有向图7.2通路、回路、图的连通性7.3图的矩阵表示7.4最短路径问题及关键路径

第4页，课件共104页，创作于2023年2月7.1无向图及有向图设A,B为两集合,称

{{a,b}｜a∈A∧b∈B}为A与B的无序积,记作A＆B．将无序对{a,b}记作(a,b).第5页，课件共104页，创作于2023年2月定义7.1

一个无向图G是一个二元组<V,E>,即G＝<V,E>,其中,(1)V是一个非空的集合,称为G的顶点集,V中元素称为顶点或结点；

(2)E是无序积V＆V的一个多重子集,称E为G的边集,E中元素称为无向边或简称边.无向图元素可重复出现的集合为多重集第6页，课件共104页，创作于2023年2月例如：G=<V,E>,V={v1,v2,v3,v4,v5},E={(v1,v2),(v2,v2),(v2,v3),(v1,v3),(v1,v3),(v1,v4)}G的图形为：e5v5v4v3v2v1e4e3e2e1e6第7页，课件共104页，创作于2023年2月有向图定义7.2一个有向图D是一个二元组<V,E>,即D＝<V,E>,其中,(1)V同无向图中的顶点集；

(2)E是卡氏积的多重子集,其元素称为有向边,也简称边.有时用V(D),E(D)分别表示图D的顶点集和边集。第8页，课件共104页，创作于2023年2月例如：D=<V,E>,V={v1,v2,v3,v4,v5},E={<v1,v1>,<v3,v2>,<v3,v2>,<v3,v4>,<v2,v4>,<v4,v5>,<v5,v4>,<v1,v2>}G的图形为：e5v5v4v3v2v1e4e3e2e1e6e7e8第9页，课件共104页，创作于2023年2月设G＝<V,E>为一无向图或有向图

(1)若V,E都是有穷集合,则称G是有限图.(2)若｜V｜＝n,则称G为n阶图．

(3)若E＝,则称G为零图．特别是,若此时又有｜V｜＝1,则称G为平凡图.5阶图零图平凡图第10页，课件共104页，创作于2023年2月定义7.3设ek＝(vi,vj)为无向图G＝<V,E>中的一条边,称vi,vj为ek的端点,ek与vi(或vj)是彼此关联的.无边关联的顶点称为孤立点.若一条边所关联的两个顶点重合,则称此边为环.e5v5v4v3v2v1e4e3e2e1e6第11页，课件共104页，创作于2023年2月ek与vi(或vj)的关联次数1vi(vj)是ek的端点且vi≠vj,2vi(vj)是ek的端点且vi＝vj,0vi(vj)不是ek的端点e5v5v4v3v2v1e4e3e2e1e6第12页，课件共104页，创作于2023年2月定义7.4设无向图G=<V,E>,vi,vj∈V,ek,el∈E.(1)若存在一条边e以vi、vj为端点,即e=(vi,vj),则称vi,vj是彼此相邻的,简称相邻的．(2)若ek,el至少有一个公共端点,则称ek,el是彼此相邻的,简称相邻的．e5v5v4v3v2v1e4e3e2e1e6第13页，课件共104页，创作于2023年2月对有向图若ek＝〈vi,vj〉,除称vi,vj是ek的端点外,还称vi是ek的始点,vj是ek的终点,vi邻接到vj,vj邻接于vi.e5v5v4v3v2v1e4e3e2e1e6e7e8第14页，课件共104页，创作于2023年2月定义7.5设G＝<V,E>为一无向图,vi∈V,称vi作为边的端点的次数之和为vi的度数,简称度,记作d(vi).称度数为1的顶点为悬挂顶点,它所对应的边为悬挂边.v1v2v5v4v3d(vi)=?第15页，课件共104页，创作于2023年2月设D＝<V,E>为一有向图,vj∈V,称vj作为边的始点的次数之和,为vj的出度,记作d+(vj)；称vj作为边的终点的次数之和,为vj的入度,记作d-(vj)；称vj作为边的端点的次数之和,为vj的度数,简称度,记作d(vj).显然d(vj)＝d+(vj)＋d-(vj).第16页，课件共104页，创作于2023年2月d(v1)＝3，d+(v1)＝2，d-(v1)＝1；d(v2)＝3，d+(v2)＝2，d-(v2)＝1；d(v3)＝5，d+(v3)＝2，d-(v3)＝3；d(v4)＝d+(v4)＝d-(v4)＝0；d(v5)＝1，d+(v5)＝0，d-(v5)＝1；其中，v5是悬挂结点，<v1,v5>为悬挂边。例v5v1v2v3v4第17页，课件共104页，创作于2023年2月对于图G＝<V,E>,记Δ(G)＝max{d(v)｜v∈V},(G)＝min{d(v)｜v∈V},分别称为G的最大度和最小度.v1v2v5v4v3Δ＝4，＝0。第18页，课件共104页，创作于2023年2月若D＝〈V,E〉是有向图,除了Δ(D),(D)外,还有最大出度、最大入度、最小出度、最小入度,分别定义为v5v4v3v2v1第19页，课件共104页，创作于2023年2月定理7.1（握手定理）设图G＝<V,E>为无向图或有向图,V＝{v1,v2,...,vn},|E|=m(m为边数),则推论任何图(无向的或有向的)中,度为奇数的顶点个数为偶数.第20页，课件共104页，创作于2023年2月定理7.2设有向图D＝<V,E>,V＝{v1,v2,...,vn},｜E｜＝m,则设V＝{v1,v2,...,vn}为图G的顶点集,称(d(v1),d(v2),...,d(vn))为G的度数序列.第21页，课件共104页，创作于2023年2月例v1v2v5v4v3度数序列（4，4，3，1，0）度数序列（3，4，3，4，2）v5v4v3v2v1第22页，课件共104页，创作于2023年2月

(1)(3,3,2,3),(5,2,3,1,4)能成为图的度数序列吗？为什么？答：不能，由握手定理易知。

(2)已知图G中有10条边,4个3度顶点,其余顶点的度数均小于等于2.问G中至少有多少个顶点？为什么？答：至少有8个顶点。例第23页，课件共104页，创作于2023年2月定义7.6在无向图中,关联一对顶点的无向边如果多于1条,称这些边为平行边.平行边的条数称为重数.在有向图中,关联一对顶点的有向边如果多于1条,且它们的始点与终点相同,则称这些边为有向平行边,简称平行边.含平行边的图称为多重图.既不含平行边,也不含环的图称为简单图.第24页，课件共104页，创作于2023年2月e5v5v4v3v2v1e4e3e2e1e6

e4与e5是平行边

e3与e4是平行边

e7与e8不是平行边e5v5v4v3v2v1e4e3e2e1e6e7e8第25页，课件共104页，创作于2023年2月定义7.7设G=<V,E>是n阶无向简单图,若G中任何顶点都与其余的n-1个顶点相邻,则称G为n阶无向完全图,记作Kn.

设D=<V,E>为n阶有向简单图,若对于任意的顶点u,v∈V(u≠v),既有有向边<u,v>,又有<v,u>,则称D是n阶有向完全图.注：Kn均指无向完全图.第26页，课件共104页，创作于2023年2月图(1)中所示为K4,(2)所示为K5,(3)所示为3阶有向完全图.例(1)(2)(3)第27页，课件共104页，创作于2023年2月定义7.8设G=<V,E>,G'=<V',E'>是两个图.若V'V,且E'E,则称G'是G的子图,G是G'的母图,记做G'G.若G'G且G'≠G(即V'V或E'E),则G'是G的真子图.第28页，课件共104页，创作于2023年2月若G'G且V'=V则称G'是G的生成子图.设V1V,且V1≠,以V1为顶点集,以两端点均在V1中的全体边为边集的G的子图,称为V1导出的导出子图.

设E1

E,且E1≠,以E1为边集,以E1中关联的顶点的全体为顶点集的G的子图称为E1导出的导出子图.第29页，课件共104页，创作于2023年2月例下图给出了图G以及它的真子图G'和生成子图G''。G'是结点集{v1,v2,v4,v5,v6}的导出子图。第30页，课件共104页，创作于2023年2月v1v2v3v4e4e5e1e2e3v1v2v3v4e4e1e3v1v2e4e5v1

v2v3e4e1e2e3v1

v2v3e1e3v1v2e1例(1)(2)(3)(6)(5)(4)第31页，课件共104页，创作于2023年2月定义7.9设G=<V,E>是n阶无向简单图.以V为顶点集,以所有能使G成为完全图Kn的添加边组成的集合为边集的图,称为G相对于完全图Kn的补图,简称G的补图,记作G.

有向简单图的补图可类似定义.第32页，课件共104页，创作于2023年2月例互补互补第33页，课件共104页，创作于2023年2月观察下列图有何特点？图(a)、图(b)、图(c)和图(d)所表示的图形实际上都是一样的。bdcdcbadcbadcbaa图(a)图(b)图(c)图(d)第34页，课件共104页，创作于2023年2月定义7.10设两个无向图G1=<V1,E1>,G2=<V2,E2>,如果存在双射函数：V1→V2,使得对于任意的e=(vi,vj)∈E1当且仅当e'=((vi),(vj))∈E2,并且e与e'的重数相同,则称G1与G2是同构的,记作G1≌G2.第35页，课件共104页，创作于2023年2月(1)≌(2),顶点之间的对应关系为av1,bv2,cv3,dv4,ev5.第36页，课件共104页，创作于2023年2月(a)≌(b)≌(c)(a)所示图称为彼德森图.(a)(b)(c)1、顶点个数相同2、边的条数相同3、度数相同的结点数相同两图同构第37页，课件共104页，创作于2023年2月例(1)画出4个顶点3条边的所有可能非同构的无向简单图；

(1)(2)(3)第38页，课件共104页，创作于2023年2月(2)画出3个顶点2条边的所有可能非同构的有向简单图.(1)(2)(3)(4)第39页，课件共104页，创作于2023年2月7.2通路、回路、图的连通性定义7.11给定图G＝<V,E>.设G中顶点和边的交替序列为Γ＝v0e1v1e2…elvl,若Γ满足如下条件:vi-1和vi是ei的端点(在G是有向图时,要求vi-1是ei的始点,vi是ei的终点),i＝1,2,…,l,则称Γ为顶点v0到vl的通路.v0和vl分别称为此通路的起点和终点,Γ中边的数目l称为Γ的长度.

当v0＝vl时,此通路称为回路.第40页，课件共104页，创作于2023年2月若Γ中的所有边e1,e2,···,el互不相同,则称Γ为简单通路或一条迹.若回路中的所有边互不相同,称此回路为简单回路或一条闭迹.若通路的所有顶点v0,v1···,vl互不相同(从而所有边互不相同),则称此通路为初级通路或一条路径.若回路中,除v0＝vl外,其余顶点各不相同,所有边也各不相同,则称此回路为初级回路或圈.第41页，课件共104页，创作于2023年2月有边重复出现的通路称为复杂通路,有边重复出现的回路称为复杂回路.由定义可知,初级通路(回路)是简单通路(回路),但反之不真.注：上述定义既适合无向图，也适合有向图。第42页，课件共104页，创作于2023年2月例v1v0v4v2v3v5v8v6v7v1v0v4v2v3v1v0v4v2v3v1v0v4v2v3v5v8v6v7(1)为v0到v4的长为4的初级通路(2)为v0到v4的长为4的初级通路(3)为v0到v8的长为8的简单通路(4)为v0到v8的长为8的简单通路第43页，课件共104页，创作于2023年2月定理7.3在一个n阶图中,若从顶点vi到vj(vi≠vj)存在通路,则从vi到vj存在长度小于等于n-1的通路.推论在一个n阶图中,若从顶点vi到vj(vi≠vj)存在通路,则从vi到vj存在长度小于等于n-1的初级通路.第44页，课件共104页，创作于2023年2月定理7.4在一个n阶图中,如果存在vi到自身的回路,则从vi到自身存在长度小于等于n的回路.推论在一个n阶图中,如果vi到自身存在一条简单回路,则从vi到自身存在长度小于等于n的初级回路.第45页，课件共104页，创作于2023年2月定义7.12在一个无向图G中,若从顶点vi到vj存在通路(当然从vj到vi也存在通路),则称vi与vj是连通的.规定vi到自身总是连通的.

在一个有向图D中,若从顶点vi到vj存在通路,则称vi可达vj.规定vi到自身总是可达的.第46页，课件共104页，创作于2023年2月短程线(无向图)设vi,vj为无向图G中的任意两点,若vi与vj是连通的,则称vi与vj之间长度最短的通路为vi与vj之间的短程线,短程线的长度称为vi与vj之间的距离,记作d(vi,vj).短程线(有向图)设vi,vj为有向图D中任意两点,若vi可达vj,则称从vi到vj长度最短的通路为vi到vj的短程线,短程线的长度称为vi到vj的距离,记作d<vi,vj>.第47页，课件共104页，创作于2023年2月性质若vi不可达vj,规定d<vi,vj>＝∞.d<vi,vj>具有下面性质:(1)d<vi,vj>

≥0,当vi＝vj时,等号成立.(2)满足三角不等式,即

d<vi,vj>+d<vj,vk>≥d<vi,vk>.在无向图中,还有对称性,即

d(vi,vj)＝d(vj,vi).第48页，课件共104页，创作于2023年2月连通图(无向图)定义7.13若无向图G是平凡图,或G中任意两顶点都是连通的,则称G是连通图;否则,称G是非连通图.无向图中,顶点之间的连通关系是等价关系.设G为一个无向图,R是G中顶点之间的连通关系,按着R可将V(G)划分成k(k≥1)个等价类,记成V1,V2,···,Vk,由它们导出的导出子图G[V1],G[V2],…,G[Vk]称为G的连通分支,其个数记为p(G).第49页，课件共104页，创作于2023年2月G1是连通图，p(G1)＝1；G2是非连通图，且p(G2)＝3。G1G2例第50页，课件共104页，创作于2023年2月连通图(有向图)定义7.14设D是一个有向图,如果略去D中各有向边的方向后所得无向图G是连通图,则称D是连通图,或称D是弱连通图.若D中任意两顶点至少一个可达另一个,则称D是单向连通图.若D中任何一对顶点都是相互可达的,则称D是强连通图．第51页，课件共104页，创作于2023年2月例图a为弱连通图；图b为单向连通图；图c为强连通图。图a图b图c第52页，课件共104页，创作于2023年2月定义7.15设无向图G＝<V,E>,若存在顶点子集V'V,使G删除V'将V'中顶点及其关联的边都删除)后,所得子图G－V'的连通分支数与G的连通分支数满足

p(G-V')＞p(G),而删除V'的任何真子集V''后,p(G-V'')＝p(G),则称V'为G的一个点割集.若点割集中只有一个顶点v,则称v为割点.第53页，课件共104页，创作于2023年2月若存在边集子集E'E,使G删除E'(将E'中的边从G中全删除)后,所得子图的连通分支数与G的连通分支数满足p(G-E')＞p(G),而删除E'的任何真子集E''后,p(G-E'')＝p(G),则称E'是G的一个边割集.若边割集中只有一条边e,则称e为割边或桥.第54页，课件共104页，创作于2023年2月{v2,v7}，{v3}，{v4}为点割集，{v3}，{v4}为割点{e1,e2}，{e1,e3,e4}，{e6}，{e7,e8}，{e2,e3,e4}等都是割集，其中e6是桥。v5e8v6v7v1v4v2v3e1e2e3e4e5e6e7e9例第55页，课件共104页，创作于2023年2月本节概念:无向图、有向图、n阶图、零图、平凡图、彼此关联、相邻、度d(vi)、出度d+(vj)、入度d-(vj)、握手定理及其推论、度数序列、简单图、n阶无向完全图、子图、母图、生成子图、导出子图、补图、同构、通路、回路、连通图、点割集、边割集第56页，课件共104页，创作于2023年2月7.3图的矩阵表示

无向图的关联矩阵有向图的关联矩阵有向图的邻接矩阵有向图的可达矩阵

第57页，课件共104页，创作于2023年2月无向图的关联矩阵设无向图G＝<V,E>,V＝{v1,v2,···,vn},E＝{e1,e2,···,em},令mij为顶点vi与边ej的关联次数,则称(mij)n×m为G的关联矩阵,记为M(G)mij0(vi与ej无关),1(vi与ej关联1次),

(vi与ej关联2次,

即ej是以vi为端点的环)．第58页，课件共104页，创作于2023年2月例e2v4v2v3v1e3e4e1e5第59页，课件共104页，创作于2023年2月关联矩阵M(G)的性质第60页，课件共104页，创作于2023年2月第61页，课件共104页，创作于2023年2月有向图的关联矩阵要求有向图D中无环存在.设D＝<V,E>,V＝{v1,v2,···,vn},E＝{e1,e2,···em},令则称(mij)n×m为D的关联矩阵，记作M(D).第62页，课件共104页，创作于2023年2月v4v3v2v1e1e2e3e4e5例第63页，课件共104页，创作于2023年2月关联矩阵M(D)的性质第64页，课件共104页，创作于2023年2月有向图的邻接矩阵设有向图D＝<V,E>.V={v1,v2,···,vn},|E|＝m.令aij

(1)

为vi邻接到vj的边的条数,称(aij

(1))m×n为D的邻接矩阵,记作A(D).第65页，课件共104页，创作于2023年2月v4v3v2v1例第66页，课件共104页，创作于2023年2月邻接矩阵A(D)的性质第67页，课件共104页，创作于2023年2月(3)为D中边的总数,也可看成D中长度为1的通路总数,而为D中环的个数,即D中长度为1的回路总数.

第68页，课件共104页，创作于2023年2月考虑Al(D)(简记Al),=

这里Al=()n×n(l≥2),则为顶点vi到vj长度为l的通路数,为它到自身长度为l的回路数.Al中所有元素之和为D中长度为l的通路数,而Al中对角线上元素之和为D中始于(终于)各顶点的长度为l的回路数.第69页，课件共104页，创作于2023年2月在图中,计算A2,A3,A4如下:v4v3v2v1第70页，课件共104页，创作于2023年2月定理7.5设A为有向图D的邻接矩阵,V=｛v1,v2…,vn},则Al(l≥1)中元素为vi到vj长度为l的通路数,为D中长度为l的通路总数,其中为D中长度为l的回路数.第71页，课件共104页，创作于2023年2月推论设Br=A+A2+…+Ar(r≥1),则Br中元素为D中vi到vj长度小于等于r的通路数,为D中长度小于等于r的通路总数,其中为D中长度小于等于r的回路总数.若再令矩阵

B1=A,B2=A+A2,……Br=A+A2+…+Ar,第72页，课件共104页，创作于2023年2月有向图的可达矩阵

设D=<V,E>为一有向,V={v1,v2,…,vn},令

pii=1,i=1,2,…,n.称(pij)n×n为D的可达矩阵,记作P(D),简记P.第73页，课件共104页，创作于2023年2月v4v3v2v1P=例第74页，课件共104页，创作于2023年2月P中元素可如下确定:

于是由D的邻接矩阵可求可达矩阵.第75页，课件共104页，创作于2023年2月7.4最短路径及关键路径

1.最短路径问题

2.关键路径问题第76页，课件共104页，创作于2023年2月权、带权图对于有向图或无向图G的每条边附加一个实数w(e)，则称w(e)为边e上的权.G连同附加在各边上的实数称为带权图.常记带权图为G=<V,E,W>.第77页，课件共104页，创作于2023年2月设G1是带权图G的子图,称为G1的权,记作W(G1).当然,W(G)是G的权.当无向边e=(vi,vj)或有向边e=<vi,vj>时,w(e)也记为wij.E(G1)第78页，课件共104页，创作于2023年2月最短路径问题

设带权图G=<V,E,W>.G中每条边带的权均大于等于0.u,v为G中任意两个顶点,从u到v的所有通路中带权最小的通路称为u到v的最短路径.设G=<V,E,W>是n阶简单带权图,wij≥0.若顶点vi与vj不相邻,令wij=∞.求G中顶点v1到其余各顶点的最短路径.第79页，课件共104页，创作于2023年2月路径长度的的具体含义取决于边上权值所代表的意义。

【例】交通网络中的带权图求最短路径的问题。

（1）两地之间是否有路相通?

（2）在有多条通路的情况下，哪一条最短?

其中，交通网络可以用带权图表示：图中顶点表示城镇，边表示两个城镇之间的道路，边上的权值可表示两城镇间的距离，交通费用或途中所需的时间等等。

第80页，课件共104页，创作于2023年2月第81页，课件共104页，创作于2023年2月(1)设为顶点v1到顶点vi最短路径的权,若顶点vi获得了标号,称vi在第r步获得了p标号(永久性标号),其中,r≥0.

(2)设为v1到vj的最短路径权的上界,若vj获得,在第r步获得t标号(临时性标号),r≥0.若干定义：第82页，课件共104页，创作于2023年2月(3)设Pr={v|v已获得p标号}为第r步通过集,r≥0.(4)设Tr=V-Pr为第r步未通过集,r≥0.第83页，课件共104页，创作于2023年2月Dijkstra(标号法）的算法：开始,r←0,v1获p标号:=0,P0={v1},T0=V-{v1}.vj(j≠1)的t标号:=w1j.

①求下一个p标号顶点.

设,将标在相应顶点vi处,表明vi获得p标号.修改通过集和未通过集:Pr=Pr-1∪{vi},Tr=Tr-1-{vi}.,

查Tr:若Tr=,则算法结束,否则转②.第84页，课件共104页，创作于2023年2月②修改Tr中各顶点的t标号:

是刚刚获得标号顶点的p标号.令r←r+1,转①.第85页，课件共104页，创作于2023年2月求图中顶点v0与v5的最短路径.

例解:可以将计算过程用一张表表示出来(见下页表)31v5v3v2v154712v02v46第86页，课件共104页，创作于2023年2月31v5v3v2v154712v0

2v46

vi

Kv0v1v2v3v4v5012345011/v0433/v1∞8877/v4∞644/v2∞∞

∞1099/v3013749第87页，课件共104页，创作于2023年2月由表可知,v5与v3相邻,v3与v4相邻,v4与v2相邻,v2与v1相邻,v1与v0相邻.这样从v5往前追踪,得v0到v5的最短路径为

Γ=v0v1v2v4v3v5.W(Γ)=9.

31v5v3v2v154712v02v46第88页，课件共104页，创作于2023年2月设D=<V,E>为一个有向图,v∈V,称为v的后继元集;为v的先驱元集.2.关键路径问题第89页，课件共104页，创作于2023年2月（1）PERT图（计划评审技术图）设D=<V,E>是n阶有向带权图,满足:1)D是简单图;2)D中无回路;3)有一个顶点入度为0,称此顶点为发点;有一个顶点出度为0,称此顶点为收点;4)记边<vi,vj>带的权为wij;它常表示时间;则称D为PERT图.第90页，课件共104页，创作于2023年2月通常把计划、施工过程、生产流程、程序流程的都当成一个工程。除了很小的工程外、一般都把工程分为若干个叫做“活动”的子工程。完成了这些“活动”的子工程，这个工程就可以完成了。

通常我们用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边

<vi,vj>表示活动vi必须先于活动vj进行。

这种的有向图叫做用边表示活动的网络，简称AOE（activeonedges）网络。

第91页，课件共104页，创作于2023年2月AOE网络在某些工程估算方面非常有用。他可以使人们了解：

（1）：研究某个工程至少需要多少时间？

（2）：那些活动是影响工程进度的关键？

在AOE网络中，有些活动可以并行的进行。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。因此，完成整个工程所需的时间取决于从发点到收点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度就叫做关键路径（criticalpath）。第92页，课件共104页，创作于2023年2月

1956年，美国杜邦公司提出关键路径法，并于1957年首先用于1000万美圆化工厂建设，工期比原计划缩短了4个月。杜邦公司在采用关键路径法的一年中，节省了100万美圆。

案例第93页，课件共104页，创作于2023年2月自发点(记为v1)开始沿最长路径到达vi所需要的时间,称为vi的最早完成时间,记作

TE(vi),i=1,2,…,n.vi(i≠1)的最早完成时间可按如下公式计算:

收点vn的最早完成时间TE(vn)就是从v1到vn的最长路径的权.（2）最早完成时间第94页，课件共104页，创作于2023年2月在保证收点vn的最早完成时间不增加的条件下,自v1最迟到达vi的时间称为vi的最晚完成时间,记作TL(vi).TL(vn)=TE(vn).i≠n时,vi的最晚完成时间由下面公式计算:

（3）最晚完成时间第95页，课件共104页，创作于2023年2月称TL(vi)-TE(vi)为vi的缓冲时间,记作

ES(vi)=TL(vi)-TE(vi)i=1,2,…,n

在关键路径上各顶点的缓冲时间均为0.（4）缓冲时间第96页，课件共104页，创作于2023年2月求所示PERT图中各顶点的最早、最晚和缓冲时间以及关键路径.31v5v3v4v234416v12v60v8v71442例第97页，课件共104页，创作于2023年2月解(1)各顶点的最早完成时间: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