07图的基本概念

图论（1）--图的基本概念有向图和⽆向图的建⽴以及赋权图引⼊Q：什么是图论？A：图论是数学的⼀个分⽀。

它以图为研究对象。

图论中的图是由若⼲给定的点及连接两点的线所构成的图形，这种图形通常⽤来描述某些事物之间的某种特定关系，⽤点代表事物，⽤连接两点的线表⽰相应两个事物间具有这种关系。

现在我们来探讨⽆向图和有向图的概念以及如何去建⽴最基本的图的模型什么是图对于初⼊图论的⼈来说，复杂的定义可能会直接劝退他们，现在我来举⼀个⾮常简单的例⼦。

这就是最常见的图，由于它没有指向，即没有明确的⽅向，它被称为⽆向图。

图是由顶点和边组成的，你应该很容易就知道那些元素是顶点，那些是边。

下⾯的具有⽅向的便是有向图：若有的边有向，有的边⽆向，则称为混合图。

接下来我们将引⼊更多的概念：若两个顶点有边相连，则称两个顶点相相邻，两个点称为起点/终点或端点如1指向2，则这两个顶点相邻，这两个顶点被称为断点，⽽1被称为起点，2被称为终点。

仅含⼀个顶点的边称为⾃环在⽆向图中，包含顶点v的边的个数，称为顶点的度。

在有向图中，以v为起点的边的个数，称为点的出度，以v为终点的边的个数，称为顶点的⼊度。

⽆向图的建⽴建⽴简单⽆向图，我们使⽤Matlab，版本为R2017a。

% 函数graph(s,t)：可在 s 和 t 中的对应节点之间创建边，并⽣成⼀个图% s 和 t 都必须具有相同的元素数；这些节点必须都是从1开始的正整数，或都是字符串元胞数组。

s1 = [1,2,3,4]; %s为顶点，必须保证连续且从1开始的正整数t1 = [2,3,1,1]; %边 s与t之间是⼀⼀对应的G1 = graph(s1, t1);plot(G1) %画出效果图效果图：带汉字的⽆向图：% 注意字符串元胞数组是⽤⼤括号包起来的哦s2 = {'学校','电影院','⽹吧','酒店'};t2 = {'电影院','酒店','酒店','KTV'};G2 = graph(s2, t2);plot(G2, 'linewidth', 2) % 设置线的宽度% 下⾯的命令是在画图后不显⽰坐标set( gca, 'XTick', [], 'YTick', [] );效果图：有向图的建⽴：% ⽆权图 digraph(s,t)s = [1,2,3,4,1];t = [2,3,1,1,4];G = digraph(s, t);plot(G)set( gca, 'XTick', [], 'YTick', [] );注意边的顺序和⽅向，依次为1指向2,2指向3,3指向1,4指向1和1指向4效果图：赋权图的建⽴：赋权图，每条边都有⼀个⾮负实数对应的图。

图论--图的基本概念1.图：1.1⽆向图的定义：⼀个⽆向图G是⼀个有序的⼆元组<V,E>，其中V是⼀个⾮空有穷集，称作顶点集，其元素称作顶点或结点。

E是⽆序积V&V的有穷多重⼦集，称作边集，其元素称作⽆向边，简称边。

注意：元素可以重复出现的集合称作多重集合。

某元素重复出现的次数称作该元素的重复度。

例如，在多重集合{a,a,b,b,b,c,d}中，a,b,c,d的重复度分别为2，3，1，1。

从多重集合的⾓度考虑，⽆元素重复出现的集合是各元素重复度均为1的多重集。

1.2有向图的定义：⼀个有向图G是⼀个有序的⼆元组<V,E>，其中V是⼀个⾮空有穷集，称作顶点集，其元素称作顶点或结点。

E是笛卡尔积V✖V的有穷多重⼦集，称作边集，其元素为有向边，简称为边。

