第八章图与网络优化练习题答案
一、判断下列说法是否正确
1.在任一图G中，当点集V确定后，树图是G中边数最少的连通图。( ? )
2.若图中某点vi有若干个相邻点，与其距离最远的相邻点为vj，则边[vi，vj]必不包含在最小支撑树内。( ? )
3.若图中从v1至各点均有惟一的最短路，则连接v1至其他各点的最短路在去掉重复部分后，恰好构成该图的最小支撑树。( ? )
4.求网络最大流的问题可归结为求解一个线性规划模型。( ? )
二、有一项工程，要埋设电缆将中央控制室与15个控制点连通。下图中标出了允许挖电缆沟的地点和距离（单位：hm）。若电缆线100元/m，挖电缆沟（深1m，宽0.6m）土方30元/m3，其它材料和施工费用50元/m，请作出该项工程预算的最少费用。
1 10 14 5 13 5 12 2 15 5 11 8 12 7 6 4 8 6 2 3 中央控制室 4 10 4 7 8 9 5 4 2 3 4 5 8 11 6 9 5 10 7 6 6 5 9 6 8 3 4 9 12
答案：
求出其最小支撑树为：
1 14 5 中央控制室 13 5 12 2 15 4 4 10 4 11 5 7 3 4 9 8 2 3 7 4 2 3 5 4 5 6 5
埋设电缆的最优方案为总长6200m
所以最少工程预算费为6200×(100+0.6×30+50)=1041600元
11
三、用Dijkstra标号法求出下图中v1到各点的最短距离与最短路径。
2 8 v2 6 v3 7 v4 2 9 5 1 v6 4 v7 1 3 6 v5 2 1 v8 7 v9 3 1 v10 1 9 2 v11 v1 1 6
答案：
2 v2 2 0 v1 8 8 v3 7 v4 15 2 9 7 6 5 1 v6 4 v7 1 3 v5 3 10 6 2 1 11 v8 7 4 v9 3 1 v10 8 1 9 2 20 v11 1 6 的数字。
图中的粗线即为v1到各点的最短路径；v1到各点的最短距离为图中带 四、所给网络中弧旁数字为该弧容量，求网络最大流与最小截集。
13 2 vs 6 v3 3 v2 4 v1 3 4 6 v4 15 7 vt
答案：
第一次迭代：
(vs,13) v1 (13,7)
(0,+∞)
2 6
v3 (vs,6)
3 (vs,2)
v2 3 4 4 6
v4 (v1,4)
15 (7,7)
(v1,7) vt
vs
得增广链：(vs, v1, vt)；按θ=7调整，如上图。 第二次迭代：
12
(vs,5) v1 (13,11) (0,+∞)
2 6
v3 (vs,6)
3 (vs,2)
v2 3 4 (7,7)
(4,4)
(v4,4) vt
v4 (v1,4)
(15,4)
6
vs
得增广链：(vs, v1, v4, vt)；按θ=4调整，如上图。 第三次迭代：
(vs,2) v1 (13,11) (0,+∞)
(2,2)
3 (vs,2)
v2 3 v3 (vs,6)
4 (7,7)
(4,4)
(v4,2) vt
v4 (v2,2)
(15,6)
(6,2)
vs 6
得增广链：(vs, v2, v4, vt)；按θ=2调整，如上图。 第四次迭代：
(vs,2) v1 (13,13) (0,+∞)
(2,2)
(3,2)
(7,7)
(4,4)
(v4,2) vt
v4 (v2,2)
(15,8)
vs 6
v3 (vs,6)
(v1,2) v2
(6,4)
3 4
得增广链：(vs, v1, v2, v4, vt)；按θ=2调整，如上图。 第五次迭代：
v1 (13,13) (0,+∞)
(2,2)
(3,2) (-v4,4)
v2 3 v3 (vs,6)
(4,4) (7,7)
(4,4)
(v4,4) vt
v4 (v3,4)
(15,12)
(6,4)
vs (6,4)
得增广链：(vs, v3, v4, vt)；按θ=4调整，如上图。 第六次迭代：
13
(-v2,2) v1 (13,13) (0,+∞)
(2,2)
(3,2) (v3,2) (3,2) v3 (vs,2)
v2 (4,4) (7,7)
(4,4)
(v4,2) vt
v4 (v2,2)
(15,14)
(6,6)
vs (6,6)
得增广链：(vs, v3, v2, v4, vt)；按θ=2调整，如上图。 第七次迭代：
v1 (13,13) (0,+∞) (2,2) (3,2) (7,7) (4,4) (3,2) v2 (4,4) (6,6) vt
v4 (15,14) vs (6,6) v3
所有fsj=csj（均为饱和弧）标号无法继续，解题结束。
图中可行流即为所求最大流，最大流量为：V?f*??fs1?fs2?fs3?f1t?f4t?21 同时得到最小截集?V1,V1?：其中，V1??vs?,V1??v1,v2,v3,v4,vt? 即?V1,V1????vs,v1?,?vs,v2?,?vs,v3??，其容量也为21。
14
第九章 网络计划练习题及答案
一、判断下列说法是否正确
1. 网络图中任何一个节点都表示前一工作的结束和后一工作的开始。( ? ) 2. 在网络图中只能有一个始点和一个终点。( ? )
3. 工作的总时差越大，表明该工作在整个网络中的机动时间就越大。( ? ) 4. 总时差为零的各项工作所组成的线路就是网络图中的关键路线。( ? )
5. TFi-j是指在不影响其紧后工作最早开始的前提下，工作所具有的机动时间。( ? ) 6. FFi-j是指在不影响工期的前提下，工作所具有的机动时间。( ? ) 二、根据下表资料：
工作代号 A B C D E F G H I 要求：(1)绘制网络计划图； 紧前工作 —— A A B、C B D D E、G F、H 工作持续时间（Di-j） 15 15 14 10 6 6 1 30 8 (2)用标号法计算时间参数：ESi-j、EFi-j、LSi-j、LFi-j、TFi-j、FFi-j； (3)确定关键路线。
答案：
(1)
B 15 3 E 6 6 G 1 H 30 1 A 15 2 C 14 7 F 6 I 8 8 4 D 10 5 ESi-j LSi-j TFi-j (2)各时间参数如图所示（EFi-j LFi-j FFi-j ）。
15
1 0 0 0 15 15 0 A 15 15 15 0 30 30 0 B 15 3 30 35 5 36 41 5 E 6 2 15 16 1 29 30 1 C 14 4 30 30 0 40 40 0 D 10 5 6 30 40 40 0 41 41 0 G 1 40 65 25 46 71 25 F 6 41 41 0 71 71 0 H 7 71 71 0 79 79 0 I 8 8
(3)图中TFi-j为零的各工作构成了关键路线（粗红线），即关键工作为：A,B,D,G,H,I。 三、某项工程的各工作及其持续时间如下表所示：
工作名称 紧后工作 工作持续时间（天） A 4 B、C B 6 D、E C E 5 D 8 F、G E 5 F、G F 7 — G 9 — 要求：绘制网络图，用标号法计算时间参数，确定关键路线，计算工程完工期。 答案：
4 4 0 10 10 0 0 0 0 4 4 0 10 10 0 18 18 0 25 27 2 25 27 2 18 20 2 25 27 0 4 8 4 9 13 1 10 13 3 15 18 3 B 6 3 D 8 6 F 0 ’时间参数： ESi-j LSi-j TFi-j EFi-j LFi-j FFi-j 1 A 4 2 F 7 C 5 4 E 5 5 G 9
18 18 0 27 27 0 关键路线： 工程完工期：27天 7 T=27
16