第5章图与网络

1第5章图与网络分析

图论的基本概念

最小支撑树

最短路问题

最大流问题

网络计划2一、引言

图论是由瑞士数学家欧拉（Euler）于1736年创始的，当时有一个世界难题，叫“哥尼斯堡七桥问题”。哥尼斯堡城中有一条河，叫普雷格尔河，河中有两个岛，河上有七座桥，如图所示。当时那里的居民热衷于这样的问题：一个散步者能否走过七座桥，但每座桥只走过一次，最后回到出发点。5.1图论的基本概念ABCD3欧拉用A、B、C、D四点表示河的两岸和小岛，用两点间的联线表示桥，如右下图所示，该问题可归结为：能否从某一点出发，一笔画出这个图形，最后回到出发点而不重复？即一笔画问题。

ACBDBCDA欧拉在1786年发表了题为“依据几何位置的解题方法”的论文，解决了著名的哥尼斯堡七桥问题．欧拉证明了上述图形一笔划是不可能的，因为图中每一个点都只和奇数条线相关联．

他的结论是：图形能一笔画的充要条件是图形的奇顶点（连接奇数条线的顶点）的个数为零4二、图的定义

在自然界和人类的实际生活中，常用点和点与点之间的联线所构成的图，来反映某些研究对象和对象之间的某种特定的关系。如：为了反映城市之间有没有航班，我们可用右图表示。甲城与乙城，乙城与丙城有飞机到达，而甲、丙两城没有直飞航班。对于工作分配问题，我们可能用点表示工人与需要完成的工作，点间连线表示每个工人可以胜任哪些工作如右图所示。

甲乙丙甲乙丙工人ABC工作Ｄ5图的定义：所谓图，就是顶点（简称点）和一些点之间的连线（不带箭头或者带箭头）所组成的集合。为区别起见，不带箭头的连线称为边，带箭头的连线称为弧。如果一个图是由点和边所构成的，则称之为无向图（也简称为图），记作，其中V表示图G的非空的顶点集合，E表示G的边的集合。连接顶点和的边记为；如果一个图是由点和弧所构成的，则称之为有向图，记作，其中V仍表示有向图D的非空的顶点集合，A表示D的弧集合。一条方向从指向的弧记为。6

