《数学实验》习题及答案 习题13

习题131请用Kruskal算法和Prim算法构造图13-15和图13-16的最小生成树．图13-15赋权无向图图13-16赋权无向图解（1）图13-15的Kruskal算法：a(1,2)=14;a(1,3)=18;a(1,4)=24;a(2,5)=28;a(2,6)=16;a(3,4)=22;a(3,6)=12;a(4,7)=25;a(5,7)=10;a=[a;zeros(2,7)];A=a+a';G=graph(A)p=plot(G,'EdgeLabel',G.Edges.Weight);T=minspantree(G,'method','sparse')%使用Kruskal的算法来计算最小生成树highlight(p,T)T.EdgesS=sum(T.Edges.Weight)运行结果为：G=graph-属性:Edges:[9×2table]Nodes:[7×0table]T=graph-属性:Edges:[6×2table]Nodes:[7×0table]ans=6×2tableEndNodesWeight______________121426163422361247255710S=99得到的最小生成树为如下图，边为v1v2，v2v6，v3v4，v3v6，v4v7，v5v7，权为99.图13-15的Prim算法如下：a(1,2)=14;a(1,3)=18;a(1,4)=24;a(2,5)=28;a(2,6)=16;a(3,4)=22;a(3,6)=12;a(4,7)=25;a(5,7)=10;a=[a;zeros(2,7)];A=a+a';G=graph(A)p=plot(G,'EdgeLabel',G.Edges.Weight);T=minspantree(G)%默认的算法是‘prim’算法highlight(p,T)T.EdgesS=sum(T.Edges.Weight)运行结果为：G=graph-属性:Edges:[9×2table]Nodes:[7×0table]T=graph-属性:Edges:[6×2table]Nodes:[7×0table]ans=6×2tableEndNodesWeight______________121426163422361247255710S=99得到的最小生成树如下图，边为v1v2，v2v6，v3v4，v3v6，v4v7，v5v7，最小生成树的权为99.（2）将图13-16的赋权图矩阵输入上述算法中，即可得到最小生成树.2假设要在某地建造5个工厂，拟修筑道路连接这5处．经勘探，其道路可按图13-17所示的无向边铺设．现在每条边的长度已经测出并标记在图的对应边上，如果要求铺设的道路总长度最短，这样既能节省费用，又能缩短工期，如何铺设？图13-17赋权无向图解赋权邻接矩阵．利用MATLAB求最小生成树：A=[01204;10530;25042;03405;40250]；G=graph(A)p=plot(G,'EdgeLabel',G.Edges.Weight);T=minspantree(G)highlight(p,T)T.EdgesS=sum(T.Edges.Weight)运行结果：G=graph-属性:Edges:[8×2table]Nodes:[5×0table]T=graph-属性:Edges:[4×2table]Nodes:[5×0table]ans=4×2tableEndNodesWeight______________1211