简答 图

第七章 图

四、 应用题

1．（1）．如果G1是一个具有n个顶点的连通无向图，那么G1最多有多少条边？G1最少有多少条边？

（2）．如果G2是一个具有n个顶点的强连通有向图，那么G2最多有多少条边？G2最少有多少条边？

（3）．如果G3是一个具有n个顶点的弱连通有向图，那么G3最多有多少条边？G3最少有多少条边？

【复旦大学 1997 一（9分）】

2．n个顶点的无向连通图最少有多少条边？n个顶点的有向连通图最少有多少条边？

【山东大学 2000 一、3 (4分)】

3．一个二部图的邻接矩阵A是一个什么类型的矩阵？【北京科技大学 1999 一、8（2分）】 4．证明：具有n个顶点和多于n-1条边的无向连通图G一定不是树。【东南大学 1993 四（10分）】

5．证明对有向图的顶点适当的编号，可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。【北京邮电大学 2002 三 （10分）】

6．用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否有关？

【西安电子科技大学 2000计应用 一、6（5分）】 7．请回答下列关于图(Graph)的一些问题：（每题4分）

（1）．有n个顶点的有向强连通图最多有多少条边?最少有多少条边?

（2）．表示有1000个顶点、l000条边的有向图的邻接矩阵有多少个矩阵元素？是否稀

疏矩阵？

（3）．对于一个有向图，不用拓扑排序，如何判断图中是否存在环？【清华大学2000一(12分）】

8．解答问题。设有数据逻辑结构为： B = (K, R), K = {k1, k2, ?, k9}

R={, , ,, , ,, , , , }

（1）．画出这个逻辑结构的图示。（3分）

（2）．相对于关系r, 指出所有的开始接点和终端结点。（2分）

（3）．分别对关系r中的开始结点，举出一个拓扑序列的例子。（4分）

（4）．分别画出该逻辑结构的正向邻接表和逆向邻接表。（6分）【山东工业大学 1999 三 （15分）】

9．有向图的邻接表存储如下：（1）．画出其邻接矩阵存储；（2）．写出图的所有强连通分量；（3）．写出顶点a到顶点i的全部简单路径。【东北大学 1997 一、5 (5分)】

1 / 26

10．试用下列三种表示法画出网G 的存储结构，并评述这三种表示法的优、缺点： （1）．邻接矩阵表示法; （2）．邻接表表示法; （3）．其它表示法。【华中理工大学2000 三（12分）】 11．已知无向图G，V（G）={1，2，3，4}，E（G）={（1，2），（1，3），（2，3），（2，4），（3，4）}试画出G的邻接多表，并说明，若已知点I，如何根据邻接多表找到与I相邻的点j？ 【东南大学 1994 一、2 （8分） 1998 一、6（8分）】 12．如何对有向图中的顶点号重新安排可使得该图的邻接矩阵中所有的1都集中到对角线以上？ 【清华大学 1999 一、5 （2分）】 13．假定Ｇ＝（V，E）是有向图，V＝｛1,2，．．．,N｝，N＞＝1，G以邻接矩阵方式存储，G的邻接矩阵为A，即Ａ是一个二维数组，如果i到j有边，则A[i,j]=1，否则A[i,j]=0，请给出一个算法，该算法能判断G是否是非循环图（即G中是否存在回路），要求算法的时间复杂性为O(n*n)。 【吉林大学 1998 三(16分)】 14． 首先将如下图所示的无向图给出其存储结构的邻接链表表示，然后写出对其分别进行深度，广度优先遍历的结果。 【天津大学 1999 一】 15．下面的邻接表表示一个给定的无向图 （1）给出从顶点v1开始,对图G用深度优先搜索法进行遍历时的顶点序列； （2）给出从顶点v1开始,对图G用广度优先搜索法进行遍历时的顶点序列。【复旦大学1998六(10分)) 1 2 5 1 3 4 8 6 7 8 9 10 9 15题图 14题图 16题图 16．给出图G： （1）．画出G的邻接表表示图； （2）．根据你画出的邻接表，以顶点①为根，画出G的深度优先生成树和广度优先生成树。 【南开大学 1997 五 (14分)】 17．设G=(V,E)以邻接表存储，如图所示，试画出图的深度优先和广度优先生成树。 2 / 26

3 4 5 6 7 2

234?1

