四、图论
1、求下图中从v1到v3最短路。
v 1
v 3
v 5
4
6
从节点 1到节点3的最短路 *************************
起点 终点 距离 ---- ---- ---- 1 2 1 2 3 6
此问题的解为:7 2、最小生成树
电信公司要在15个城市之间铺设光缆，这些城市的位置及相互之间的铺设光缆的费用如下图所示。
试求出一个连接在15个城市的铺设方案，使得总费用最小。
v 1
v 2
v 3
v 4v 5v 6
v 7v 8v 9
v 10v 11v 12
v 13v 14v 15
22
41
1
3
1
4
5
6
4
2
2
3
2
3
1
3
5
1
3
4
此问题的最小生成树如下：
*************************
起点终点距离
---- ---- ----
1 4 1
1 2 2
2 5 2
5 8 1
5 6 2
6 3 1
8 7 2
8 9 3
9 12 2
12 11 4
11 10 1
10 13 3
13 14 1
14 15 3
此问题的解为:28
3、最短路问题
例. 求下图中从v1到各点的最短路，并指出有哪些点是不可达到的。
v
v
7
v
8
v
4
从节点 1到节点2的最短路
*************************
起点终点距离
---- ---- ---- 1 2 4
此问题的解为:4
1到3没有路
1到4没有路
从节点 1到节点5的最短路
*************************
起点终点距离 ---- ---- ---- 1 5 1
此问题的解为:1
从节点 1到节点6的最短路
*************************
起点终点距离 ---- ---- ---- 1 5 1 5 6 6
此问题的解为:7
从节点 1到节点7的最短路
*************************
起点终点距离 ---- ---- ---- 1 7 3
此问题的解为:3
从节点 1到节点8的最短路
*************************
起点终点距离 ---- ---- ---- 1 5 1 5 6 6
6 8 3
此问题的解为:10
4、最短路问题
有6个村庄，各村庄的距离如下图所示。
现在要开办一所小学，问应该建在哪个村庄，才能使得各村的学生上学的总路程最短？
v 1
v
2
v
3
v
4
v
5
v
6 3
4
6
3
8
1
14
2
7
最小为17，选择村庄2或者村庄5建立学校
5、例（多发点多收点的最大流问题）某产品有两个产地s1、s2，三个销地t1、t2、t3。
运输系统如下图所示，其中v1和v2是两个中转站，各弧旁的数字是最大运输能力。
求从产地到销地的最大运输量。
V1-V2流量为2
s 1
s 2
t 2
从节点 1到节点9的最大流 *************************
起点 终点 距离 ---- ---- ---- 1 2 27 1 3 18 2 6 10 2 4 5
s 1
s 2
27
27
C8
2 5 12
3 5 6 3 8 12
4 6 7 4 7 0
5 4 2 5 7
6 5 8 10 6 9 1
7 7 9 6
8
9 22
此问题的解为:45
6 例（顶点有容量约束的最大流问题）某油田s 通过输油管道向一炼油厂t 输送原油，中间经过三个泵站v 1、v 2和v 3，管道的输送能力和各泵站的输送能力如下图。
求这个系统的最大输送能力。
s
t
从节点 1到节点8的最大流 *************************
起点 终点 距离 ---- ---- ---- 1 2 9 1 3 13 2 4 9 3 5 13 4 8 8 5 8 11 4 6 1 5 6 2 6 7 3 7 8 3
此问题的解为:22
7. . 求下图所示网络的最小费用最大流，弧旁数字为),(ij ij u c 表示 (单位成本，容
量）
8. 北京（Pe）、东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)各城市之间的航线距离如下表：
由上述交通网络的数据确定最小生成树。
此问题的最小生成树如下：
*************************
起点终点距离
---- ---- ----
1 4 21
1 3 35
3 2 21
1 5 51
5 6 13
此问题的解为:141
9. 某台机器可连续工作4年，也可于每年末卖掉，换一台新的。
已知于各年初购置一台新机器的价格及不同役龄机器年末的的处理价如下表所示。
又新机器第一年运行及维修费为0.3万元，使用1-3年后机器每年的运行及维修费用分别为0.8，1.5，2.0万元。
试确定该机器的最优更新策略，使4年内用于更换、购买及运行维修的总费用为最省。
从节点 1到节点5的最短路
*************************
起点终点距离
---- ---- ----
1 2 0.8
2 3 0.9
3 5 2.3
此问题的解为:4
设备够买3次，分别于2001、2002、2003年购买
10. 某产品从仓库运往市场销售。
已知各仓库的可供量、各市场需求量及从i仓库至j市场的路径的运输能力如下表所示（表中数字0代表无路可通），试求从仓库可运往市场的最大流量，各市场需求能否满足？
C20 10 40 5 100 需求量20 20 60 20
C5 C6 C7 C8 C1
C2 30 10 0 40 20
C3 0 0 10 50 20
C4 20 10 40 5 100
C9 20 20 60 20
软件输入数据
答案110
11. 某单位招收懂俄、英、日、德、法文的翻译各一人，有5人应聘。
已知乙懂俄文，甲、乙、丙、丁懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法文，问这5个人是否都能得到聘书？最多几个得到聘书，招聘后每人从事哪一方面翻译工作？
12. 下表给出某运输问题的产销平衡表与单位运价表。
将此问题转化为最小费用最大流问题，画出网络图并求数值解。
产量销地 1 2 3 产量
A B 20
30
24
22
5
20
8
7
销量 4 5 6
13. 一只狼、一头山羊和一箩卷心菜在河的同侧。
一个摆渡人要将它们运过河去，但由于船小，他一次只能运三者之一过河。
显然，不管是狼和山羊，还是山羊和卷心菜，都不能在无人监视的情况下留在一起。
问摆渡人应怎样把它们运过河去？
（注：本资料素材和资料部分来自网络，仅供参考。
请预览后才下载，期待你的好评与关注！）。