通常⽤图形来表⽰⽆向图和有向图：⽤⼩圆圈（或实⼼点）表⽰顶点，⽤顶点之间的连线表⽰⽆向边，⽤带箭头的连线表⽰有向边。

与1.1，1.2有关的⼀些概念和定义：（1）⽆向图和有向图统称为图，但有时也把⽆向图简称作图。

通常⽤G表⽰⽆向图，D表⽰有向图，有时也⽤G泛指图（⽆向的或有向的）。

⽤V(G),E(G)分别表⽰G的顶点集和边集，|V(G)|,|E(G)|分别是G的顶点数和边数，有向图也有类似的符号。

（2）顶点数称作图的阶，n个顶点的图称作n阶图。

（3）⼀条边也没有的图称作零图，n阶零图记作N n。

1阶零图N1称作平凡图。

平凡图只有⼀个顶点，没有边。

（4）在图的定义中规定顶点集V为⾮空集，但在图的运算中可能产⽣顶点集为空集的运算结果，为此规定顶点集为空集的图为空图，并将空图记作Ø。

（5）当⽤图形表⽰图时，如果给每⼀个顶点和每⼀条边指定⼀个符号（字母或数字，当然字母还可以带下标），则称这样的图为标定图，否则称作⾮标定图。

（6）将有向图的各条有向边改成⽆向边后所得到的⽆向图称作这个有向图的基图。

（7）若两个顶点v i与v j之间有⼀条边连接，则称这两个顶点相邻。