如无向图：Ｖ1Ｖ4Ｖ3Ｖ2e1e5e6e4e3e2e77如有向图：Ｖ1Ｖ3Ｖ2Ｖ4Ｖ5Ｖ6Ｖ7a1a2a3a4a6a5a7a8a9a10a118三、基本概念点和边的相关概念：（1）顶点数和边数：给定图，集合V的元素的个数，称为图G的顶点数，记作；集合E的元素的个数，称为图G的边数，记作。（2）端点和关联边：若，则称顶点是的端点，是的关联边。（3）相邻点和相邻边：若顶点和与同一条边相关联，则称点和为相邻点；若边和有一个共同的端点，则称其为相邻边。（4）环和多重边：若边的两个端点属同一顶点，则称该边为环；若两个端点之间多于一条边，则称这些边为多重边。（5）多重图和简单图：含多重边的图称为多重图，无环也无多重边的图称为简单图。9（6）次和孤立点：与点关联的边的条数，称为点的次，记作；次数为零的点为孤立点。（7）悬挂点和悬挂边：次为1的点称为悬挂点；悬挂点的关联边称为悬挂边。（8）奇点和偶点：次为奇数的点称为奇点；次为偶数的点为偶点。定理1图中，所有顶点的次之和等于所有边数的2倍，即链的概念：（1）给定一个图，一个点、边的交错序列，如果满足。这样的序列称为一条联结和的链，记作。10（2）开链和闭链：如果，则该链称为开链；如果，则该链称为闭链（或称为圈）。（3）简单链和初等链：如链内所含的边均不相同，称之为简单链；如链内所含的点均不相同，称之为初等链。如：是简单链，是初等链，是初等圈，是简单圈，Ｖ1Ｖ2Ｖ4Ｖ3Ｖ5Ｖ6Ｖ7e1e2e3e8e4e7e6e5e911（4）基础图和路：若把一个有向图D的方向去掉，即每一弧都用相应得无向边代替，所得到的一个无向图，称为该有向图D的基础图，记为G（D）；基础图G（D）中的链（或圈）恢复无向边的方向后，称为有向图D的链（或圈）。若交替序列是有向图G的一条链，且满足，即链中每一条弧的箭头方向都和链的方向一致，那么该链称为有向图D的一条从到的路，简记。又若，则称μ为图D中的回路。对无向图G来说，链和路（闭链和回路）这两个概念是一致的。但有向图D中的链不一定是路，因为有向图的链可能存在和链的方向不一致的反向弧，但按定义，它们仍是有向图中的链。12连通图和网络图的概念：（1）连通图：在一个图G中，若任意两点之间至少存在一条链，则称该图G为连通图，否则称之为不连通图。如：Ｖ3Ｖ6Ｖ5Ｖ2Ｖ4Ｖ1a2a3a1a4a5左图为不连通图。因为在顶点Ｖ1，V2，V3，V4和V5，V6之间不存在任何一条链将它们相连接。Ｖ1Ｖ2Ｖ3Ｖ4Ｖ5右图为有向连通图13（2）连通分图：若G是不连通图，那么它的每一个连通部分称为图G的连通分图。（3）子图和支撑子图：设图，若有，使，则称是的子图；若，则称是的支撑子图。如，以下右图是左图的支撑子图。v1v3v5v4e5v3v5v4v2e2e1e3e4e5e6e7e8v2e1e3e4v1e614（4）赋权图：设图，若对其边集E定义了一个实值函数，则称该图为一个赋权图。记作。称为边的权。如某工厂内连接六个车间的道路网如入所示，已知每条路长，要求沿道路架设连接六个车间的电话线路，使电话总长最短。Ｖ1Ｖ2Ｖ3Ｖ4Ｖ5Ｖ6652715344左图为一赋权图最优解：如红线所示，电话总长15个单位。红线所示为图Ｇ的最小支撑树15（5）网络图，若为一赋权图，并在其顶点集合V中指定了起点（或称发点）和终点（或称收点），其余的点为中间点，这样的赋权图称为网络图（简称网络）。记作。网络一般是连通的赋权图。

若一个网络图中的每条边都是有向的弧，则称之为有向网络，记作

16四、图的矩阵表示距离矩阵：设图，为边上的权，表示点到之间的距离，则可构造距离矩阵，其中如：以下无向赋权图中的权表示点与点之间距离其他Ｖ1247635489Ｖ2Ｖ3Ｖ4Ｖ5或

对有向赋权图，则定义时将改为。17邻接矩阵：

设图，则邻接矩阵的元素可定义如下其他对有向赋权图，则定义时将改为如Ｖ1Ｖ2Ｖ3Ｖ4Ｖ518一、树及其性质树的定义：设，若G连通，并且没有圈，则称G为树，记作。比如有六个顶点的树有6种，5.2最小支撑树··19定理2

以下关于树T的六种描述是等价的，（1）无圈连通图；（2）无圈，(即图有条边，是图中的顶点数)；（3）连通，；（4）无圈，但增加一条边可得唯一一个圈；（5）连通，但舍弃一条边则不连通；（6）每一对顶点之间有一条且仅有一条链。上述六个等价命题可以使用循环证明法，即由命题（1）推得命题（2），再由命题（2）推得命题（3），……，依次类推，最后由命题（6）回推到命题（1），完成以上推导过程即证明了六个命题是等价的。20二、图的支撑树支撑树的定义：假设图是图的支撑子图，如果图是一个树，则称T是G的支撑树。如下图中，（b）图是(a)图的支撑树定理3

图G有支撑树的充分必要条件是图G是连通的V1V2V3V4V5V6V2V3V4V5V6（a）（b）21三、最小支撑树定义设赋权图，它的每条边有非负权，是G的一个支撑树，中所有边的权之和如果，则称是G的最小支撑树。定理4

设赋权图，若把E分割成两个不相交的非空子集和，那么连接这两个子集的最小边一定包含在G的最小支撑树内。由定理4可以引出求最小支撑树的方法22求最小支撑树的方法。（1）避圈法。步骤如下：①从赋权图G中任选一点，令，；②从连接和的边中选择权最小的边，不妨假设为，由定理4，它必包含在最小支撑树内；③令，；④若，则停止计算，已选出的各条边已构成最小支撑树，否则回到②。例1

