会计学Prim算法树：没有圈的连通图树中任意两点间有唯一路径。树的边数恰好为顶点数减1。城市电信局有许多业务如收费，营业，112，114等，希望在全市范围实现计算机联网服务，共享各种资源。一个主要关心的问题是：用数据通讯线把一组站点联结起来，而不允许通讯线在非站点处相交，如何连接可使通讯线的花费最小？引例：计算机网络的线路设计确定应在哪些站点之间铺设通讯线路，是否可看作是在相应的加权图中构造最小费用的生成树的问题？最小生成树最大生成树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:mift(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:nift(j)==tmaxt(j)=tmin;endendend程序运行结果：T=14452325c=17Prim算法贪婪法可被用于各种各样问题的处理。该法只是一种试探法，计算上简便有效，可提供正确解的一个近似。但一般情况下，不能保证输出的解是正确的。其正确性需要证明，这往往比较困难。已证明,求最小生成树的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=7815123946474513c=4.4300你能给出对应于该机器分组的零件分类吗？设是两点i与j之间的距离，或1（1表示连接，0表示不连接），并假设顶点1是生成树的根.则最小生成树问题的0-1规划模型最小生成树问题的0-1规划模型最小生成树问题的0-1规划模型最小生成树问题的0-1规划模型最小生成树问题的0-1规划模型最小生成树问题的0-1规划模型最小生成树问题的0-1规划模型最小生成树问题的0-1规划模型