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

Mathematicamodel;Prim算法;赵根;树：没有圈的连通图

?树中任意两點间有唯壹途径。

?树的边数恰好為顶點数減1。

;都市電信局有許多业务如收费，营业，112，114等，但愿在全市范围实現计算机联网服务，共享多种资源。壹种重要关怀的問題是：用数据通讯线把壹组站點联結起来，而不容許通讯线在非站點处相交，怎样连接可使通讯线的花费最小？;1;引例：计算机网络的线路设计;确定应在哪些站點之间铺设通讯线路，与否可看作是在對应的加权图中构造最小费用的生成树的問題？;最小生成树

最大生成树;10個顶點的完全图，其不壹样的生成树就有壹亿棵。

壹般地，n個顶點的完全图，其不壹样的生成树個数為nn-2。

30個顶點的完全图就有3028個生成树，求最小生成树時用穷举法是無效的。;返回;Prim算法;基本思想:

最初把图的n個顶點看作n個分离的部分树，每個树具有壹种顶點，算法的每壹步选择可连接两分离树的边中权最小的边连接两個部分树，合二為壹,部分树逐渐減少，直到只有壹种部分树（n-1步之後）便得到最小生成树。;Kruskal算法;Kruskal算法;初始化：j?0,T??,c?0,k?0；

对所有顶点i,t(i)?i.

;Kruskal算法;b=[11122334;24535455;815679103];

[B,i]=sortrows(b,3);B=B’;m=size(b,2);n=5;

t=1:n;k=0;T=[];c=0;

fori=1:m

ift(B(1,i))~=t(B(2,i))

k=k+1;T(k,1:2)=B(1:2,i),c=c+B(3,i)

tmin=min(t(B(1,i)),t(B(2,i)));

tmax=max(t(B(1,i)),t(B(2,i)));

forj=1:n

ift(j)==tmax

t(j)=tmin;

end

end

end ;程序运行成果：

T=

14

45

23

25

c=

17;Prim算法;?;贪婪法可被用于多种各样問題的处理。该法只是壹种试探法，计算上简便有效，可提供對的解的壹种近似。但壹般状况下，不能保证输出的解是對的的。其對的性需要证明，這往往比较困难。

已证明,求最小生成树的Kruskal算法和Prim算法都是對的的;分组技术是设计制造系统的壹种措施，它把生产零件的机器分组，對应地把需生产的零件分类，使零件跨组加工的情形尽量少，最理想的状况是使每個零件的加工，都在组内完毕。

假设有13种零件，需??9台机器上加工。在各台机器上加工的零件号在下表中給出。;范例：制造系统的分组技术;设用Mi表达需由机器i加工的零件集，對任意两台机器i,j,定义相异度：;“?”：對称差，

分子：在机器i但不在机器j上加工，或在机

器j但不在机器i上加工的零件数。

分母：或在机器i，或在机器j上加工的零件数。

显然0???1;构造加权图

以机器為顶點，作壹种完全图，每条边(i,j)被赋予权?(i,j)。

原問題的转化

加权图的最小生成树是由那些相异度最小的边构成的连通图，假如但愿把机器提成k個组，就继续删去最小生成树上权最大的k-1条边。于是得到k個分离的子树，每棵树的顶點集就构成各机器组。;對表1給出的数据，加权图的边权矩阵如下：

[111111112222222333333444445555666778;

234567893456789456789567896789789899;

0.510.890.141111110.621111111110.50.870.670.750.7511111111011]

用Kruskal算法可求出最小生成树，在前面給出的Kruskal算法的MATLAB程序中，边权矩阵b的值改為此处的边权矩阵，顶點数n改為9即可。;T=78

15

12

39

46

4