Page 216 - 数学建模算法与应用

Mathematical Modeling Algorithms and Applications
数学建模算法与应用

第四节 树与网络流问题的解决

一、基本概念

连通的无圈图叫做树，记之为 T 。若图 G 满足 V(G)=V(T) ， E(T)Ì E(G) ，
则称 T 是 G 的生成树。图 G 连通的充分必要条件为 G 有生成树。一个连通图的
生成树的个数很多，用 t(G) 表示 G 的生成树的个数，则有公式

其中 G -e 表示从 G 上删除边 e ，G·e 表示把 e 的长度收缩为零得到的图。
树有下面常用的五个充要条件。
定理 1 1.G 是树当且仅当 G 中任二顶点之间有且仅有一条轨道。

2.G 是树当且仅当 G 无圈，且
3.G 是树当且仅当 G 连通，且
（iv）G 是树当且仅当 G 连通，且 不连通

（v）G 是树当且仅当 G 无圈， 恰有一个圆

二、应用—连线问题

欲修筑连接 n 个城市的铁路，已知 i 城与 j 城之间的铁路造价为 Cij ，设计
一个线路图，使总造价最低。

连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具最小
权的生成树叫做最小生成树。
下面介绍构造最小生成树的两种常用算法。
（一） prim 算法构造最小生成树

设置两个集合 P 和 Q ，其中 P 用于存放 G 的最小生成树中的顶点，集合 Q
存放 G 的最小生成树中的边。令集合 P 的初值为 P={v1}（假设构造最小生成树时，
从顶点 v1 出发），集合 Q 的初值为 Q=F。prim 算法的思想是，从所有 pÎP ，

vÎV － P 的边中，选取具有最小权值的边 pv ，将顶点 v 加入集合 P 中，将边 pv
加入集合 Q 中，如此不断重复，直到 P=V 时，最小生成树构造完毕，这时集合
Q 中包含了最小生成树的所有边。

206