5?1342

124? 31235? 4 524? 【北京轻工业学院 1998 八 （6分）】 18．对一个图进行遍历可以得到不同的遍历序列，那么导致得到的遍历序列不唯一的因素有哪些？ 【北京航空航天大学 1998 一、7 （4分）】 19．解答下面的问题 （1）．如果每个指针需要4个字节，每个顶点的标号占2个字节，每条边的权值占2个字节。下图采用哪种表示法所需的空间较多？为什么? 2 9 8 7 10 5 1 20 4 1 10 5 6 10 2 2 3 3 6 11 3 4 15 3 5 19题图 20题图 （2）．写出下图从顶点1开始的DFS树。【西安电子科技大学 2000计应用 六 （10分）】 20．如下所示的连通图，请画出： （1）．以顶点①为根的深度优先生成树；（5分） （2）．如果有关节点，请找出所有的关节点。（5分）【清华大学 1998 七 （10分）】 21．某田径赛中各选手的参赛项目表如下: 姓名 参 赛 项 ZHAO A B E QIAN C D SHUN C E F LI D F A ZHOU B F 设项目A ,B ,?，F各表示一数据元素,若两项目不能同时举行,则将其连线(约束条件). （1）．根据此表及约束条件画出相应的图状结构模型,并画出此图的邻接表结构; （2）．写出从元素A出发按“广度优先搜索”算法遍历此图的元素序列. 【北京科技大学 1999 五 2000 五 （12分）】 22．已知无向图如下所示： （1）．给出从V1开始的广度优先搜索序列；（2）．画出它的邻接表； （3）．画出从V1开始深度优先搜索生成树。【燕山大学 2000 五 （5分）】 234?v1 5?1v2 5?1v3 v416? 3 / v526 24?3?v6 第22题图 第23题图 23．已知某图的邻接表为 （1）．写出此邻接表对应的邻接矩阵；（2分） （2）．写出由v1开始的深度优先遍历的序列；（2分） （3）．写出由v1开始的深度优先的生成树；（2分） （4）．写出由v1开始的广度优先遍历的序列；（2分） （5）．写出由v1开始的广度优先的生成树；（2分） （6）．写出将无向图的邻接表转换成邻接矩阵的算法。（8分） 【山东大学 1998 六、A 2 18分】 5 6 4 C 24．考虑右图： D B E 1 (1)从顶点A出发，求它的深度优先生成树 3 5 3 (2)从顶点E出发，求它的广度优先生成树 1 G F （3）根据普利姆(Prim) 算法， 求它的最小生成树【上海交通大学 1999 六 (12分)】 25.在什么情况下，Prim算法与Kruskual算法生成不同的MST？ 【西安电子科技大学 2000计应用 一、11 （5分）】 26．下面是求无向连通图最小生成树的一种方法。 将图中所有边按权重从大到小排序为（e1,e2,?,em） i:=1 WHILE (所剩边数 >=顶点数) BEGIN 从图中删去ei 若图不再连通，则恢复ei i:=i+1 END. 试证明这个算法所得的图是原图的最小代价生成树。【北京邮电大学 1999 五 （10分）】 27．已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树（假设以①为起点，试画出构造过程）。【哈尔滨工业大学 1999 九 （8分）】 20 1 4 1 9 4 2 5 11 7 8 2 9 6 6 14 6 3 10 10 5 3 2 6 5 4 4 5 18 27 题图 28题图 28．G=(V,E)是一个带有权的连通图,则：

（1）．请回答什么是G的最小生成树； （2）．G为下图所示,请找出G的所有最小生成树。【北方交通大学 1993 二 （12分）】 29．试写出用克鲁斯卡尔（Kruskal）算法构造下图的一棵最小支撑（或生成）树的过程。

5

21 7818 21 2 5 6 12 83 23 85 15 8 3 7 4 64 4 / 26 3325 10 7 24 6 7420

346657

第29图

【吉林大学 2000 一、3 (3分)】

30.求出下图的最小生成树。【合肥工业大学 1999 四、2 （5分）】 第30题图

31．一带权无向图的邻接矩阵如下图 ，试画出它的一棵最小生成树。

【浙江大学 1994 五 (8分)】 第32题图 32．请看下边的无向加权图。 （1）．写出它的邻接矩阵（ 5分） （2）．按Prim算法求其最小生成树，并给出构造最小生成树过程中辅助数组的各分量值（15分）

