下图是一个城镇的地图，现在要在该城镇的各地点铺设 管道，已知各点相互之间的铺设费用（单位：千元）， 如何设计铺设线路，使各地互通的总铺设费用最少？
8
3
74
5
10
7
2
6
7 9
12 8
51
5
4
解：求各边相通且总费用最少的方案，实际上求最小树， 保证了各点之间连通且费用最少。
3
4
7
5
2
1
4
5
其总费用为：31千元
用一条边把代表这两个项目
v2
的顶点连接起来。这样得到
v3
下图
v1
为了解决这个问题，只需
找到一条包含所有顶点的
v4
初等链。
v5
如：{v4，v1，v2，v3，v5}是一条初等链，对应的比赛是： 100m自由泳，50m仰泳，50m蛙泳，100m碟泳，200m自由泳。
此问题的方案不唯一。
例 2.线路铺设问题
2
V
C0= 3
V
22 2 33 3 44 4
222 333 444
4 8 3 1 0 3 V 6 3 0
5
4 55 5 5 5 5 V 66 6 6 6 6
5
V
V
6 迭代得到最短距离矩阵D0和相应6的中间点矩阵C0如下：
V
1
V
2
V D6=3
V
V1 V2
02 20 64 75
V3 V4
67 45 01 10
如下图A、B、C、D、E、F分别表示陆地和岛屿，若河的两岸 分别被敌对两方部队占领，问至少切断哪几座桥梁才能阻止对 方部队过河？
A
B
C
D
E
F
陆地、河流及桥梁示意图
解：
将A，B，C，D，E，F分别用一个点表示，相互之间有桥相连 的连一条弧；弧的容量就是两点间的桥梁数；设一个方向，得 到网络图如下：
A
从一个房间到另一房间相当于从这个顶点有一条链能到另一 个顶点。
C
I
B
J 图的任意一个连通
H
A
D
G
的生成子图，在它
的所有边对应的隔 K 墙上开门，即可达
到要求。
E
F
令所有边的权为1，为了使开的门尽可能少，就要使这个连 通子图的生成子图的边尽可能少，即求图的最小生成树。
B
C
I J
H
D A
K G
E
F
最小生成树
D 2,0
C 1,1 (B,1)
2,0
E
F
由上图得知：已标号点为A，B，C，而D，E，F不能获得标号， 从而知道该最大流对应的最小割为{（A，E），（C，D）， （C，F）}因此，切断AE，CD，CF三座桥梁，即可阻止对方 部队过河。
例11:生产计划问题
某工厂与客户签定合同,当月起连续三个月每月末向客户提 供某种产品。该厂三个月的生产能力、单位产品生产成本及 客户需求见下表。
0 50 150 175 200 275 40 0 80 100 120 180 180 120 0 30 60 150 D= 70 50 10 0 10 40 280 210 70 35 0 105 495 405 225 180 135 0
D = [1065 835 535 520 525 750]
2
11
1
B
D2
2
C1 12
2
E
2
F
割是分离A和F的弧的集合,若切断一个割的所有弧对应的桥梁, 就可切断A和F之间的线路。切断最小割包含的弧对应的桥梁， 是切断A和F之间线路的桥梁数最少的方法。
由最大流最小割定理，分离A和F的最小割容量等于由A到F的 最大流量
A(0,+)
B (A,1)
1,0
2,1
年份
1
2
3
4
5
表1
购置费
10
10
11
12 13
使用年限 0 -1
1- 2
2- 3 3- 4 4- 5 表2
维修费
5
6
8
11 15
解：为解决好这一问题，建立下述网络模型，并用最短路 法求解。
令： vi — 第 i 年年初购进一台新设备，i=1 , 2 , 3 , 4 , 5 , 6 v6 指第五年年末。
例3.设备更新问题
某单位使用一台生产设备，在每年年底，单位领导都要决 策下年度是购买新设备还是继续使用旧设备。
若购置新设备，需要支付一笔购置费；如果继续使用旧的， 则要支付一定的维修费用。
一般说来，维修费随设备使用年限的延长而增加。根据以 往的统计资料，已经估算出设备在各年年初的价格和不同 使用年限的年维修费用，分别示于表1和表2。
T
+,2
X2
10,62
V3
结 束！
V5 V6
89 69 25 14
V 1 V1 V2 V3 V4 V5 V6
V 11 2345
2
V
C6= 3
V
22 23 33
2345 3345 4445
4 8 621 03 V 11 9 5 4 3 0
5
V
6
4 44 4555 V 55 5566
5
V
6
考虑各点的学习人数，对矩阵D6的每一行乘以相应各点的 人数，得到：
v2
6
21ຫໍສະໝຸດ v1487
v3
3
v4 6
1
v6
3 v5
解：首先计算各点对间的最短路，每个学习者为使所走的路
程最短，应走最短路。
V
1
V1 V2 V3 V4 V5 V6
V 0 2 7
V
V1 V2 V3 V4 V5
1
V6
V 11 1 1 1 1
2
V
D0= 3
V
2 04 6 8 74 0 1 3 6 1 0 1 6
A1
1
A2
S
1
1 A3
A4
1 A5
B1
B2
1
1
B3 1
T
B4 1
B5
A1
1,0
A2
S
1,1
1,1 A3
A4
1,1 A5
B1
B2
1,1
1,1
B3 1,0
T
B4 1,1
B5
fmax=4，知道最多能有4架飞机同时出航。 分配方案为：
A2 - B1；A3 - B4 ; A4 - B2；A5 - B5
例9：桥梁切断问题
市场 仓库
A1 A2 A3
B1 B2 B3 B4
30 10 0 40 0 0 10 50 20 10 40 5
需 求 量 20 20 60 20
供应量
20 20 100
用点A1，A2，A3表示三个仓库；点B1，B2，B3，B4表示四个市 场；若仓库与市场间有线路可通，则在对应点间连一条弧，
弧的容量就是线路的容量。
50
55
2 40 15 30
60
65
3 20 10 30
55
62
解：构造网络图如下
X1 ——工厂处于正常生产状态 X2 ——工厂处于加班生产状态 Vj ——第j个月生产产品的存储与供货点。 增设起点S和终点T。这样问题就转化为求从S到T的最小费用最大流问题。
V1
+,2
S
+,0 X1
40,60 V2 30,0
B3
f=110
A3 5,5
B4
由于最大流量为110,而市场总需求量为120, 所以现有线路容量 不能满足市场的需求。
由上图得到，市场B3的需求量不能满足，而仓库A3的供应量 尚有余量，所以考虑将弧（A3，B3）容量增至50，可满足市 场的需要。
例8：分派问题
某飞行队有5名正驾驶员和5名副驾驶员。由于种种原因，某些 正、副驾驶员不能同时飞行，某些则可以，如下表所示，（* 表示可同机飞行）每架飞机出航时需要正、副驾驶员各一人， 问最多能有几架飞机同时出航？应如何安排正、副驾驶员？
V1…….V4：V1- V2 - V3 - V4 V2…….V4： V2 - V3 - V4 V3…….V4： V3 - V4 V5…….V4： V5 - V4 V6…….V4： V6- V5 - V4
最短路程为520，即夜校应设在v4点，由 C6得到相应路径。
例 6：网络运输容量问题
有三个仓库运送某种产品到四个市场上去，仓库的供应量 是20、20和100件，市场需求量是20、20、60和20件。仓库 与市场之间的线路上的容量如下表所示（容量零表示两点 之间无直接的线路可通）。确定现有线路容量是否能满足 市场的需求。若不能，应修改哪条线路的容量。
（vi，vj）— 第 i年年初引进新设备一直使用到第 j 年年初。 Wij— 第 i 年年初购进的新设备一直使用到第 j 年年初这段
期间的全部费用。
v2
15
21
15 40 29
30
21
v1
29
40 55
v3
16 22
23
v4
17
v6
18
v5
求解得v1到v6得最短路径为： v1-v3-v6，最短路长为51。 设备更新的计划是：第一年初购置一台新设备，使用到第二年末，
已知单位产品每积压一个月需支付存储费2元。在签定合同 时，工厂有该产品的库存量5个，工厂希望在第三个月末完 成合同后还能存储该产品10个。问工厂应如何安排生产计划， 使在满足上述条件的情况下，总的费用最小？
正常生 加班生
单位产品正 单位产品加