最小生成树-数学建模.ppt

prim()算法动态图形 演示：
a
18 16
19 14
b
12 7
5
c
3
e
8
gHale Waihona Puke 27d f21
所得生成树权值和 = 14+8+3+5+16+21 = 67
样例题目：
描述
最近，小Hi很喜欢玩的一款游戏模拟城市开放出了新Mod， 在这个Mod中，玩家可以拥有不止一个城市了！ 但是，问题也接踵而来——小Hi现在手上拥有N座城市， 且已知这N座城市中任意两座城市之间建造道路所需要的费 用，小Hi希望知道，最少花费多少就可以使得任意两座城市 都可以通过所建造的道路互相到达（假设有A、B、C三座城 市，只需要在AB之间和BC之间建造道路，那么AC之间也是 可以通过这两条道路连通的）。
最小生成树 MST minimum-cost spannirng tree 2015/1/28
最小生成树
问题：
假设要在 n 个城市之间建立通讯 联络网，则连通 n 个城市只需要 修建 n-1条线路，如何在最节省经 费的前提下建立这个通讯网？
该问题等价于：
构造网的一棵最 小生成树， 即：在 e 条带权 的边中选取 n-1 条边 （不构成回路）
程序代码：
kruskal 算法
问题的出发点：为使生成树上边的权值之和达到最小，则应使生成树 中每一条边的权值尽可能地小。 算法思路： 1. 建立一个边集（该边集按照权值成“递增”顺序）（一般用结构体） 2.从边集开始找边加到树上。当第一条边加到树上后，此时树上有两 个节点，此时的权值和就是这条边。接着添加第二条边，这是就要判断 这条边的加入会不会和之前的已经加入到树上的那些边组成回路呢？如 果组成回路，则说明该边不可以加到该生成树上否则可以。就这样一直 往生成树上加边，直到生成树上有n-1条边了。退出循环，输出权值总 和。

不含圈的连通图树的基本性质若图是连通的且qp1则该图不含圈因此是树三最小生成树最小生成树的定义最小生成树的定理ijij四寻找最小生成树的方法kruskal方法矩阵计算法kruskal方法习题第一版
第二节 最小生成树
什么是树？ 构造生成树的方法 最小生成树问题 寻找最小生成树的方法
一、什么是树？
树：不含圈的连通图 树的基本性质
最小生成树的定义 最小生成树的定理
v4
v1
水塔 6 1 5 7
5
v5
4 3 4
v6
v2
2
v3
最小生成树的数学模型
min
( i , j ) A
w
ij
xij
( i , j ) A
x
ij
n 1 S 1, S A
( i , j )S
x
ij
xij 0,1
四、寻找最小生成树的方法
5
矩阵计算结果
v4
6 5
v5
4
v1
5
1
7
3 4
v6
v2
2
v3
习题
第一版：

P. 265，第四章习题1、2。
第二版：

P. 284，第四章习题3、5。
矩阵计算方法
v1 v2
T v1 0
v3 v4
v5 v6
T v2 5 0 2 1 7 T v3 2 0 3 4 T v4 6 1 0 5 v5 7 3 5 0 4 v6 4 4 0 6
5
矩阵计算方法
v1 v2
T v1 0
v3 v4
v5 v6
T v2 5 0 2 1 7 v3 2 0 3 4 v4 6 1 0 5 v5 7 3 5 0 4 v6 4 4 0 6

1、最灵繁的人也看不见自己的背脊。——非洲 2、最困难的事情就是认识自己。——希腊 3、有勇气承担命运这才是英雄好汉。——黑塞 4、与肝胆人共事，无字句处读书。——周恩来 5、阅读使人充实，会谈使人敏捷，写作使人精确。——培根

图论课件--最小生成树
1、纪律是管理关系的形式。——阿法 纳西耶 夫 2、改革如果不讲纪律，就难以成功。
3、道德行为训练，不是通过语言影响 ，而是 让儿童 练习良 好道德 行为， 克服懒 惰、轻 率、不 守纪律 、颓废 等不良 行为。 4、学校没有纪律便如磨房里没有水。 ——夸 美纽斯
5、教导儿童服从真理、服从集体，养 成儿童 自觉的 纪律性 ，这是 儿童道 德教育 最重要 的部分 。—— 陈鹤琴

(a)
图11-12
(b)
(c)
§3 最小生成树问题
一、求解最小生成树的破圈算法 算法的步骤：
1、在给定的赋权的连通图上任找一个圈。
2、在所找的圈中去掉一个权数最大的边（如果有两条或两条 以上的边都是权数最大的边，则任意去掉其中一条）。
3、如果所余下的图已不包含圈，则计算结束，所余下的图即最小生成树问题
给了一个无向图G=(V,E)，我们保留G的所有点，而删掉部分G的边或 者说保留一部分G的边，所获得的图G，称之为G的生成子图。在图11-12中， (b)和(c)都是(a)的生成子图。 如果图G的一个生成子图还是一个树，则称这个生成子图为生成树， 在图11-12中，(c)就是(a)的生成树。 最小生成树问题就是指在一个赋权的连通的无向图G中找出一个生成 树，并使得这个生成树的所有边的权数之和为最小。
个网络能联通7个学院办公室，并使总的线路长度为最短。
v2 3 1 4 v7 3 v6 5 2 8 v5 v3
7
v4
图11-14
v1 10
3
4
解：此问题实际上是求图11-14的最小生成树，这在例4中已经求得， 也即按照图11-13的(f)设计，可使此网络的总的线路长度为最短，为19 百米。 “管理运筹学软件”有专门的子程序可以解决最小生成树问题。
§3 最小生成树问题
例4 用破圈算法求图（a）中的一个最小生成树
v2 3 3 1 v3 v2 3 3 v6 v2 v4 v1 3 3 v6 v2 1 v3 v4
v1
10
7 3 4 v7 2 4 5 v5 v3 8
v4
v1
7 3 4 v7 2
4 5 v5 v3 7 8
v6
v2 v1 3 3 v6 v2 v1 3 3 v6