判 断 题
判断正误，如果错误请更正
第六章 网络模型
1. 连通图G的部分树是取图G的点和G的所有边组成的树。 2. Dijkstra算法要求边的长度非负。 3. Floyd算法要求边的长度非负。 4. 割集中弧的流量之和称为割量。 5. 最小割集等于最大流量。 6. 求最小树可用破圈法。
7. 在最短路问题中，发点到收点的最短路长是唯一的。 8. 在最大流问题中，最大流是唯一的。
9. 最大流问题是找一条从发点到收点的路，使得通过这条路的流量最大。 10. 容量Cij是弧（i,j）的实际通过量。
11. 可行流是最大流的充要条件是不存在发点到收点的增广链。 12. 任意可行流的流量不超过任意割量。 13. 任意可行流的流量不小于最小割量。 14. 可行流的流量等于每条弧上的流量之和。 15. Dijkstra算法是求最大流的一种算法。
16. 避圈法（加边法）是：去掉图中所有边，从最短边开始添加，加边的过程中不能形
成圈，直到有n条边（n为图的点数）。 17. 连通图一定有支撑树。
18. μ是一条增广链，则后向弧上满足流量f>=0。 19. 最大流量等于最大流。
20. 旅行售货员问题是遍历每一条边的问题。
选择题
在下列各题中，从4个备选答案中选出一个或从5个备选答案中选出2~5个正确答案。
第6章 网络模型
1. μ关于可行流f的 增广链，则在μ上有 A 对任意（ i，j）∈μ，有fij<=cij B
+，
对任意（ i，j）∈μ，fij<=cij C 对任意（ i，j）∈μ，有fij<=cij D 对
+，
-
2. 3.
4. 5.
任意（ i，j）∈μ，有fij>0 E对任意（ i，j）∈μ，有fij>=0
连通图G有n个点，其部分树是T ，则有 A T 有n点n条边 B T的长度等于G的每条边的长度之和。 C T有n个点n-1条边 D T 有n-1个点 n条边 设P是图G 到Vs到Vt的最段短路 ，则有 A P的最短路长等于Vs到Vt的最大流量 B P的长度等于G的每条边的长度之和 C P的长度等于P的每条边的长度之和 D P有n 个点n-1 条边
求最短路的计算方法有 A Dijkstra 法 B Floyd法 C 加边法 D 破圈法 E Ford-fulkerson 算法
求最大流的方法有 A Dijkstra 法 B Floyd法 C 加边法 D 破圈法 E Ford-fulkerson 算法
--
1
6. 下列说法正确的是 A 割集是子图 B 割量等于割集中弧的流量之和 C 割
量大于等于最大流量 D 割量小于等于最大流量
7. 下列错误的结论是 A 容量不超过流量 B 流量非负 C 容量非负 D 发点流
出的合流等于流入收点的合流
8. 下列正确的结论是 A 最大流等于最大流量 B 可行流是最大流当且仅当存在发
点到收点的增广链 C可行流是最大流当且仅当不存在发点到收点的增广链 D 调整量等于增广链上点标号的最大值
9. 下列正确的结论是 A 最大流量等于最大截量 B 最大流量等于最小截量 C 任
意流量不小于最小截量 D 最大流量不小于任意截量
计算题
6.1 求以下网络的最小支撑树和从节点1到节点12的最短路径。
3 4 7
① ② ③ ④ 6 2 5 1 1 9 8 ⑤ ⑥ ⑦ ⑧ 4 8 6 3
⑨ ⑩ ⑾ ⑿
7 2 4 解答： 最小支撑树为 ，权值为35； 3 4
① ② ③ ④ 2 5 1 1
⑤ ⑥ ⑦ ⑧ 4 6 3
⑨ ⑩ ⑾ ⑿
2 4 最短路径为1-2-3-4-8-12，路径为18。
6.2 求以下网络的最大流的流量以及最小割集的解集和最小割集的容量。
6
② ⑤ 7 4 3 10 9 6 4
① ③ ⑥ ⑧ 3 1 4 8 5
④ ⑦
解答： [6] 6
2
② ⑤ [7] 7 4[1] [3] 3 10[9] 6[6]
① [7]9 ③ ⑥ [4]4 ⑧ 3 [2] [1] 1
[4] 4 8[6] 5[5]
④ ⑦
最大流流量为18，最小割集容量为18，割集为x{1,2,3,4},x～{5,6,7,8}。
6.3 求以下网络的最小支撑树和从节点1到节点7的最短路径。
7
② ⑤
5 2 6 3 Wij
1 ① ④ ⑦ 7 2
2 6 ③ ⑥
4 解答：
② ⑤
2 3 Wij
1 ① ④ ⑦ 2 2 ③ ⑥
4
最短路为1-3-6-5-7. 最短路长为10。最小支撑树如图所示，权为14。 6．4 求以下网络的最大流的流量以及最小割集的解集和最小割集的容量。 10
② ⑤ 3 10 1 2 3 1
① ④ ⑥ ⑧ 5 2
4 5 9 ③ ⑦ 解答： [3] 10 ② ⑤ [3] 3 10[0] [0] 1 3[3] [1]1 [0]2 ① ④ ⑥ ⑧ 5 [1] [1]2
3