题目
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) 写出最小生成树的权重。