题目

Problem

The table below shows the distances, in metres, between six vertices, A, B, C, D, E and F, in a network.

(a) Draw the weighted network using the vertices given in Diagram 1 in the answer book.

(2)

(b) Use Kruskal’s algorithm to find a minimum spanning tree for the network. You should list the edges in the order that you consider them and state whether you are adding them to your minimum spanning tree.

(3)

(2)

题目中文翻译

下表显示了网络中六个顶点 A、B、C、D、E 和 F 之间的距离（单位：米）。

(a) 使用答案本中图 1 给出的顶点画出加权网络。

(b) 使用 Kruskal 算法找到网络的最小生成树。应按考虑顺序列出边，并说明是否将它们添加到最小生成树中。

解答

(a)

解法一

思路

展开

距离表中每个非空的非对角条目代表一条无向边。由于表格关于主对角线对称，每条边只画一次，并在边旁标上对应权重；空白位置表示两顶点之间没有直接边。

答题过程

展开

The weighted network contains the following eleven edges:

Edge	Weight	Edge	Weight
$AB$	$18$	$AC$	$23$
$AD$	$17$	$AE$	$28$
$AF$	$19$	$BC$	$20$
$BD$	$11$	$BF$	$24$
$CE$	$25$	$CF$	$13$
$DF$	$22$

Drawing each of these edges between the given vertices gives:

(b)

解法一

思路

展开

按权重从小到大考虑各边。只要加入一条边不会形成回路，就把它加入最小生成树；否则明确记为拒绝。加入第五条边 $CE$ 后，六个顶点已经全部连通，算法结束。

答题过程

展开

Using Kruskal’s algorithm, consider the edges in increasing order of weight:

Edge	Weight	Decision
$BD$	$11$	Add
$CF$	$13$	Add
$AD$	$17$	Add
$AB$	$18$	Reject: it forms a cycle
$AF$	$19$	Add
$BC$	$20$	Reject: it forms a cycle
$DF$	$22$	Reject: it forms a cycle
$AC$	$23$	Reject: it forms a cycle
$BF$	$24$	Reject: it forms a cycle
$CE$	$25$	Add

The five selected edges are therefore

\boxed{BD,\ CF,\ AD,\ AF,\ CE}.

(c)

解法一

思路

展开

把 (b) 选出的五条边画在给定顶点上。六个顶点全部连通且没有回路，因此所得图确为生成树；总权重是五条边权之和。

答题过程

展开

The minimum spanning tree consists of $BD$ , $CF$ , $AD$ , $AF$ and $CE$ :

Its total weight is

\begin{aligned} 11+13+17+19+25=&\,85\text{ metres}. \end{aligned}

Hence the weight of the minimum spanning tree is

\boxed{85\text{ metres}}.

IAL 2020 Oct D1 Q1

题目

解答

(a)

解法一

思路

答题过程

(b)

解法一

思路

答题过程

(c)

解法一

思路

答题过程