数学建模社区-数学中国

标题: 最小生成树问题 [打印本页]

作者: 森之张卫东 时间: 2015-7-14 14:28
标题: 最小生成树问题
在一给定的无向图 G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即 (u, v)\in E），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集（即 T\subseteq E）且为无循环图，使得

w(T) = \sum_{(u,v)\in T} w(u,v)

的 w(T) 最小，则此 T 为 G 的最小生成树。

最小生成树其实是最小权重生成树的简称。以有线电视电缆的架设为例，若只能沿着街道布线，则以街道为边，而路口为顶点，其

中必然有一最小生成树能使布线成本最低。

下面附上最小生成树算法程序：

ex4_5.m

401 Bytes, 下载次数: 1, 下载积分: 体力 -2 点

ex4_6.m

497 Bytes, 下载次数: 0, 下载积分: 体力 -2 点

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)