题目
Figure 1 shows a weighted network.
(a) Define the terms
(i) tree,
(ii) minimum spanning tree.
(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.
(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.
(Total 8 marks)
题目中文翻译
图 1 显示了一个加权网络。
(a) 定义以下术语
(i) 树，
(ii) 最小生成树。
(b) 使用 Kruskal 算法求图 1 所示网络的最小生成树。你必须清楚地显示你考虑边的顺序。对于每条边，说明你是否将其包含在最小生成树中。
(c) 使用答案册中 Diagram 1 给出的顶点画出最小生成树，并说明最小生成树的权重。
解答
(a)(i)
解法一
思路
展开
树的定义必须同时包含两个条件：图是连通的，并且不含回路。只写其中一个条件并不足以确定一棵树。
答题过程
展开
A tree is a connected graph containing no cycles.
(a)(ii)
解法一
思路
展开
最小生成树首先必须是覆盖原图所有顶点的树；在所有这样的树中，它的边权总和最小。
答题过程
展开
A minimum spanning tree is a tree that contains every vertex of the original graph and has the smallest possible total edge weight.
(b)
解法一
思路
展开
按权值从小到大考虑各边。若加入一条边不会形成回路便保留，否则拒绝；当九个顶点已由八条边连成一棵树时停止。
答题过程
展开
Applying Kruskal’s algorithm:
| Order | Edge | Weight | Decision |
|---|---|---|---|
| 1 | FJ | 11 | Include |
| 2 | EG | 13 | Include |
| 3 | EF | 15 | Include |
| 4 | EH | 17 | Include |
| 5 | GH | 18 | Reject: forms a cycle |
| 6 | BC | 19 | Include |
| 7 | HJ | 20 | Reject: forms a cycle |
| 8 | BD | 22 | Include |
| 9 | FH | 23 | Reject: forms a cycle |
| 10 | AE | 25 | Include |
| 11 | BE | 29 | Include |
The selected edges, in order, are therefore
(c)
解法一
思路
展开
把 (b) 中保留的八条边画到答案册给定顶点上。这些边连接全部九个顶点且无回路；将其权值相加即可得到最小生成树的总权。
答题过程
展开
The minimum spanning tree contains the edges
Its weight is