题目
Figure 1 shows a graph, .
(a) Write down an example of a path from A to J on .
(b) State, with a reason, whether A – B – C – D – E – G – F – H – J is an example of a tour on .
Figure 2 shows a network with 15 arcs between nine vertices, A, B, C, D, E, F, G, H and J. The numbers on the arcs represent the distances, in km.
(c) Use Kruskal’s algorithm to find the minimum spanning tree for the network. You should list the arcs in the order in which you consider them. In each case, state whether or not you are adding the arc to the minimum spanning tree.
(d) Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book.
(e) State the weight of the minimum spanning tree.
题目中文翻译
图 1 显示了一个图 。
(a) 写出 上从 A 到 J 的路径的一个例子。
(b) 说明 A – B – C – D – E – G – F – H – J 是否是 上回路的一个例子，并给出理由。
图 2 显示了一个网络，九个顶点 A、B、C、D、E、F、G、H 和 J 之间有 15 条弧。弧上的数字表示距离（单位：km）。
(c) 使用 Kruskal 算法找到网络的最小生成树。应按考虑顺序列出弧。在每种情况下，说明是否将弧添加到最小生成树中。
(d) 使用答案本中图 1 给出的顶点画出最小生成树。
(e) 写出最小生成树的权重。
解答
(a)
解法一
思路
展开
沿图中的相邻顶点从 A 走到 J，并确保没有顶点重复出现即可。例如依次经过 B、F、H。
答题过程
展开
One possible path is
(b)
解法一
思路
展开
虽然给出的路线经过了每个顶点，但 tour 必须回到出发顶点。该路线从 A 开始、在 J 结束，因此不是 tour。
答题过程
展开
No. Although the route contains every vertex, it starts at A and finishes at J. A tour must finish at its starting vertex.
(c)
解法一
思路
展开
按权重从小到大考察各条弧。若加入一条弧会形成回路，就拒绝该弧；否则加入。权重同为 21 的 HJ 与 BC 可按任一顺序考察，这里先考察 HJ。九个顶点的生成树需要八条弧，选满八条后停止。
答题过程
展开
Applying Kruskal’s algorithm gives:
| Arc | Weight | Decision |
|---|---|---|
| AC | 9 | add |
| BE | 11 | add |
| BF | 12 | add |
| EF | 14 | reject |
| FG | 15 | add |
| FH | 17 | add |
| EG | 18 | reject |
| EJ | 20 | add |
| HJ | 21 | reject |
| BC | 21 | add |
| CE | 23 | reject |
| AB | 24 | reject |
| CD | 25 | add |
The arcs in the minimum spanning tree are therefore
(d)
解法一
思路
展开
保留 (c) 中选入的八条弧 AC、BE、BF、FG、FH、EJ、BC、CD，删去其余所有弧，即得到最小生成树。
答题过程
展开
The minimum spanning tree is:
(e)
解法一
思路
展开
把最小生成树中八条弧的权重相加即可。
答题过程
展开
The weight of the minimum spanning tree is