题目

Problem

The network in Figure 2 shows the distances, in miles, between ten towns, A, B, C, H, L, M, P, S, W and Y.

(a) Use Kruskal’s algorithm to find a minimum spanning tree for the network. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.

(3)

	A	B	C	H	L	M	P	S	W	Y
A	-	6	18	15	54	29	16	26	29	74
B	6	-	22	21	60	35	10	32	33	80
C	18	22	-	17	59	31	12	44	11	80
H	15	21	17	-	42	14	29	41	28	63
L	54	60	59	42	-	40	70	28	61	21
M	29	35	31	14	40	-	43	55	21	61
P	16	10	12	29	70	43	-	42	23	90
S	26	32	44	41	28	55	42	-	55	48
W	29	33	11	28	61	21	23	55	-	82
Y	74	80	80	63	21	61	90	48	82	-

The table shows the shortest distances, in miles, between the ten towns.

(b) Use Prim’s algorithm on the table, starting at A, to find the minimum spanning tree for this network. You must clearly state the order in which you select the arcs of your tree.

(3)

(1)

Sharon needs to visit all of the towns, starting and finishing in the same town, and wishes to minimise the total distance she travels.

(d) Use your answer to (c) to calculate an initial upper bound for the length of Sharon’s route.

(1)

(e) Use the nearest neighbour algorithm on the table, starting at W, to find an upper bound for the length of Sharon’s route. Write down the route which gives this upper bound.

(2)

Using the nearest neighbour algorithm, starting at Y, an upper bound of length 212 miles was found.

(f) State the best upper bound that can be obtained by using this information and your answers from (d) and (e). Give the reason for your answer.

(1)

(g) By deleting W and all of its arcs, find a lower bound for the length of Sharon’s route.

(2)

Sharon decides to take the route found in (e).

(h) Interpret this route in terms of the actual towns visited.

(1)

题目中文翻译

图 2 中的网络显示了十个城镇 A、B、C、H、L、M、P、S、W 和 Y 之间的距离（单位：英里）。

(a) 使用 Kruskal 算法找到网络的最小生成树。应按考虑顺序列出弧。在每种情况下，说明是否将弧添加到最小生成树中。

表格显示了十个城镇之间的最短距离（单位：英里）。

(b) 在表格上使用 Prim 算法，从 A 开始，找到此网络的最小生成树。必须清楚说明选择树弧的顺序。

Sharon 需要访问所有城镇，从同一城镇出发并回到同一城镇，并希望最小化旅行总距离。

(d) 使用 (c) 的答案计算 Sharon 路线长度的初始上界。

(e) 在表格上使用最近邻算法，从 W 开始，找到 Sharon 路线长度的上界。写出给出此上界的路线。

使用最近邻算法，从 Y 开始，找到长度为 212 英里的上界。

(f) 说明使用此信息和 (d) 和 (e) 的答案可以获得的最佳上界。给出理由。

(g) 通过删除 W 及其所有弧，找到 Sharon 路线长度的下界。

Sharon 决定采用 (e) 中找到的路线。

(h) 根据实际访问的城镇解释此路线。

解答

(a)

解法一

思路

展开

Kruskal 算法按边权从小到大考虑原网络中的边。若加入一条边不会形成回路就接受，否则拒绝；相同权重的边可按任一一致顺序处理。达到连接 10 个顶点所需的 9 条边后停止。

答题过程

展开

Applying Kruskal’s algorithm:

Arc	Weight	Decision
AB	6	Add
BP	10	Add
CW	11	Add
CP	12	Add
HM	14	Add
AH	15	Add
CH	17	Reject - forms a cycle
AC	18	Reject - forms a cycle
AP	20	Reject - forms a cycle
MW	21	Reject - forms a cycle
LY	21	Add
AS	26	Add
LS	28	Add

Therefore the minimum spanning tree consists of

\boxed{AB,\ BP,\ CW,\ CP,\ HM,\ AH,\ LY,\ AS,\ LS}.

(b)

解法一

思路

展开

Prim 算法从 A 开始，每次从“已在树中的顶点”到“尚未在树中的顶点”的所有可用边中选择最短者。这里使用最短距离表，因此选边权重不一定整体递增，例如加入 C 后才出现较短的 CW。

答题过程

展开

Starting at $A$ , Prim’s algorithm selects the arcs in the order

\boxed{AB,\ BP,\ CP,\ CW,\ AH,\ HM,\ AS,\ LS,\ LY}.

The corresponding order in which vertices enter the tree is

A,\ B,\ P,\ C,\ W,\ H,\ M,\ S,\ L,\ Y.

(c)

解法一

思路

展开

把 (b) 所选九条边的权重相加即可得到最小生成树总权重。

答题过程

展开

The weight of the minimum spanning tree is

