当前位置:首页 >> 数学 >>

数学建模案例分析-- 图与网络方法建模4通讯网络的最小生成树


§4

通讯网络的最小生成树

连通的无圈图称为树。树是最简单但又是十分重要的一类图,它在许多学科领域中有广泛的 应用,例如分子结构,电网络分析等。最短连接问题与树有关,学科分类和一些决策过程也往往 可以用树的形式表示。 图 T (V , E ), V ? n , E ? m ,则下面关于树的命题是等价的。 (1) T 是一个树。 (2) T 无圈,且 m ? n ? 1 。 (3) T 连通,且 m ? n ? 1 。 (4) T 无圈,但加一新边即得唯一一个圈。 (5) T 连通,但舍去一边就不连通。 (6) T 中任意两点,有唯一链相连。 上述性质中每一个命题均可作为树的定义,它们对判断和构造树将极为方便。 若 G 1 是连通图 G 2 的生成子图,且 G 1 本身是树,则称 G 1 为 G 2 的生成树。 对 图 G ? (V , E ) 的 每 一 条 边 e ? E 赋 以 相 应 的 实 数 权 w ( e ) , 得 到 一 个 网 络 , 记 为
N ? (V , E , W ) 。设 T ? (V , E ? ) 是 N 的一个生成树,令 W ( T ) ?
N 中权最小的生成树称为 N 的最小生成树。

?
e? E
'

w ( e ) ,则 W (T ) 称为 T 的权,

许多实际问题,如在若干个城市之间建造铁路网、输电网或通信网等,都可归纳为寻求连通 赋权图(网络)的最小生成树问题。例如已知城市 v i 和 v j 间的直通线路的造价为
w ij ? w ( e ij ) ( e ij ? ( v i , v j ))

要求一个总造价为最小的设计方案。又如一个城市中,对若干新建居民点供应自来水和煤气,已 测知连接各点间的直通管道的造价,要求给出一个总造价最小的铺设方案等等。下面介绍在给定 网络 N ? (V , E , W ) 内求最小生成树的两种算法。设网络点数为 n ,此时最小生成树的边数为
n ?1。

算法1

(克鲁斯凯尔,Kruskal)

算法I的中心思想是每次添加权尽可能小的边,使新的图无圈,直到生成最小生成树为止。也 形象地简称“最小边的加入法”。其步骤如下: (1)把 N 内的所有边按照权的非减次序排列。 (2)按(1)排列的次序检查 N 中的每一条边,如果这条边与已得到的边不产生圈,则取这一条 边为解的一部分。 (3)若已取到 n ? 1 条边,算法终止。此时以 V 为顶点集,以取到的 n ? 1 条边为边集的图即为最

小生成树。 例1 求图1所示网络的最小生成树。 解 按各边的权的非减次序将网络中的8条边排列为
e1 ? e 2 ? ? ? e 8

首先取 e 1 和 e 2 为所求最小生成树 T 的两条边,然后检查边 e 3 。由于边 e 1 、 e 2 和 e 3 构成圈,故不 取边 e 3 ,考虑 e 4 。由于 e 1 、 e 2 和 e 4 不构成圈,故可取 e 4 。然后检查 e 5 。由于 e 1 、 e 2 、 e 4 和 e 5 不构成圈,故可取 e 5 。此时由 e 1 、 e 2 、 e 4 和 e 5 构成的生成树 T 即为网络 N 的最小生成树(如图 2) 。

e1
1 2

v2

3 4
e6 e7 e5

e1
1 2
e4

3
v2

e5

2

v1
2
e2

e3

v4

v5
e8

v1
2
e2

v4

e4

v5

4

4 图1

v3

图2

v3

算法II (普赖姆,Prim) 这是一种迭代算法,每进行一次迭代将产生组成网络 N 最小生成树 T 的一条边。其作法基于 下面的事实:如果我们已经知道 T 中的一些边,它们的端点集为 S ,则 S 是 N 的顶点 V 的一个 子集。以 ? ( S ) 记一个端点在 S 中、另一端点在 V \ S 中的所有边组成的集合,由于最小生成树 T 是 N 的连通生成子图,? ( S ) 中权最小的一条边,应该也是 N 的最小生成树 T 中的一条边。下面 通过对图1所示的网络 N 求最优树 T 的过程介绍这一算法。 算法开始时,S ? ( v 1 ) ,? ( S ) ? ( e 1 , e 2 ) 。 由于 w ( e 1 ) ? 1 ? w ( e 2 ) ? 2 , T ? ( e 1 ) , 取 并把 e 1 不在 S 中的一个端点 v 2 加入 S 中。于是 S ? ( v 1 , v 2 ) , ? ( S ) ? ( e 2 , e 3 , e 5 , e 6 ) , ? ( S ) 中权最小的 边为 e 2 和 e 3 。任取一条边,例如 e 3 加入 T 中,把 e 3 不在 S 中的另一端点 v 3 加进 S 中。此时
T ? ( e 1 , e 3 ) , S ? ( v 1 , v 2 , v 3 ) ,从而 ? ( S ) ? ( e 1 , e 6 , e 7 , e 8 ) ,其中权最小的边为 e 5 。 e 5 不在 S 中

