网络是反映对象之间关系的一种工具
因此，可以说，在一般情况下，网络中点的相对位置如何， 点与点之间联线的长短曲直，对于反映对象之间的关系，并 不是重要的，例如哥尼斯堡七桥问题。 如例2，也可以用网络去反映五个球队的比赛情况，这与例 3没有本质的区别。所以，图论中的图与几何图、工程图等 是不同的。
8
6.2 最小生成树算法
最小生成树算法是以来链接一个网络所有的节点，使得树上 边的总长度最小。例如，在几个城镇之间修路，使得任意两 个城镇之间都有路相连，之间可以穿过其他城镇那么最经济 的道路网络设计方案就是道路里程最小。 令N={1,2,…,n}是网络中节点的集合，定义：
Ck 在第k步时已经连接起来的节点集合 Ck 在第k步以后需
4
例1
北京
天津
是北京、上海等十个
城市间的铁路交通图。
与此类似的还有电话 线分布图、煤气管道
郑州
图、航空路线图等。
济南 徐州
武汉
南京
青岛 连云港 上海
5
例2
分别用点v1,v2,v3,v4,v5分别代表甲、乙、 丙、丁、戊五支球队。若有两支球队之间比赛 过，就在相应的点之间联一条线，且这条线不 过其他点。如下图所示：
13
6.3 最短路径问题
6.3.1 最短路应用实例
RentCar公司开展了一项4年一周期的汽车更换政策，在每一 年的开始，消费者都可以选择继续使用购买的汽车，也可以选 择更换汽车。一辆汽车最少使用1年，最多3年，下表给出了 汽车更换的费用，它取决于车辆购置时的年数以及使用年限。 客户该如何更换汽车？
1
9
15
3
7
4
C1
迭代1
5
6
C1
2
3
5
1
9
1
6
5
3
74
6
4
C2
迭代2
C2
C3
2
3
5
1
C4
2
3
5
1
1
6
5
3
8
C3
1
6
5
3
8
C4
74 4
45
6
3
6
4
迭代3
迭代4
12
C5
2
3
5
1
1
5
6 3
C5
45
10
3
6
4
迭代5
2 1
1
5
3
45
4
3
5
可选边
3
6
迭代6 （最小生成树）
最小生成树算法在第6步给出了问题的解，要服务的电视 网络线缆长度为1+3+4+3+5=16
v1
v2
可知需要4个库房， 其中一个答案是：
v8 v7
v6
v3
{ v1 }
{ v2, v4, v7 }
v4
{ v3, v5 }
{ v6, v8 }
还有其他的答案。 7 v5
从以上几个例子可见
可以用由点及点与点的联线所构成的网络，去反映实际生活 中，某些对象之间的某个特定的关系，通常用点代表研究的 对象（如城市、球队、药品等等），用点与点的联线表示这 两个对象之间有特定的关系（如两个城市间有铁路线、两个 球队比赛过、两种药品不能存放在同一个库房里等）。
9
最小生成树算法步骤：
第0步 令 C0 ,C0 N
第1步 从 C0 中的任意一个节点i开始，令C1={i}, 那么
C1 N i ，设定 k=2.
一般的第k步 在还没有连接的节点集合 Ck1 中选择一
个节点 j*，使得j*到Ck-1中某个节点之间的弧长
最小，然后将
j*
放在Ck-1，从
Ck
中删除
2
网络模型的定义
网络是由节点(node)和弧(arc)集合组成，用符号(N,A)表示， 其中N表示节点的集合，A表示弧的集合。
1
3
5 N={1，2，3，4，5}
A={(1,2),(1,3),(2,3),(2,5),(3,4),(3,5),(4,2),(4,5)}
2
4
如果一条弧上的其中一个方向的流量是正数，相反方向就是
为零，该弧是有向的(directed)，如果所有弧上的容量都是有 向的，则网络是有向网络。将两点之间链接起来，并经过其
他的一些节点的这一些列弧，称之为路径(path),如果经过路 径又能回到自身，则这些路径称之为圈(Loop),如果网络中没 有圈，网络就是树(tree),如果该树包括了图上所有的节点，则 是生成树。
开始购买汽 车的年数
给定年限的更换费用
1
2
3
1
4000
5400
9800
2
4300
6200
8700
3
4800
7100
—
4
4900
—
—
14
该问题可以描述为网络模型，节点1到5表示第1年到第5年每 年的开始。
与节点1(第1年)有弧相连的节点只有2,3,4,因为按照轨道汽车 的使用年限为1到3年。同理，可以推断出从其他节点出发的 弧。每条弧的长度等于更换费用。那么问题等价于求一条从 节点1到5的最短路径。
9800 5400
7100
1 4000 2 4300 3 4800 4 4900 5
6200 8700
可以知道，最短路是1→3→5. 这个解说明汽车在第1年购
买，然后使用2年，在第3年开始的时候更换新的汽车，一
直使用到年底。
15
例
Smart每天开车去工作，如果找最短走，会被限速因此行程 时间不是最短，如果超速会被罚款，所以最短路对smart而 言不是最好选择. 假设已知各个路段相应不被罚款的概率已 知，如下图。他想选择一条不被警察罚款的概率最大的路径， 该如何选择？
1
j*，即
Ck = Ck-1 + j* , Ck = Ck-1 j*
10
例
中西部有线电视公司正在计划为5个新的居民区提供有线电 视服务，下图给出了小区之间可以铺设电缆的情况以及相应 的距离。确定最经济的电缆铺设方案，使得5个小区可以连 接起来。
2
3
5
1
9
1
5
6 3
8
4
7
5
10
3
6
4
11
2
第6章 网络模型
1
6.1 网络模型的应用范围和定义
大量的运筹学问题都可以应用网络建模来求解： a) 在墨西哥海湾上需要设计一个海面上的天然气管道网络，
将各个井口链接到岸边的运输点，模型目标是最小化管 道建设费用。 b) 在已经存在的道路网络中，求起讫点之间的最短路径. c) 求山西煤矿到北京的发电厂的煤浆管道网络的最大运输 量 d) 给一个工程项目中的各项活动确定时间表
3
欧拉 (Euler) 在1736 年发表图论方面的第一篇论 文，解决了著名的哥尼斯堡七桥问题。哥尼斯堡城中有 一条河叫普雷格尔河，该河中有两个小岛，河上有七座 桥，参见图 5.1(a) 。
当时那里的居民热衷于这样的问题：一个散步者能 否走过七座桥，且每座桥只走过一次，最后回到出发点。
A D
C B
v1 v2
v5 v4
v3
可知各队之间的比赛情况如下： 甲—— 乙、丙、丁、戊 乙—— 甲、丙 丙—— 甲、乙、丁 丁—— 甲、丙、戊 戊—— 甲、丁
6
例3 “染色问题”
储存8种化学药品，其中某些药品不能 存放在同一个库房里。 用v1,v2,…,v8分别代 表这8种药品。规定若两种药品不能存放在 一起，则其相应的点之间联一条线。如下 图所示：