\begin{align*} &\,6+10+12+11+15\\ +&\,14+26+28+21\\ =&\,\boxed{143\text{ miles}}. \end{align*}

(d)

解法一

思路

展开

把最小生成树的每条边走两次，会得到一条从某城镇出发、遍历整棵树后回到起点的闭合路线。因此“最小生成树权重的两倍”是一个保证可行的初始上界。

答题过程

展开

Doubling the minimum spanning tree gives the initial upper bound

2(143)=\boxed{286\text{ miles}}.

(e)

解法一

思路

展开

从 W 开始，每一步利用最短距离表前往尚未访问的最近城镇；所有城镇访问完后，再回到 W。逐步选择得到 W、C、P、B、A、H、M、L、Y、S，最后返回 W。

答题过程

展开

The nearest-neighbour route starting at $W$ is

\boxed{W-C-P-B-A-H-M-L-Y-S-W}.

Its length is

\begin{align*} &\,11+12+10+6+15\\ +&\,14+40+21+48+55\\ =&\,\boxed{232\text{ miles}}. \end{align*}

(f)

解法一

思路

展开

可用的三个上界分别是 (d) 的 286、(e) 的 232，以及题目给出的从 Y 开始所得 212。上界越小越好，因此取三者中的最小值。

答题过程

展开

Since

212<232<286,

the best available upper bound is the one obtained by starting at $Y$ :

\boxed{212\text{ miles}}.

(g)

解法一

思路

展开

删除 W 后，(b) 的最小生成树只需删去与 W 相连的 CW，剩余边仍连接其余九个城镇，权重为 $143-11=132$ 。任何包含 W 的巡回必须用两条边连接 W；从最短距离表取与 W 相连的两条最短边 WC 和 WM，再加到剩余生成树上即可得到下界。

答题过程

展开

After deleting $W$ , the residual spanning tree has weight

143-11=132.

The two least distances incident to $W$ are

WC=11,\qquad WM=21.

Therefore a lower bound is

132+11+21=\boxed{164\text{ miles}}.

(h)

解法一

思路

展开

(e) 使用的是最短距离表，其中表内的一步不一定对应原网络的一条直接边。路线最后的表内路段 S—W 长 55；回到原网络后，这条最短路实际是 S—A—C—W，所以必须把中途经过的 A、C 也写出。

答题过程

展开

The table entry from $S$ to $W$ corresponds in the original network to

S-A-C-W,

because

SA+AC+CW=26+18+11=55.

Hence the actual towns visited, in order, are

\boxed{W-C-P-B-A-H-M-L-Y-S-A-C-W}.

	A	B	C	H	L	M	P	S	W	Y
A	-	6	18	15	54	29	16	26	29	74
B	6	-	22	21	60	35	10	32	33	80
C	18	22	-	17	59	31	12	44	11	80
H	15	21	17	-	42	14	29	41	28	63
L	54	60	59	42	-	40	70	28	61	21
M	29	35	31	14	40	-	43	55	21	61
P	16	10	12	29	70	43	-	42	23	90
S	26	32	44	41	28	55	42	-	55	48
W	29	33	11	28	61	21	23	55	-	82
Y	74	80	80	63	21	61	90	48	82	-

	A	B	C	H	L	M	P	S	W	Y
A	-	6	18	15	54	29	16	26	29	74
B	6	-	22	21	60	35	10	32	33	80
C	18	22	-	17	59	31	12	44	11	80
H	15	21	17	-	42	14	29	41	28	63
L	54	60	59	42	-	40	70	28	61	21
M	29	35	31	14	40	-	43	55	21	61
P	16	10	12	29	70	43	-	42	23	90
S	26	32	44	41	28	55	42	-	55	48
W	29	33	11	28	61	21	23	55	-	82
Y	74	80	80	63	21	61	90	48	82	-

IAL 2022 June D1 Q3

题目

解答

(a)

解法一

思路

答题过程

(b)

解法一

思路

答题过程

(c)

解法一

思路

答题过程

(d)

解法一

思路

答题过程

(e)

解法一

思路

答题过程

(f)

解法一

思路

答题过程

(g)

解法一

思路

答题过程

(h)

解法一

思路

答题过程

	A	B	C	H	L	M	P	S	W	Y
A	-	6	18	15	54	29	16	26	29	74
B	6	-	22	21	60	35	10	32	33	80
C	18	22	-	17	59	31	12	44	11	80
H	15	21	17	-	42	14	29	41	28	63
L	54	60	59	42	-	40	70	28	61	21
M	29	35	31	14	40	-	43	55	21	61
P	16	10	12	29	70	43	-	42	23	90
S	26	32	44	41	28	55	42	-	55	48
W	29	33	11	28	61	21	23	55	-	82
Y	74	80	80	63	21	61	90	48	82	-