某工厂联结六个车间的道路网如下图所示，已知每条道路长，要求沿道路架设联结六个车间的电话网，使电话线的总长最短。V1V2V4V3V5V661557234423至此，停止计算，

V1V2V4V3V5V6615572344解：这是求最小支撑树的问题，由避圈法的步骤，在图G的六个顶点中任选其中一点作为S，比如选，则，联结和一共有3条边，取最短边，并令，依次类推…

，最短电话线路的总长为15个单位。24（2）破圈法。步骤是：在图中任取一个圈，从圈中除去权最大的一条边（圈中存在两条以上最大权的边，可任选其中一条），在余下的支撑子图中重复这个步骤，一直得到一个不含圈的支撑子图为止，这时的图就是原赋权图的最小支撑树。例2，用破圈法求例1中的赋权图的最小支撑树。V1V3V5V6615572344

，最短电话线路的总长为15个单位。25最短路问题表述：给定一个赋权图，对每一边相应地有权，又有两点，设Ｐ是Ｇ中从到的一条路，路Ｐ的权是Ｐ中所有边的权之和，记为。最短路问题就是求从到的路中一条权最小的路Ｐ0，使上述定义中，若是有向赋权图，则任一边改为任一弧，其他相同。此时从到的路应是沿弧的箭头方向首尾相接的路。5.3最短路问题26一、Dijkstra算法

狄克斯拉算法是由Dijkstra于1959年提出来，用于求解指定两点，cc之间的最短路，或从指定点到其余各点的最短路，目前被认为是求情形下最短路问题的最好方法。基本思路基于以下原理：若Ｐ是从到的最短路，是Ｐ中的一个点，那么从到的最短路就是从沿Ｐ到的那条路。采用标号法：Ｔ标号与Ｐ标号。Ｔ标号为试探性标号，Ｐ为永久性标号。给点一个Ｐ标号时，该标号表示从到点的最短路权，点的标号不再改变。给点一个Ｔ标号时，Ｔ标号表示从到点的最短路权的上界，是一种临时标号。凡没有得到Ｐ标号的点都有Ｔ标号。算法每一步都把某一点的Ｔ标号改为Ｐ标号，当终点得到Ｐ标号时，全部计算结束。27Dijkstra算法基本步骤：⑴给以Ｐ标号，其余各点均给Ｔ标号，。⑵若点为得到Ｐ标号的点，考虑且为Ｔ标号。对的Ｔ标号进行如下的更改：⑶比较所有具有Ｔ标号的点，若则把最小值对应的点改为Ｐ标号，即当存在两个以上最小者时，可同时改为Ｐ标号。若全部点均为Ｐ标号则停止。否则转回⑵。步骤(3)，当给顶点Ｐ标号时，可以在图的对应顶点旁标上一个记号（，），其中为从到的最短路上与邻接的顶点，为从到的最短路长。的记号取（，０）28例2

用Dijkstra算法求图中从的最短路12235535775１1４２３５６７解：⑴首先给以P标号给其余所有点Ｔ标号

(2)考察，由于且是Ｔ标号点，所以修改Ｔ标号为：(v1,0)在所有Ｔ标号中，，于是给Ｐ标号令，并标上（，２）。(v1,2)2912235535775１1４２３５６７(v1,0)在所有Ｔ标号中，最小，于是给Ｐ标号令，并标上（，3）。(3)考察，因且是Ｔ标号，故修改对应的Ｔ标号：(v1,3)(v1,2)30(4)考察，因且是Ｔ标号，故修改对应的Ｔ标号为：在所有Ｔ标号中，最小，于是给Ｐ标号令

，并标上（，4）。12235535775１1４２３５６７(v1,0)(v1,3)(v2,4)(v1,2)31在所有Ｔ标号中，最小，于是给Ｐ标号令

