《數(shù)學(xué)實(shí)驗(yàn)》習(xí)題及答案 習(xí)題13

習(xí)題131請(qǐng)用Kruskal算法和Prim算法構(gòu)造圖13-15和圖13-16的最小生成樹．圖13-15賦權(quán)無(wú)向圖圖13-16賦權(quán)無(wú)向圖解（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的算法來(lái)計(jì)算最小生成樹highlight(p,T)T.EdgesS=sum(T.Edges.Weight)運(yùn)行結(jié)果為：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，權(quán)為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)%默認(rèn)的算法是‘prim’算法highlight(p,T)T.EdgesS=sum(T.Edges.Weight)運(yùn)行結(jié)果為：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，最小生成樹的權(quán)為99.（2）將圖13-16的賦權(quán)圖矩陣輸入上述算法中，即可得到最小生成樹.2假設(shè)要在某地建造5個(gè)工廠，擬修筑道路連接這5處．經(jīng)勘探，其道路可按圖13-17所示的無(wú)向邊鋪設(shè)．現(xiàn)在每條邊的長(zhǎng)度已經(jīng)測(cè)出并標(biāo)記在圖的對(duì)應(yīng)邊上，如果要求鋪設(shè)的道路總長(zhǎng)度最短，這樣既能節(jié)省費(fèi)用，又能縮短工期，如何鋪設(shè)？圖13-17賦權(quán)無(wú)向圖解賦權(quán)鄰接矩陣．利用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)運(yùn)行結(jié)果：G=graph-屬性:Edges:[8×2table]Nodes:[5×0table]T=graph-屬性:Edges:[4×2table]Nodes:[5×0table]ans=4×2tableEndNodesWeight______________1211