CalcGospel 國際數學圖譜
返回

IAL 2025 June D1 Q2

A Level / Edexcel / D1

IAL 2025 June Paper · Question 2

题目

Problem

The table shows the least distances, in metres, between seven signposts, P, Q, R, S, T, U and V.

PQRSTUV
P–1059019527095155
Q105–195295370190255
R90195–110185180245
S195295110–75115170
T27037018575–180245
U95190180115180–65
V15525524517024565–

Aisha must visit each signpost to check that it has not been damaged. She needs to find a route which minimises the distance travelled, starting and finishing at P.

(a) Use Prim’s algorithm, starting at P, to obtain a minimum spanning tree for the network. You must clearly show the order in which you select arcs.

(2)

(b) Use the answer to part (a) to obtain an initial upper bound for the length of Aisha’s route.

(2)

(c) Use the nearest neighbour algorithm, starting at P, to find a second upper bound for the length of Aisha’s route. You should state both the route and its length.

(3)

(d) By deleting T and all of its arcs, and using the answer to part (a), obtain a lower bound for the length of Aisha’s route.

(2)
题目中文翻译

下表显示了七个路标 P、Q、R、S、T、U 和 V 之间的最短距离（单位：米）。

PQRSTUV
P–1059019527095155
Q105–195295370190255
R90195–110185180245
S195295110–75115170
T27037018575–180245
U95190180115180–65
V15525524517024565–

Aisha 必须访问每个路标以检查其是否损坏。她需要找到一条从 P 出发并回到 P 的路线，使行驶距离最小化。

(a) 使用 Prim 算法，从 P 出发，求网络的最小生成树。必须清楚显示选择弧的顺序。

(b) 利用 (a) 的答案，求 Aisha 路线长度的初始上界。

(c) 使用最近邻算法，从 P 出发，求 Aisha 路线长度的第二个上界。应说明路线及其长度。

(d) 通过删除 T 及其所有弧，并利用 (a) 的答案，求 Aisha 路线长度的下界。

解答

(a)

解法一

思路

展开

从 P 开始使用 Prim 算法。每一步只比较已进入生成树的顶点与未进入顶点之间的弧，并选取其中权值最小的一条；同时记录弧而不只记录顶点，才能清楚呈现选择顺序。

答题过程

展开

Starting at P, Prim’s algorithm selects the arcs in the following order:

StepSelected arcWeight
1PR90
2PU95
3UV65
4PQ105
5RS110
6ST75

Hence the minimum spanning tree consists of

PR, PU, UV, PQ, RS, ST.\boxed{PR,\ PU,\ UV,\ PQ,\ RS,\ ST}.

(b)

解法一

思路

展开

先把最小生成树的六条弧权相加，再将总权乘以 2。沿生成树的每条弧往返一次会形成一条覆盖所有顶点并回到 P 的闭合巡回，因此其长度给出初始上界。

答题过程

展开

The weight of the minimum spanning tree is

90+95+65+105+110+75=540.90+95+65+105+110+75=540.

Doubling the minimum spanning tree gives the initial upper bound

2(540)=1080 metres.2(540)=\boxed{1080\text{ metres}}.

(c)

解法一

思路

展开

从 P 出发，每次前往尚未访问且距离当前路标最近的路标。所有路标访问完毕后回到 P，并把沿途七段距离相加，得到第二个上界。

答题过程

展开

The nearest neighbour choices are

P→R→S→T→U→V→Q→P.P\to R\to S\to T\to U\to V\to Q\to P.

The length of this route is

90+110+75+180+65+255+105= 880.\begin{align*} 90+110+75+180+65+255+105=&\,880. \end{align*}

Therefore, the second upper bound is

880 metres,\boxed{880\text{ metres}},

using the route P−R−S−T−U−V−Q−P\boxed{P-R-S-T-U-V-Q-P}.

(d)

解法一

思路

展开

删除 T 后，(a) 中最小生成树只有弧 ST 被移除，所以余下生成树的权为 540−75540-75。任何经过 T 的完整巡回都必须使用两条与 T 相连的弧，因此再加上从 T 出发的两条最短弧 TS 与 TU，便得到下界。

答题过程

展开

Deleting T removes the arc ST, of weight 75, from the minimum spanning tree. The two shortest arcs incident to T are ST and TU, with weights 75 and 180.

Hence the lower bound is

540−75+(75+180)= 720.\begin{align*} 540-75+(75+180)=&\,720. \end{align*}

Therefore, a lower bound for the route length is

720 metres.\boxed{720\text{ metres}}.