，标上（，7）。(5)考察，因且是Ｔ标号，故修改对应的Ｔ标号为：12235535775１1４２３５６７(v1,0)(v1,3)(v2,4)(v3,7)(v1,2)32在所有Ｔ标号中，最小，于是给Ｐ标号令，标上（，8）。12235535775１1４２３５６７(6)考察，因且是Ｔ标号，故修改对应的Ｔ标号为：(v1,0)(v1,3)(v2,4)(v3,7)(v5,8)(v1,2)33(7)考察，因且是Ｔ标号，故修改对应的Ｔ标号为：由于只剩最后一个Ｔ标号，所以给Ｐ标号。令，标上（，13）。由于所有顶点都标上了Ｔ标号所以计算结束。(v６,13)从到的最短路：最短路长13.12235535775１1４２３５６７(v1,0)(v1,3)(v2,4)(v3,7)(v5,8)(v1,2)34例3

设备更新问题。某企业使用一台设备，在每年年初，都要决定是否更新。若购置新设备，要付购买费；若继续使用旧设备，则支付维修费用。试制定一个5年更新计划，使总支出最少。若已知设备在各年的购买费及不同机器役龄时的残值和维修费，如下表所示：第1年第2年第3年第4年第5年购买费1112131414机器役龄0-11-22-33-44-5维修费5681118残值4321035解：把这个问题化为最短路问题用表示第i年初购进一台新设备，虚设一个点表示第5年底；用弧表示第i年初购的设备一直使用到第j年年初（第j-1年年低）；弧旁的数字表示第i年初购进设备，一直使用到第j年初所需支付的购买、维修的全部费用。这样设备更新问题就变为：求从到的最短路.第1年第2年第3年第4年第5年购买费1112131414机器役龄0-11-22-33-44-5维修费5681118残值4321036第1年第2年第3年第4年第5年购买费1112131414机器役龄0-11-22-33-44-5维修费5681118残值43210194059121314152130152841292220123456购买维修残值费用１→２１１５４１２１→３１１１１３１９１→４１１１９２２８１→５１１３０１４０１→６１１４８０５９２→３１２５４１３２→４１２１１３２０２→５１２１９２２９２→６１２３０１４１３→４１３５４１４３→５１３１１３２１３→６１３１９２３０４→５１４５４１５４→６１４１１３２２５→６１４５４１５37

计算结果表明为最短路，路长为49。即在第1年、第3年初各购买一台新设备为最优决策，这时5年的总费用为49。194059121314152130152841292220123456(v1,0)(v1,12)(v1,19)(v1,28)(v3,40)(v3,49)ＴＴＴＴＴＴV1０V2∞12V3∞1919V4∞282828V5∞40404040V6∞5953494949相邻点V1V1V1

V1V3V3Ｐ标号38右图是输油管道网，为起点，是终点，为中转站，边上的数表示该管道的最大输油能力，问：（1）应如何安排各管道输油量，才能使从到的总输油量最大？

最大流问题是网络分析中一类应用极为广泛的问题。在交通运输网络中有人流、车流、货物流；供水网络中有水流；金融系统中有现金流；通讯系统中有信息流；等等。20世纪50年代Ford，Fulkerson建立的“网络流理论”是网络应用的重要组成部分。5.4最大流问题254311２１４３Ｓt352（2）如果要增加管道网的最大输油量，应该优先增加哪个管道的输油能力?39一、基本概念网络与流：我们已经给出了网络图的概念，网络图是一种无向或有向赋权图，在其顶点集合中指定了起点和终点，其余的点为中间点。在最大流问题中，我们所讨论的网络都是有向连通赋权图，记作，称V中的起点为发点，终点为收点，其余的点仍为中间点。对于每一个弧，对应有一个权，称为弧的容量，简记。所谓网络上的流，是指定义在弧集合A上的一个函数，并称为弧上的流量，简记作。40可行流：满足下列条件的流成为可行流：①容量限制条件：每一弧②平衡条件：对于中间点，有对于发点，收点，有并称为这个可行流的流量。可行流总是存在的，如零流，。