辅助数组内各分量值：【华北计算机系统工程研究所 1999 四 （20分）】 Y Closedge Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost Vex Lowcost

2 3 4 5 6 7 8 U V.-U 5 / 26

Vex Lowcost 33．已知世界六大城市为:北京(Pe)、纽约(N)、巴黎(Pa)、 伦敦(L) 、 东京(T) 、 墨西哥(M),下表给定了这六大城市之间的交通里程: 世界六大城市交通里程表(单位:百公里) PE N PA L T M PE N PA L T M 1 2 5 1 3 8 1 4 3 2 4 6 2 3 2 3 4 4 3 5 1 3 6 10 4 5 7 4 6 11 5 6 15 109 82 81 21 124 109 58 55 108 32 82 58 3 97 92 81 55 3 95 89 21 108 97 95 113 124 32 92 89 113 （1）．画出这六大城市的交通网络图; （2）．画出该图的邻接表表示法; （3）．画出该图按权值递增的顺序来构造的最小(代价)生成树. 【上海海运学院1995 六（9分） 1999 五 （14分）】 34．已知顶点1-6和输入边与权值的序列（如右图所示）：每行三个数表示一条边 的两个端点和其权值，共11行。请你： （1）．采用邻接多重表表示该无向网，用类PASCAL语言描述该数据结构，画出存 储结构示意图，要求符合在边结点链表头部插入的算法和输入序列的次序。 （2）．分别写出从顶点1出发的深度优先和广度优先遍历顶点序列，以及相应的 生成树。 （3）．按prim算法列表计算，从顶点1始求最小生成树，并图示该树。 【北京工业大学 1999 四(20分)】 35．下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出所有可能的选择。【东北大学2000一、4(4分)】 16 21 2153 d 8 1 b 5 114 19 e 5 c a 43614 6 7 h 3 2 f 633 56 18 第36题图 36．设无向网G 如上： 第35题图 （1）． 设顶点a、b、c、d、e、f、h的序号分别为1、2、3、4、5、6、7，请列出网G的邻接矩阵、画出网G 的邻接表结构: （2）．写出从顶点a出发,按“深度优先搜索”和“广度优先搜索”方法遍历网G所的到的 6 / 26

顶点序列：

按Prim算法求出网G的一棵最小生成树。【北京科技大学 2001 五 (12分)】

12

37．有一图的邻接矩阵如下，试给出用弗洛伊德算法求各点间最短距离的矩阵序列A，A，34

A，A。

?02?????016????5?04???3??0? A=?