《离散数学》第七章图的基本概念讲稿7.1 ⽆向图及有向图⼀、本节主要内容⽆向图与有向图顶点的度数握⼿定理简单图完全图⼦图补图⼆、教学内容⽆序对: 两个元素组成的⼆元组（没有顺序），即⽆论a,b是否相同，（a,b ）＝（b, a ）⽆序积: A与B 为两个集合，A&B={(x,y) |x∈A∧y∈B}例A={a1, a2}, B={b1, b2}A&B={(a1 , b1 ), (a1 , b2 ) ,(a2 , b1 ) ,(a2 , b2 )}A&A={(a1 , a1 ), (a1 , a2 ) ,(a2 , a2 )}多重集合: 元素可以重复出现的集合⽆向图与有向图定义⽆向图G=, 其中(1) V?≠为顶点集，元素称为顶点(2) E为V&V的多重⼦集，其元素称为⽆向边，简称边.例如, G=如图所⽰,其中V={v1, v2, …,v5},E={(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5)}定义⽆向图G=, 其中(1) V≠?为顶点集，元素称为顶点(2) E为V&V的多重⼦集，其元素称为⽆向边，简称边.例如, G=如图所⽰,其中V={v1, v2, …,v5},E={(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5)} ⽆向图与有向图(续)定义有向图D=, 其中(1) V同⽆向图的顶点集, 元素也称为顶点(2) E为V?V的多重⼦集，其元素称为有向边，简称边.⽤⽆向边代替D的所有有向边所得到的⽆向图称作D的基图右图是有向图，试写出它的V和E⽆向图与有向图(续)通常⽤G表⽰⽆向图, D表⽰有向图,也常⽤G泛指⽆向图和有向图,⽤ek表⽰⽆向边或有向边.V(G), E(G), V(D), E(D): G和D的顶点集, 边集.n 阶图: n个顶点的图有限图: V, E都是有穷集合的图零图: E=?平凡图: 1 阶零图顶点和边的关联与相邻定义设ek=(vi, vj)是⽆向图G=的⼀条边, 称vi, vj为ek的端点, ek与vi ( vj)关联.若vi ≠ vj, 则称ek与vi ( vj)的关联次数为1;若vi = vj, 则称ek为环, 此时称ek与vi 的关联次数为2;若vi不是ek端点, 则称ek与vi 的关联次数为0.⽆边关联的顶点称作孤⽴点.定义设⽆向图G=, vi,vj∈V,ek,el∈E,若(vi,vj) ∈E, 则称vi,vj相邻;若ek,el⾄少有⼀个公共端点, 则称ek,el相邻.对有向图有类似定义. 设ek=?vi,vj?是有向图的⼀条边, vi,vj是ek端点,⼜称vi 是ek的始点, vj是ek的终点,vi邻接到vj, vj邻接于vi.邻域和关联集设⽆向图G , v ∈V(G)v 的邻域 N(v)={u|u ∈V(G)∧(u,v)∈E(G)∧u ≠v} v 的闭邻域 = N(v)∪{v} v 的关联集 I(v)={e|e ∈E(G)∧e 与v 关联} 设有向图D, v ∈V(D)v 的后继元集 ={u|u ∈V(D)∧∈E(G)∧u ≠v}v 的先驱元集 ={u|u ∈V(D)∧∈E(G)∧u ≠v}v 的邻域v 的闭邻域顶点的度数设G=为⽆向图, v ∈V,v 的度数(度) d(v): v 作为边的端点的次数之和悬挂顶点: 度数为1的顶点悬挂边: 与悬挂顶点关联的边 G 的最⼤度?(G)=max{d(v)| v ∈V} G 的最⼩度δ(G)=min{d(v)| v ∈V} 例如 d(v5)=3, d(v2)=4, d(v1)=4, ?(G)=4, δ(G)=1,v4是悬挂顶点, e7是悬挂边, e1是环顶点的度数(续)设D=为有向图, v ∈V,v 的出度d+(v): v 作为边的始点的次数之和 v 的⼊度d -(v): v 作为边的终点的次数之和 v 的度数(度) d(v): v 作为边的端点次数之和 d(v)= d+(v)+ d-(v)D 的最⼤出度?+(D), 最⼩出度δ+(D) 最⼤⼊度?-(D), 最⼩⼊度δ-(D) 最⼤度?(D), 最⼩度δ(D) 例如 d+(a)=4, d-(a)=1, d(a)=5, d+(b)=0, d-(b)=3, d(b)=3,+(D)=4, δ+(D)=0, ?-(D)=3, δ-(D)=1, ?(D)=5, δ(D)=3. 图论基本定理——握⼿定理定理任意⽆向图和有向图的所有顶点度数之和都等于边数的2倍, 并且有向图的所有顶点⼊度之和等于出度之和等于边数.)(v N )(v D +Γ)(v D -Γ)()()(v v v N D D D -+ΓΓ= }{)()(v v N v N D D =证 G 中每条边（包括环）均有两个端点，所以在计算G 中各顶点度数之和时，每条边均提供2度，m 条边共提供2m 度.有向图的每条边提供⼀个⼊度和⼀个出度, 故所有顶点⼊度之和等于出度之和等于边数. 握⼿定理(续)推论在任何⽆向图和有向图中，度为奇数的顶点个数必为偶数. 证设G=为任意图，令 V1={v | v ∈V ∧d(v)为奇数} V2={v | v ∈V ∧d(v)为偶数}则V1∪V2=V, V1∩V2=?，由握⼿定理可知∑∑∑∈∈∈+==21)()()(2V v V v Vv v d v d v d m由于2m,∑∈2)(V v v d 均为偶数，所以 ∑∈1)(V v v d 也为偶数, 但因为V1中顶点度数都为奇数，所以|V1|必为偶数.图的度数列设⽆向图G 的顶点集V={v1, v2, …, vn} G 的度数序列: d(v1), d(v2), …, d(vn) 如右图度数序列:4,4,2,1,3设有向图D 的顶点集V={v1, v2, …, vn} D 的度数序列: d(v1), d(v2), …, d(vn) D 的出度序列: d+(v1), d+(v2), …, d+(vn) D 的⼊度序列: d -(v1), d -(v2), …, d -(vn) 如右图度数序列:5,3,3,3出度序列:4,0,2,1 ⼊度序列:1,3,1,2 握⼿定理的应⽤例1 (3,3,3,4), (2,3,4,6,8)能成为图的度数序列吗? 解不可能. 它们都有奇数个奇数.例2 已知图G 有10条边, 4个3度顶点, 其余顶点的度数均⼩于等于2, 问G ⾄少有多少个顶点? 解设G 有n 个顶点. 由握⼿定理, 4?3+2?(n-4)≥2?10 解得 n ≥8握⼿定理的应⽤(续)例3 给定下列各序列,哪组可以构成⽆向图的度数序列 (2,2,2,2,2) (1,1,2,2,3) (1,1,2,2,2) (1,3,4,4,5)多重图与简单图定义(1) 在⽆向图中,如果有2条或2条以上的边关联同⼀对顶点, 则称这些边为平⾏边, 平⾏边的条数称为重数.(2)在有向图中,如果有2条或2条以上的边具有相同的始点和终点, 则称这些边为有向平⾏边, 简称平⾏边, 平⾏边的条数称为重数.(3) 含平⾏边的图称为多重图.(4) 既⽆平⾏边也⽆环的图称为简单图.注意:简单图是极其重要的概念多重图与简单图(续)例如e5和e6 是平⾏边重数为2不是简单图e2和e3 是平⾏边,重数为2 e6和e7不是平⾏边不是简单图图的同构定义设G1=, G2=为两个⽆向图(有向图), 若存在双射函数f: V1→V2, 使得对于任意的vi,vj∈V1,(vi,vj)∈E1（∈E1）当且仅当(f(vi),f(vj))∈E2（∈E2），并且,(vi,vj)（）与(f(vi),f(vj))（）的重数相同，则称G1与G2是同构的，记作G1?G2.图的同构(续)⼏点说明：图之间的同构关系具有⾃反性、对称性和传递性.能找到多条同构的必要条件, 但它们都不是充分条件:①边数相同，顶点数相同②度数列相同(不计度数的顺序)③对应顶点的关联集及邻域的元素个数相同，等等若破坏必要条件，则两图不同构图的同构(续)例1 试画出4阶3条边的所有⾮同构的⽆向简单图例2 判断下述每⼀对图是否同构:(1)度数列不同不同构例2 (续)(2)不同构⼊(出)度列不同度数列相同但不同构为什么?完全图与正则图n阶⽆向完全图Kn: 每个顶点都与其余顶点相邻的n阶⽆向简单图.简单性质: 边数m=n(n-1)/2, ?=δ=n-1n阶有向完全图: 每对顶点之间均有两条⽅向相反的有向边的n阶有向简单图.简单性质: 边数m=n(n-1), ?=δ=2(n-1),+=δ+=?-=δ-=n-1n阶k正则图: ?=δ=k 的n阶⽆向简单图简单性质: 边数m=nk/2完全图与正则图(续)(1) 为5阶⽆向完全图K5(2) 为3阶有向完全图(3) 为彼得森图, 它是3 正则图⼦图定义设G=, G '=是2个图(1) 若V '?V且E '?E, 则称G '为G的⼦图, G为G '的母图, 记作G '?G(2)若G '?G且G '≠ G（即V '?V 或E '?E），称G '为G的真⼦图(3) 若G '?G 且V '=V，则称G '为G的⽣成⼦图(4) 设V '?V 且V '≠?, 以V '为顶点集, 以两端点都在V '中的所有边为边集的G的⼦图称作V '的导出⼦图，记作G[V '](5) 设E '?E且E '≠?, 以E '为边集, 以E '中边关联的所有顶点为顶点集的G的⼦图称作E '的导出⼦图, 记作G[E ']⼦图(续)例画出K4的所有⾮同构的⽣成⼦图补图定义设G=为n阶⽆向简单图，以V为顶点集,所有使G成为完全图Kn的添加边组成的集合为边集的图，称为G的补图，记作G?G.若G ? G , 则称G 是⾃补图.例画出5阶7条边的所有⾮同构的⽆向简单图⾸先，画出5阶3条边的所有⾮同构的⽆向简单图然后，画出各⾃的补图7.2 通路、回路与图的连通性⼀、本节主要内容简单通(回)路, 初级通(回)路, 复杂通(回)路⽆向连通图, 连通分⽀弱连通图, 单向连通图, 强连通图点割集与割点边割集与割边(桥) ⼆、教学内容通路与回路定义给定图G=（⽆向或有向的），设G 中顶点与边的交替序列Γ=v0e1v1e2…elvl ，(1) 若?i(1≤i ≤l), vi -1 和 vi 是ei 的端点(对于有向图, 要求vi -1是始点, vi 是终点), 则称Γ为通路, v0是通路的起点, vl 是通路的终点, l 为通路的长度. ⼜若v0=vl ，则称Γ为回路. (2) 若通路(回路)中所有顶点(对于回路, 除v0=vl)各异，则称为初级通路(初级回路).初级通路⼜称作路径, 初级回路⼜称作圈.(3) 若通路(回路)中所有边各异, 则称为简单通路(简单回路), 否则称为复杂通路(复杂回路). 通路与回路(续) 说明:在⽆向图中，环是长度为1的圈, 两条平⾏边构成长度为2的圈. 在有向图中，环是长度为1的圈, 两条⽅向相反边构成长度为2的圈. 在⽆向简单图中, 所有圈的长度≥3; 在有向简单图中, 所有圈的长度≥2. 通路与回路(续)定理在n 阶图G 中，若从顶点vi 到vj （vi ≠vj ）存在通路，则从vi 到vj 存在长度⼩于等于n -1的通路.推论在n 阶图G 中，若从顶点vi 到vj （vi ≠vj ）存在通121212G G G G G G ??例设与均为⽆向简单图，当且仅当路，则从vi到vj存在长度⼩于等于n-1的初级通路.定理在⼀个n阶图G中，若存在vi到⾃⾝的回路，则⼀定存在vi到⾃⾝长度⼩于等于n的回路.推论在⼀个n阶图G中，若存在vi到⾃⾝的简单回路，则⼀定存在长度⼩于等于n的初级回路.⽆向图的连通性设⽆向图G=,u与v连通: 若u与v之间有通路. 规定u与⾃⾝总连通.连通关系R={| u,v ∈V且u~v}是V上的等价关系连通图: 平凡图, 或者任意两点都连通的图连通分⽀: V关于R的等价类的导出⼦图设V/R={V1,V2,…,Vk}, G[V1], G[V2], …,G[Vk]是G的连通分⽀, 其个数记作p(G)=k.G是连通图? p(G)=1u与v之间的短程线: 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=vd(u,v)=d(v,u)（对称性）d(u,v)+d(v,w)≥d(u,w) （三⾓不等式)点割集记G-v: 从G中删除v及关联的边G-V': 从G中删除V'中所有的顶点及关联的边G-e : 从G中删除eG-E': 从G中删除E'中所有边定义设⽆向图G=, 如果存在顶点⼦集V'?V, 使p(G-V')>p(G)，⽽且删除V'的任何真⼦集V''后（? V''?V'），p(G-V'')=p(G), 则称V'为G的点割集. 若{v}为点割集, 则称v为割点.点割集(续)例{v1,v4}, {v6}是点割集, v6是割点.{v2,v5}是点割集吗？边割集定义设⽆向图G=, E'?E, 若p(G-E')>p(G)且?E''?E',p(G-E'')=p(G), 则称E'为G的边割集. 若{e}为边割集, 则称e为割边或桥.在上⼀页的图中，{e1,e2}，{e1,e3,e5,e6}，{e8}等是边割集，e8是桥，{e7,e9,e5,e6}是边割集吗？⼏点说明：Kn⽆点割集n阶零图既⽆点割集，也⽆边割集.若G连通，E'为边割集，则p(G-E')=2若G连通，V'为点割集，则p(G-V')≥2有向图的连通性设有向图D=u可达v: u到v有通路. 规定u到⾃⾝总是可达的.可达具有⾃反性和传递性D弱连通(连通): 基图为⽆向连通图D单向连通: ?u,v∈V，u可达v 或v可达uD强连通: ?u,v∈V，u与v相互可达强连通?单向连通?弱连通有向图的连通性(续)例下图(1)强连通, (2)单连通, (3) 弱连通有向图的短程线与距离u到v的短程线: u到v长度最短的通路(u可达v)u与v之间的距离d: u到v的短程线的长度若u不可达v, 规定d=∞.性质：d+d ≥d注意: 没有对称性7.3 图的矩阵表⽰⼀、本节主要内容⽆向图的关联矩阵有向图的关联矩阵有向图的邻接矩阵有向图的可达矩阵⼆、教学内容⽆向图的关联矩阵定义设⽆向图G=, V={v1, v2, …, vn}, E={e1, e2, …, em}, 令mij为vi与ej的关联次数，称(mij)n?m为G的关联矩阵，记为M(G).定义设⽆向图G=, V={v1, v2, …, vn}, E={e1, e2, …, em}, 令mij为vi与ej的关联次数，称(mij)n?m为G的关联矩阵，记为M(G).性质关联次数为可能取值为0，1，2有向图的关联矩阵定义设⽆环有向图D=, V={v1, v2, …, vn}, E={e1, e2, …, em}, 令则称(mij)n ?m 为D 的关联矩阵，记为M(D). 性质:有向图的邻接矩阵定义设有向图D=, V={v1, v2, …, vn}, E={e1, e2, …, em}, 令 )1(ij a 为顶点vi 邻接到顶点vj 边的条数，称()1(ij a )n ?n 为D 的邻接矩阵, 记作A(D), 简记为A. 1110001110()1001200000M G=1100010111()0000101110M D ---?=-??-??平⾏边的列相同)4(2)3(),...,2,1()()2(),...,2,1(2)1(,11mm n i v d m m j m ji ijimj ijni ij =====∑∑∑==(1)1(1)1(1)(),1,2,...,(2)(),1,2,...,nij i j n ij ji a d vi n a d v j n+=-=====∑∑性质D 中的通路及回路数定理设A 为n 阶有向图D 的邻接矩阵, 则Al(l ≥1)中元素)(l ij a 为D 中vi 到vj 长度为 l 的通路数， )(l ii a 为vi 到⾃⾝长度为 l 的回路数，∑∑==n i nj l ija11)( 为D 中长度为 l 的通路总数，∑=ni l iia1)( 为D 中长度为 l 的回路总数.D 中的通路及回路数(续)推论设Bl=A+A2+…+Al(l ≥1), 则Bl 中元素为D 中长度⼩于或等于l 的通路数，为D 中长度⼩于或等于l 的回路数. 例有向图D 如图所⽰, 求A, A2, A3, A4, 并回答问题：(1) D 中长度为1, 2, 3, 4的通路各有多少条？其中回路分别为多少条？ (2) D 中长度⼩于或等于4的通路为多少条？其中有多少条回路？12100010()00010010A D=有向图的可达矩阵定义设D=为有向图, V={v1, v2, …, vn}, 令称(pij)n ?n 为D 的可达矩阵, 记作P(D), 简记为P. 性质:P(D)主对⾓线上的元素全为1.D 强连通当且仅当P(D)的元素全为1. 有向图的可达矩阵(续)例右图所⽰的有向图D 的可达矩阵为7.4 最短路径及关键路径⼀、本节主要内容最短路关键路线⼆、教学内容对于有向图或⽆向图G 的每条边，附加⼀个实数w(e)，则称w(e)为边e 上的权. G 连同附加在各边上的实数，称为带权图.设带权图G=,G 中每条边的权都⼤于等于0.u,v 为G 中任意两个顶点，从u 到v 的所有通=1101110111110001P路中带权最⼩的通路称为u 到v 的最短路径.求给定两个顶点之间的最短路径，称为最短路径问题. 算法：Dijkstra(标号法){}()*()*1()*()()1()*1.2./5.i r r i i i i ir i r r j j j j j r i r v l v v v l v r p l l v v v l v r l v v p r T V r ∞==-j ij r r 如果顶点与v 不相邻，则w =为顶点到顶点最短路径的权，如果顶点获得了标号，则称顶点在第步获得了标号（永久性标号）3.为顶点到顶点最短路径的权的上界，如果顶点获得了标号，则称顶点在第步获得了t 标号（临时性标号）4.P 已经获得标号为第步通过集P 为第步未通过集例：求图中v0与v5的最短路径(0)*000(0)0(1)*(0)(1)*1010100,{},T {},1,2,3,4,5{},min {},T T {}(2)T j jj i j i v T l P l w j l l l P P t ∈=======?=-0012345j i i i i 第步(r=0)：v 获得p 标号v v ，v ，v ，v ，v ，v 获得t 标号第1步(r=1)：(1)求下⼀个p 标号的顶点，将标在顶点v 处，表明顶点v 获得p 标号.修改通过集和未通过集：v v 修改中各顶点的标1(1)(0)(1)*(2)*(1)(2)*2121(2)(1)(2)*2min{,}{},min {},T T {}(2)T min{,}j jj iij i j iv T j j iij ll lw l l l P P t l l l w ∈=+==?=-=+i i i i 号：第2步(r=2)：(1)求下⼀个p 标号的顶点，将标在顶点v 处，表明顶点v 获得p 标号.修改通过集和未通过集：v v 修改中各顶点的标号：2.关键路径问题,(){/,}(){/,}D D D V E v V v x x V v x E v v x x V x v E v +=<>∈Γ=∈∧<>∈Γ=∈∧<>∈－设为⼀个有向图，，则为的后继元集为的先继元集定义：PERT 图设D=是n 阶有向带权图1. D 是简单图2. D 中⽆环路3. 有⼀个顶点出度为0，称为发点；有⼀个顶点⼊度为0，称为收点4. 记边的权为wij,它常常表⽰时间1. 最早完成时间：⾃发点v1开始，沿最长路径（权）到达vi 所需时间，称为vi 的最早完成时间，记为TE （vi ），i=1,2,…,nj 1i i j ij v ()234567TE(v )=0,v (1)TE(v )={(v )+w },1,2,,max TE(v )=max{0+1}=1;TE(v )=max{0+2,1+0}=2;TE(v )=max{0+3,2+2}=4;TE(v )=max{1+3,4+4}=8;TE(v )=max{2+4,8+1}=9;TE(v )=max{1+4,2+D i v i TE i n -∈Γ≠=显然的最早完成时间按如下公式计算：813784}=6;TE(v )=max{6+6,9+1}=12;v v v v 关键路径：从发点到收点的⼀条最长路径，2. 最晚完成时间：在保证收点vn 的最早完成时间不增加的条件下，⾃发点v1最迟到达vi 所需时间，称为vi 的最晚完成时间，记为TL （vi ）.j n n i i j ij v ()876543TL(v )=TL(v ),v ()TL(v )={(v )-w },1,2,,min TL(v )=12;TL(v )=min{12-6}=6;TL(v )=min{12-1}=11;TL(v )=min{11-1}=10;TL(v )=min{10-4}=6;TL(v )=min{6-2,11-4,6-4}=2;TL(D i v i n TL i n∈Γ≠=＋显然的最晚完成时间按如下公式计算：21v )=min{2-0,10-3,6-4}=2;TL(v )=min{2-1,2-2,6-3}=0;3. 缓冲时间：TS(vi)=TL(vi)- TE(vi) TS(v1)= TS(v3)= TS(v7)= TS(v8)=0 TS(v2)=2-1=1; TS(v4)=6-4=2; TS(v5)=10-8=2; TS(v6)=11-9=2。