（2，1）（5，3）（4，3）（3，0）（1，1）（1，1）２１４３Ｓt（3，3）（5，1）（2，2）41最大流：所谓最大流问题，就是求一个流，使其流量达到最大，并且满足以上容量限制条件和平衡条件。最大流问题是一个特殊的线性规划问题．（2，1）（5，4）（4，４）（3，0）（1，1）（1，0）２１４３Ｓt（3，3）（5，2）（2，2）42增广链：若是网络中联结发点和收点的一条链，且链的方向是从到，则与链的方向一致的弧叫前向弧，表示前向弧的集合；与链的方向相反的弧叫后向弧，表示后向弧的集合。定义1

设是一个可行流，是从到的一条链，若满足下列条件，则是可行流的一条增广链：①

前向弧上，，即中每一弧是非饱和弧，②

后向弧上，，即中每一弧是非零流弧。定理5

可行流是最大流，当且仅当不存在关于的增广链。43（2，1）（5，3）（4，3）（3，0）（1，1）（1，1）２１４３Ｓt（3，3）（5，1）（2，2）44二、Ford-Fulkerson算法福特－富克逊算法又称寻求最大流的标号法。前提是已有一个可行流，标号算法分2步。第1步：给顶点的标号过程。通过顶点的标号来寻找增广链；第2步是调整过程，沿增广链调整ｆ以增加流量。⑴标号过程每个顶点的标号包含两部分：第1部分表明它的标号是从哪一个顶点得到，以便找出增广链；第2部分是为确定增广链的调整量用的。①给发点以标号；②选择一个已标号的点，对于的所有未标号的邻接点，如果，且，令，并给以标号；如果，且，令，并给以标号。45重复上述步骤②，直到被标上号或不再有顶点可标号为止。如果得到标号，说明存在增广链，转入调整过程；如果未获得标号，标号过程已无法进行时，说明ｆ已是最大流。⑵调整过程令其中调整量．调整后去掉所有标号，对新的可行流重新进行标号过程。调整过程为：在增广链的前向弧上加上调整量θ，后向弧上减去调整量θ，其他弧的流量不变．这样可使总流量增加θ，即46找可行流ｆ给ＶS标号(ＶS，＋∞)Ｖt是否已

标号

是否存在已标号但未检查的点

倒向追踪找出增广链μ

令调整量求改进的可行流不存在关于ｆ的增广链ｆ即为最大流Ｖi已

标号,但未检查．

对Ｖi

进行检查，并对Ｖj标号:

若，且，对Ｖj标号:

，若，且，对Ｖj标号:

，是否47例4

用标号法求所示网络图的最大流。弧旁的数是。弧不满足标号条件．（2，2）（2，1）（5，3）（4，3）（3，3）（5，1）（3，0）（1，1）（1，1）解：经检查，网络中的流是可行流，下面分析是否可以增加流量。（１）标号过程：①先给标号；②检查，在弧上，所以

则的标号２１４3Ｓt（ＶＳ,+∞)（ＶＳ,4)．弧不满足标号条件．③检查，在弧上，所以则的标号（－Ｖ１,１）48（Ｖ4,１）（2，2）（2，1）（5，3）（4，3）（3，3）（5，1）（3，0）（1，1）（1，1）④检查，在弧上，

给标号

２１４３Ｓt（ＶＳ,+∞)（ＶＳ,4)

在弧上．给标号⑤检查，在弧上，所以

,

给标号．因已经标号，故进入调整过程．（－Ｖ１,１）（Ｖ２,１）（－Ｖ2,１）49（5，1）（Ｖ4,１）（2，2）（2，1）（5，3）（4，3）（3，3）（3，0）（1，1）（1，1）２１４３Ｓt（ＶＳ,4)（－Ｖ１,１）（Ｖ２,１）（－Ｖ2,１）（ＶＳ,+∞)（2）调整过程：取定增广链．前向弧上流量增加１，后向弧上流量减去１，其他不变，得可行流在进入新的循环：①给标号检查给标号检查，标号过程无法进行下去．所以为最大流，（2，2）（3，3）（5，2）（ＶＳ,+∞)（2，1）（5，4）（4，４）（3，0）（1，1）（1，0）２１４３Ｓt（ＶＳ,3)问题（1）：应如何安排各管道输油量，才能使从到的总输油量最大？答：fs1=2、fs2=3、f13=2、f24=4、f32=1、f4t=4、f3t=1.（2，1）（5，4）（4，４）（3，0）（1，1）（1，0）２１４３Ｓt（3，3）（5，2）（2，2）51截集与截量：设，我们把始点在Ｓ，终点在Ｔ中的所有弧构成的集合，记为。定义１：设网络，若点集Ｖ被剖分为两个非空集合和，使，则把弧集称为分离，的截集。截集是从到的必径之道。定义2

