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

习题13

1请用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.Edges

S=sum(T.Edges.Weight)

运行结果为：

G=

graph-属性:

Edges:[9×2table]

Nodes:[7×0table]

T=

graph-属性:

Edges:[6×2table]

Nodes:[7×0table]

ans=

6×2table

EndNodesWeight

______________

1214

2616

3422

3612

4725

5710

S=

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.Edges

S=sum(T.Edges.Weight)

运行结果为：

G=

graph-属性:

Edges:[9×2table]

Nodes:[7×0table]

T=

graph-属性:

Edges:[6×2table]

Nodes:[7×0table]

ans=

6×2table

EndNodesWeight

______________

1214

2616

3422

3612

4725

5710

S=

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.Edges

S=sum(T.Edges.Weight)

运行结果：

G=

graph-属性:

Edges:[8×2table]

Nodes:[5×0table]

T=

graph-属性:

Edges:[4×2table]

Nodes:[5×0table]

ans=

4×2table

E