题目
Problem
Figure 1 shows a weighted network.
(a) Define the terms
(i) tree,
(ii) minimum spanning tree.
(3)
(b) Use Kruskal’s algorithm to find the minimum spanning tree for the network shown in Figure 1. You must clearly show the order in which you consider the edges. For each edge, state whether or not you are including it in the minimum spanning tree.
(3)
(c) Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book and state the weight of the minimum spanning tree.
(2)
(Total 8 marks)
题目中文翻译
图 1 显示了一个加权网络。
(a) 定义以下术语
(i) 树，
(ii) 最小生成树。
(b) 使用 Kruskal 算法求图 1 所示网络的最小生成树。你必须清楚地显示你考虑边的顺序。对于每条边，说明你是否将其包含在最小生成树中。
(c) 使用答案册中 Diagram 1 给出的顶点画出最小生成树，并说明最小生成树的权重。