给定一截集，把截集中所有弧的容量之和称为这个截集的容量（或称截量），记作任何一个可行流的流量都不会超过任一截量的容量，即若对于一个可行流，网络中有一个截集，使则必是最大流，而必定是网络的所有截集中容量最小的一个，称为最小截量。52

最大流量最小截量定理：任一个网络中，从到的最大流的流量等于分离，的最小截集的容量。

53由上述可见，用标号法找增广链找到最大流的同时，得到一个最小截集。最小截集的容量大小影响网络最大流量。因此为提高总的输送量，必须首先考虑改善最小截集中各弧的输送能力。另一方面，一旦最小截集中弧的通过能力被降低，就会使总的输送量减少。（2，1）（5，4）（4，４）（3，0）（1，1）（1，0）２１４３Ｓt（ＶＳ,3)（ＶＳ,+∞)（3，3）（5，2）（2，2）问题（2）：如果要增加管道网的最大输油量，应该优先增加哪个管道的输油能力?答：cs2、c21、c13.（2，1）（5，4）（4，４）（3，0）（1，1）（1，0）２１４３Ｓt（3，3）（5，2）（2，2）练习用Dijkstra标号法求网络图起点VS到终点Vt的最短路径，结果如下图示：由结果之间的关系，可以知A=

，B=

，C=

，D=

。起点VS到终点Vt的最短路程为

，最短路径为：

。起点VS到点V5的最短路程为

，最短路径为：

。练习如下图所示的网络图，弧上数为（）。为了使f为可行流，则f23=

；f31=

；f14=

；f4t=

。找一条增广链：

；为使可行流流量增加，如何改进行可行流：

。（5，1）（3，3）（1，1）（2，f31）（4，f14）（2，f23）（2，1）（5，f4t）（3，0）s1324t575.5网络计划

20世纪50年代以来，国外陆续出现一些计划管理的新方法，如关键路线法（CriticalPathMethod，缩写为CPM），计划评审方法（ProgramEvaluationReviewTechnique，缩写为PETR）等。这些方法都是建立在网络模型基础之上，称为网络计划技术。网络计划技术被地广泛应用于工业、农业、国防、科研等计划管理中，对缩短工期，节约人力、物力和财力，提高经济效益发挥了重要作用。我国数学家华罗庚先生将这些方法总结概括为统筹方法，引入中国并推广应用。统筹方法的基本原理是：从任务的总进度着眼，以任务中各工作所需要的工时为时间因素；按照工作的先后顺序和相互关系作出网络图，以反映任务全貌，实现管理过程的模型化。然后进行时间参数计算，找出计划中的关键工作和关键路线，对任务的各项工作所需的人、财、物通过改善网络计划作出合理安排，得到最优方案并付诸实施。通过对各种评价指标进行定量化分析，在计划的实施过程中，进行有效的监督与控制，以保证任务高质量地完成。58例5

某项新产品投产前全部准备工作如下表，表中列示了各工序所需时间以及它们之间的相互关系。工序工序内容紧前工序工时（周）A市场调整/4B资金筹措/10C需求分析A3D产品设计A6E产品研制D8F制定成本计划C，E2G制定生产计划F3H筹备设备B，G2I原材料准备B，G8J安装设备H5K人员准备G2L准备开工投产I，J，K1问：（1）该新产品投产前全部准备工作的最短工期需要多长时间？（2）如果要提早完成工期，优先考虑压缩哪些工序的工作时间？60一、网络图的绘制什么是网络图：网络图是由节点、弧及权所构成的有向赋权图。(1)用一个箭头（弧）表示一个工序．多道工序就有多个箭头。(2)把各个箭头按工序间的相互制约关系，依流程方向从左向右联系起来。(3)相邻工序交接处画上圆圈（节点），每个节点编上循序号，表示工序的事项。节点在箭尾表示工序的开始，节点在箭头表示工序的完成。(4)把每道工序所需要的时间（权）标在对应的箭头旁．２４３１６５７８４３２５５６３５５２61网络图的组成：（1）工序：指一项有具体内容，需要一定人力，物力，经过一定时间才能完成的生产过程或活动过程．虚工序：不消耗资源，不需要时间，仅用以表示一个工序和另一工序之间相互依存的制约关系，是虚设的工序，用虚箭头表示。工序代号紧前工序ＡＢＣＤ－－Ａ，ＢＢＡＢＣＤ（2）事项：指工序的开始（即开工事件）和工序的结束（完工事件）一个事项对它的前工序是完工事件，对它的后工序是开工事件。

