图4-2-1

3. 分别用Kruskal算法（避圈法）和Prim算法求下图的最小生成树。

图4-2-4

4. 已知9个人v1, v2, …, v9，其中v1与两个人握过手，v2, v3各与4个人握过手，

v4, v5, v6, v7各与5个人握过手，v8, v9各与6个人握过手，证明：9个人中至少有3个人相互握过手。 5. 证明：把网络中的节点划分成两个集合V 和V’，两部分节点的连线中最短

的边必定在最小树中。 6. 已知世界六大城市：Pe , N , PA , L , T , M，试在由【表4-2-1】所示交通网络

的数据中确定最小树。

表4-2-1

Pe T PA M

Pe X 13 51 77 T 13 X 60 70 PA 51 60 X 57 M 77 70 57 X N 68 67 36 20 L 50 59 2 55 13

N L 68 50 67 59 36 2 20 55 X 34 34 X 7. 求下图中v1到所有点的最短路径及其长度。(要求最短路用双线在图中标出，

保留图中的标记值)

v5v21v154v3v41275v735632v817v6

图4-2-9

8. 将上图看作无向图，写出边权邻接矩阵，用Prim算法求最大生成树，并画

出该树图。

4.3 最短路问题

1. 试述Dijkstra算法的基本思路。

2. 在下图4-3-1中，求v1到其他各点的最短路（要过程）。

图4-3-1

3. 某软件公司生产4种系统的软件，每种软件的型号、计算速度、需求量及生

产一件的可变费用（元/件）如下表所示。不同规格的软件生产时需调整设备，其固定费用Cd为2000万元。当某种软件不能满足需求时，可用更新型

14

号的软件替代。问在满足需求的情况下如何组织生产，使总费用最小。

表4-3-2

软件型号 计算速度S（次/秒） 需求量D（万件） 可变费用C（元/件） A 15000 1000 4 B 25000 1200 5 C 40000 2700 6 D 60000 1800 10 4.4 网路的最大流、最小截集

1. 试述什么是截集、截量以及最大流最小截量定理。

2. 在下图中，已给出流值为6的f流，试判断它是否为最小费用流？若不是，求出该流值下的最小费用流。（图中，弧上所标的三个数值分别为容量、流量和费用） 3. 下图给出网络上各弧的容量和已有的流量 (cij , fij)

1) 确定所有的截集； 2) 求最小截集的容量； 3) 证明指出的流是最大流。

4. 运输公司接到任务需将产地P1，P2 两地所产的物质经S1，S2，S3三个中转

站运往用户U1，U2两处；公司所获利润与运输总量成正比。已知P1，P2有物资分别为120吨和240吨，U1，U2各需180吨和200吨，全部交通网络布置与交通干线容量见下图4-4-4，问：运输公司应如何制定运输方案？

图4-4-4

5. 下图中，给出现有流（边旁边的数值分别表示容量和实际流量），试用标号

法求出最大流。

15

图4-4-8

6. 求出如图4-4-12所示的网络最小费用最大流，每条弧旁边的数值为 (dij, cij)

（分别代表费用和容量）。

图4-4-12

7. 下述判断正确与否：可行流f的流量为零，即V( f )＝0，当且仅当f是零流。 8. 求下面网络s到t的最大流和最小截，从给定的可行流开始标号法。(要求每得到一个可行流后，即每次增广之后，重新画一个图，标上增广后的可行流，再进行标号法)

v1(4,0)s(4,4)(3,0)v3(2,0)(3,0)v2(4,4)(3,0)(6,0)(4,0)图4-4-17

v4(8,4)t(9,0)(10,0)v5

4.5 欧拉回路和中国邮递员问题

1. 何为欧拉回路？

16