【北京邮电大学2001四、5(5分）】

38．下图所示是一带权有向图的邻接表法存储表示。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求：

（1）．该带权有向图的图形；

（2）．从顶点V1为起点的广度优先周游的顶点序列及对应的生成树（即支撑树）； （3）．以顶点V1为起点的深度优先周游生成树；

（4）．由顶点V1到顶点V3的最短路径。【中山大学 1994 四 （12分）】

(顶点边)（出边表）b 6 e 5 h 2 1V15 4 9 8 233429625?3 2 2 i 9 a 2 c 4 z f 2V2336?2 4 1 6 4 1 2 3 9 j d g 3V3? 第39题图 V4230338542? 4 1018?16V5 5 6V6?

39．用最短路径算法，求如下图中a到z的最短通路。【西南财经大学 1999 四】 40．已知一有向网的邻接矩阵如下，如需在其中一个结点建立娱乐中心，要求该结点距其它各结点的最长往返路程最短，相同条件下总的往返路程越短越好，问娱乐中心应选址何处？给出解题过程。 V1?02???3?V2??032?????V3?4?0?4????V4?1??01??V5??1??03???V6???25?0? 601105301562316787102036154683 第41题图 【北京邮电大学 2002 四、1 （10分）】

41．求出下图中顶点1到其余各顶点的最短路径。【厦门大学 2002 八、2 （5分）】 42．试利用Dijkstra算法求下图中从顶点a到其他个顶点间的最短路径，写出执行算法过程中各步的状态。

【东南大学 2000 四（10分）】

43．对于如下的加权有向图，给出算法Dijkstra产生的最短路径的支撑树，设顶点A为源

点，并写出生成过程。【吉林大学 1999 一、2 (4分)】

45

bA3B 2015C20D353040E 7 / 26

a12d15 62c45f10g8e94 2120第43题图

44．已知图的邻接矩阵为： V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 V1 0 1 1 1 0 0 0 0 0 0 V2 0 0 0 1 1 0 0 0 0 0 V3 0 0 0 1 0 1 0 0 0 0 V4 0 0 0 0 0 1 1 0 1 0 V5 0 0 0 0 0 0 1 0 0 0 V6 0 0 0 0 0 0 0 1 1 0 V7 0 0 0 0 0 0 0 0 1 0 V8 0 0 0 0 0 0 0 0 0 1 V9 0 0 0 0 0 0 0 0 0 1 V10 0 0 0 0 0 0 0 0 0 0 当用邻接表作为图的存储结构，且邻接表都按序号从大到小排序时，试写出： （1）．以顶点V1为出发点的唯一的深度优先遍历； （2）．以顶点V1为出发点的唯一的广度优先遍历； （3）．该图唯一的拓扑有序序列。【同济大学 1998 一 (12分 )】 45．已知一图如下图所示： （1）．写出该图的邻接矩阵； （2）．写出全部拓扑排序； （3）．以v1为源点,以v8为终点，给出所有事件允许发生的最早时间和最晚时间，并给出关键路径； （4）．求V1结点到各点的最短距离。【北京邮电大学 2000 五 （15分）】 2 V1 V3 3 3 V7 10 V5 1 7 4 8 3 2 1 2 3 6 5 4 V6 6 V8 V2 V4 5 第46题图 第45题图

46．（1）．对于有向无环图，叙述求拓扑有序序列的步骤； （2）．对于以下的图，写出它的四个不同的拓扑有序序列。【南开大学 1998 二 (12分)】 47．有向图的拓扑排序能否用图的深度搜索模式来查找?若能，请简述方法，若不能，请简述原因

【西北大学 2000 二、8 (5分)】

8 / 26

48．下图是带权的有向图G的邻接表表示法，求： （1）．以结点V1出发深度遍历图G所得的结点序列； （2）．以结点V1出发广度遍历图G所得的结点序列； （3）．从结点V1到结点V8的最短路径； （4）．从结点V1到结点V8的关键路径。 【青岛海洋大学 1999 四（10分）】 49．对有五个结点{ A,B, C, D, E}的图的邻接矩阵， ?010030?10???0????????60020?????10?0????????500?? （1）．画出逻辑图 ； （2）．画出图的十字链表存储； （3）．基于邻接矩阵写出图的深度、广度优先遍历序列； （4）．计算图的关键路径。 【华南师范大学 1999 三 (20分)】 50．何为AOE网的始点和终点，一个正常的AOE网是否只有一个始点和一个终点？ 【首都经贸大学 1997 一、4 （4分）】 51．下表给出了某工程各工序之间的优先关系和各工序所需时间 （1）．画出相应的AOE网 （2）．列出各事件的最早发生时间,最迟发生时间 （3）．找出关键路径并指明完成该工程所需最短时间. 【武汉交通科技大学 1996 二、6 (7分)】 工序 A B C E F G H I J K L 代号 D M N 所需 10 50 15 300 15 120 15 30 时间 15 8 40 60 20 40 先驱 -- A,B C,D B E G,I E I F,I H,J,K L G 工作 -- B 52．对图示的AOE网络，计算各活动弧的e(ai)和l(ai)的函数值，各事件（顶点）的ve（Vj）和vl (Vj)的函数值，列出各条关键路径。【北京轻工业学院 1997 四 （15分）】 9 / 26

A1B?6534C72E821 11106F9 1716H12WG133 2 1 0 2 2 5 4 3 3 7 5 4 3 8 5 2 7 4 3 D

10 1 6 6 4 9 7 11 第52题图 第53题 工程作业的网络图

53．请写出应填入下列叙述中（ ）内的正确答案。

某一工程作业的网络图如图所示，其中箭头表示作业，箭头边的数字表示完成作业所需的天数。箭头前后的圆圈表示事件，圆圈中的数字表示事件的编号。用事件编号的序列（例如0-2-7-9-11）表示进行作业的路径。

完成此工程的关键路径是（A）完成此工程所需的最少天数为（B）天，此工程中具有最大充裕天数的事件是（C），充裕天数是（D）。关键路径上的事件的充裕天数是（E）。【上海大学 2002 三 （10分）】

四.应用题

1．（1）G1最多n(n-1)/2条边，最少n-1条边 (2) G2最多n(n-1)条边，最少n条边

(3) G3最多n(n-1)条边，最少n-1条边 (注：弱连通有向图指把有向图看作无向图时，仍是连通的) 2．n-1，n 3.分块对称矩阵

4．证明：具有n个顶点n-1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于n-1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形成回路的连通图不再是树（在图论中树定义为无回路的连通图）。

5．证明：该有向图顶点编号的规律是让弧尾顶点的编号大于弧头顶点的编号。由于不允许从某顶点发出并回到自身顶点的弧，所以邻接矩阵主对角元素均为0。先证明该命题的充分条件。由于弧尾顶点的编号均大于弧头顶点的编号，在邻接矩阵中，非零元素（A[i][j]=1）自然是落到下三角矩阵中；命题的必要条件是要使上三角为0，则不允许出现弧头顶点编号大于弧尾顶点编号的弧，否则，就必然存在环路。（对该类有向无环图顶点编号，应按顶点出度顺序编号。）

2

6．设图的顶点个数为n(n≥0)，则邻接矩阵元素个数为n，即顶点个数的平方，与图的边数无关。

7．（1）n(n-1)， n

6

(2) 10，不一定是稀疏矩阵（稀疏矩阵的定义是非零个数远小于该矩阵元素个数，且分布无规律） （3）使用深度优先遍历，按退出dfs过程的先后顺序记录下的顶点是逆向拓扑有序序列。若在执行dfs(v)未退出前，出现顶点u到v的回边，则说明存在包含顶点v和顶点u的环。

10 / 26

8．(1) （2）开始结点：（入度为0）K1，K2，终端结点（出度为0）K6，K7。

（3）拓扑序列K1，

K2，K3，K4，K5，K6，K8，K9，K7

K2，K1，K3，K4，K5，K6，K8，K9，K7

规则：开始结点为K1或K2，之后，若遇多个

入度为0的顶点，按顶点编号顺序选择。

（4）

11 / 26

8（4）邻接表和逆邻接表

9．（1） 注：邻接矩阵下标按字母升序:abcdefghi

（2）强连通分量：（a），(d)，

（h），

(b，e，i，

f，c，g）

(3 ) 顶点a到顶点i的简

单路径：

（a?b?e?i），

(a?c?g?i)，

(a?c?b?e?i)

10．图G的具体存储结构略。

2

邻接矩阵表示法，有n个顶点的图占用n个元素的存储单元，与边的个数无关，当边数较少时，存储效率较低。这种结构下，对查找结点的度、第一邻接点和下一邻接点、两结点间是否有边的操作有利，对插入和删除顶点的操作不利。

邻接表表示法是顶点的向量结构与顶点的邻接点的链式存储结构相结合的结构，顶点的向量结构含有n（n≥0）个顶点和指向各顶点第一邻接点的指针，其顶点的邻接点的链式存储结构是根据顶点的邻接点的实际设计的。这种结构适合查找顶点及邻接点的信息，查顶点的度，增加或删除顶点和边（弧）也很方便，但因指针多占用了存储空间，另外，某两顶点间是否有边（弧）也不如邻接矩阵那么清楚。对有向图的邻接表，查顶点出度容易，而查顶点入度却困难，要遍历整个邻接表。要想查入度象查出度那样容易，就要建立逆邻接表。无向图邻接表中边结点是边数的二倍也增加了存储量。

十字链表是有向图的另一种存储结构，将邻接表和逆邻接表结合到一起，弧结点也增加了信息（至少弧尾，弧头顶点在向量中的下标及从弧尾顶点发出及再入到弧头顶点的下一条弧的四个信息）。查询顶点的出度、入度、邻接点等信息非常方便。

12 / 26

邻接多重表是无向图的另一种存储结构，边结点至少包括5个域：连接边的两个顶点在顶点向量中的下标，指向与该边相连接的两顶点的下一条边的指针，以及该边的标记信息（如该边是否被访问）。边结点的个数与边的个数相同，这是邻接多重表比邻接表优越之处。

11．

已知顶点i，找与i相邻的顶点j的规则如下：在顶点向量中，找到顶点i，顺其指针找到第一个边结点（若其指针为空，则顶点i无邻接点）。在边结点中，取出两顶点信息，若其中有j，则找到顶点j；否则，沿从i发出的另一条边的指针（ilink）找i的下一邻接点。在这种查找过程中，若边结点中有j，则查找成功；若最后ilink为空，，则顶点i无邻接点j。

12．按各顶点的出度进行排序。n个顶点的有向图，其顶点最大出度是n-1，最小出度为0。这样排序后，出度最大的顶点编号为1，出度最小的顶点编号为n。之后，进行调整，即若存在弧，而顶点j的出度大于顶点i的出度，则将把j编号在顶点i的编号之前。本题算法见下面算法设计第28题。

13．采用深度优先遍历算法，在执行dfs(v)时，若在退出dfs(v)前，碰到某顶点u ，其邻接点是已经访问的顶点v，则说明v的子孙u有到v的回边，即说明有环，否则，无环。（详见下面算法题13）

14．深度优先遍历序列：125967384

宽度优先遍历序列：123456789

注：（1）邻接表不唯一，这里顶点的邻接点按升序排列

（2）在邻接表确定后，深度优先和宽度优先遍历序列唯一 （3）这里的遍历，均从顶点1开始

13 / 26

15．（1）V1V2V4V3V5V6

2）V1V2V3V4V5V6

14 / 26

16.(1)

（

16题（3）宽度优先生成树

（2）深度优先生成树

为节省篇幅，生成树横画，下同。

17．设从顶点1开始遍历，则深度优先生成树(1)和宽度优先生成树(2)为：

图

17(1) 图17(2)

18．遍历不唯一的因素有：开始遍历的顶点不同；存储结构不同；在邻接表情况下邻接点的顺序不同。

19．（1）邻接矩阵：（6*6个元素）*2字节/元素=72字节

邻接表：表头向量6*（4+2）+边结点9*(2+2+4)*2=180字节

邻接多重表：表头向量6*（4+2）+边结点9*（2+2+2+4+4）=162字节

邻接表占用空间较多，因为边较多，边结点

又是边数的2倍，一般来说，邻接矩阵所占空间与边个数无关（不考虑压缩存储），适合存储稠密图，而邻接表适合存储稀疏图。邻接多重表边结点个数等于边数，但结点中增加了一个顶点下标域和一个指针域。

（2）因未确定存储结构，从顶点1开始的DFS

树

不唯一，现列出两个：

20．未确定存储结构，其DFS树不唯一，其中之一（按邻接点逆序排列）是

15 / 26

50．AOE网的始点是入度为零的顶点，该顶点所代表的事件无任何先决条件，可首先开始。终点是出度为零的顶点，表示一项工程的结束。正常的AOE网只有一个始点和一个终点。

51．（1）AOE网如右图

图中虚线表示在时间上前后工序之间仅是接 续顺序关系不存在依赖关系。顶点代表事件，弧 代表活动，弧上的权代表活动持续时间。题中顶

点1代表工程开始事件，顶点11代表工程结束事件。 （2）各事件发生的最早和最晚时间如下表

事 件 最早发生时间 最晚发生时间 1 0 0 2 15 15 3 10 57 4 65 65 5 50 6 80 7 8 9 10 11 12 200 380 395 425 445 420 335 380 395 425 445 425 380 80 （3）关键路径为顶点序列：1->2->4->6->8->9->10->11；

事件序列：A->C->E->G->H->L->M，完成工程所需的最短时间为445。

52

顶点 Ve(i) Vl(i)

活动 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a15 a16 a17 e(i) 0 0 0 0 3 1 6 6 3 3 4 7 24 31 13 20 13 36 13 13 39 39 22 22 22 40 l(i) 28 18 0 29 24 31 34 3 α 0 0 A 1 29 B 6 24 C 3 3 D 4 7 E 24 31 F 13 13 G 39 39 H 22 22 W 52 52 关键路径是：

活动与顶点的对照表：a1<α,A> a2<α,B> a3<α,C> a4<α,D> a5 a6

a7 a8

a9 a10 a11 a12 a13 a14 a15 a16 a17

53．A.0—2—6—9—11 B.20 C.1，5，7 D.各2 天 E.0

26 / 26

本文来源：https://www.bwwdw.com/article/wwy8.html