②是工序Ａ的完工事件，是Ｂ的开工事件只有一个总的开工事件，一个总的完工事件。ＡＢ１２３62（3）路线：指网络图中从起点开始顺箭头所指方向，连续不断到达终点为止的一条路。关键路线：指完成各个工序需要时间最长的路线，也称主要矛盾线．绘制网络图的规则：(１)每个工序只出现一次。(２)只能有一个总起始顶点，一个总终止顶点。(３)不能有回路。(４)两个顶点之间只能有一条弧。(５)正确表示工序之间的前行、后继关系。(６)每一工序起始顶点编号小于终止顶点编号，所有编号从１连续编号。２４３１６５７８４３２５５６３５５２63例5

某项新产品投产前全部准备工作如下表，表中列示了各工序所需时间以及它们之间的相互关系。要求编制该项工程的网络计划。工序工序内容紧前工序工时（周）A市场调整/4B资金筹措/10C需求分析A3D产品设计A6E产品研制D8F制定成本计划C，E2G制定生产计划F3H筹备设备B，G2I原材料准备B，G8J安装设备H5K人员准备G2L准备开工投产I，J，K164工序紧前工序工时（周）工序紧前工序工时（周）A/4GF3B/10HB，G2CA3IB，G8DA6JH5ED8KG2FC，E2LI，J，K1AＢＣＤＥＦＧＨＩＫＪＬ４11３６８２３２８２５１１２３４５６７８９1065二、时间参数和关键路线计算

计算网络图中有关的时间参数，主要目的是找出关键路线，为网络计划的优化、调整和执行提供明确的时间概念。通常把网络图中需时最长的路线叫做关键路线，如右图所示网络中双箭线表示的为关键路线，关键路线上的工序称为关键工序。要想使任务按期完或提前完工，就要在关键路线的关键工序上想办法。

网络图的时间参数包括工序所需时间、事项最早、最迟时间，工序的最早、最迟时间及时差等，下面分别叙述。1234564537223466工序时间的确定工序的所需时间可记为，有以下两种情况：⑴完成每道工序所需时间确定，在具备劳动定额资料，或者具有类似工序作业时间消耗的统计资料时，用对比分析来确定作业时间。⑵影响工序因素较多，作业时间难以确定，可以采用三点时间估计法来确定作业时间：a——最快可能完成时间b——最可能完成时间c——最慢可能完成时间一般情况下，可按下列公式近似计算作业时间。67

事项时间参数⑴事项最早时间事项ｊ的最早时间用表示，它表示以ｊ为始点的各工序最早可能开工的时间，也表示以ｊ为终点的各工序的最早可能完工时间。它等于从始点事项到本事项最长路线的时间长度。事项最早时间可用下列递推公式，按照事项编号从小到大（自左向右）顺序逐个计算。其中，为与事项ｊ相邻的各紧前事项的最早时间。是工序的工时，Ａ为网络图弧（工序）的全体，为边界条件．68例5中的事项最早时间：1０AＢＣＤＥＦＧＨＩＫＪＬ４３６８２３２８２５１１２３４５６７８９10８

０４182０23313223251０问（1）该新产品投产前全部准备工作的最短工期需要多长时间？答：最短工期需要32周。70⑵事项的最迟时间事项ｉ的最迟时间用表示，它表明在不影响总工期条件下，以它为终点的各工作的最迟必须完工时间，或以它为始点的工序的最迟必须开工时间。在一般情况下，把任务的最早完工时间作为任务的总工期，所示事项