的一个端点为 v 5 ,取新的 T ? ( e 1 , e 3 , e 5 ) , S ? ( v 1 , v 2 , v 3 , v 5 ) ,从而 ? ( S ) ? ( e 1 , e 6 , e 7 ) ,其中权 最小的边为 e 4 。e 4 不在 S 中的一个端点为 v 4 ,从而取 T ? ( e 1 , e 3 , e 5 , e 4 ) , S ? ( v 1 , v 2 , v 3 , v 5 , v 4 )

? V 。此时以 V 为顶点集, T ? ( e 1 , e 3 , e 5 , e 4 ) 为边集的树 T 即为 N 的最小生成树。

我们将上述过程一般化。设 V ( G ) ? ( v 1 , v 2 , ? , v n ) , e ij ? ( v i , v j ) ? E ( G ) , w ij ? w ( e ij ) 为 边 e ij 的权。如果 v i 和 v j 之间无边相连,则取 w ij ? ? 。为叙述方便,我们以顶点的下标来表示 S 中的顶点。普赖姆迭代过程如下: (1) T ? ? , S ? {1}, R ? { 2 , 3 , ? , n }, U (2)设 Min U
j? R j
j

? w ij ,此处 i ? 1 ? S , j ? R



? w ik

,记 U k

? w ik

。以 S

? {k } 代替 S , R \ { k } 代替 R , T ? { e ik } 代替 T 。

(3)若 R ? ? ,算法终止,此时 T 即为所求;否则,对每个 j ? R ,以 Min {U j , w ik k ? S } 代替
U
j

,返回上一步骤(2) 。 应用该算法求得例1(图1)中的网络 N 的最优树 T ? ( e 1 , e 2 , e 4 , e 5 ) (如图2) 。 克鲁斯凯尔用于手工计算小型网络的最小生成树是比较好,而且直观易懂,但应用较大型网

络时效率不高,基于这种算法的计算机软件也较难实现。普赖姆方法克服了这些缺点,但遗憾的 是普赖姆方法应用于小型问题时却过分的繁复。


相关文章:
数学建模案例分析
理论和方法的理解, 培养数学建模的意识, 那么我们初步...案例一. 交通网络流量分析问题城市道路网中每条道路...图 4 某城市单行线车流量 (1)建立确定每条道路...
数学建模实验四
数学建模实验四_数学_自然科学_专业资料。数学实验与数学建模实验报告信息学院 通信...最小生成树问题 试用 Prim 算法 Kruskal 算法求下图所示网络的最优树 1 ...
数学建模-最小生成树-kruskal算法及各种代码
数学建模-最小生成树-kruskal算法及各种代码_数学_自然科学_专业资料。数学建模-...4 6 100 100 1 100 4 0 5 100 6 100 6 100 5 0]; Kruskal(a,100)...
数学建模课程大纲
(4)韩中庚 编著 数学建模方法及其应用 北京 高等...图与网络模型 数值分析模型 6 6 6 6 36 3 3 ...图的生成树 三、最小生成树问题 1.掌握插值法的...
数学建模案例分析--线性代数建模案例(20例)
理论和方法的理解, 培养数学建模的意识, 那么我们初步...案例一. 交通网络流量分析问题城市道路网中每条道路...图 4 某城市单行线车流量 (1)建立确定每条道路...
深圳大学 数学建模引论课程教学大纲
4 月修订 一、课程设计的指导思想(一)课程性质 1...学生数学建模基本能力和善于用数学思想与方法分析与...的概念和最小生成树 最短路 网络的最大流 二分...
数学建模 四大模型总结
数学建模数学模型总结 吴翔 四类基本模型 1 ...最小生成树问题 (MST)、旅行商问题(TSP)、图的...与遗传算法、神经网络或灰色理论联合的聚类方法 2.3...
数学建模 遥测遥感网2
y=58,74,12,68,67,4,75,52,30,28,63,61,...(1)对于 B1 中的数据,我们首先根据最小生成树图(...[2] 吴建国等,数学建模案例精编,北京:中国水利水电...
数学建模方法归类(很全很有用)
数学建模方法归类(很全很有用)_理学_高等教育_教育...合并距离最近的两类为一个新类 4. 计算新类与...最小生成树问题:连线问题—欲修筑连接多个城市的...
数学建模案例分析4足球门的危险区域--概率统计方法建模
数学建模案例分析4足球门的危险区域--概率统计方法建模_数学_自然科学_专业资料。数学建模案例分析--概率统计方法建模§4 足球门的危险区域 一、问题提出 在足球比赛...
更多相关标签: