CalcGospel 國際數學圖譜
返回

IAL 2022 Jan D1 Q5

A Level / Edexcel / D1

IAL 2022 Jan Paper · Question 5

题目

Problem

Figure 4 represents a network of 16 roads in a city. The number on each arc represents the time taken, in minutes, to travel along the corresponding road.

[The total weight of the network is 82]

Chan needs to check that the roads are in good repair. He must travel along each road at least once. Chan will start and finish at his office at G and must minimise the total time taken for his inspection route.

For this inspection route,

(a) find the time taken and state a possible route. You must make your method and reasoning clear.

(3)

Chan wonders if he can reduce his travel time by starting from his home at B, travelling along each road at least once and finishing at his office at G.

(b) By considering the pairings of all relevant nodes, find any arcs that would need to be traversed twice in the minimum inspection route from B to G. You must make your method clear, showing your working.

(5)

(c) Determine which of the two routes ending at G is quicker, the one starting at G or the one starting at B. You must justify your answer.

(2)
题目中文翻译

图 4 表示一个城市中 16 条道路的网络。每条弧上的数字表示沿对应道路行驶所需的时间（单位：分钟）。

[网络总权重为 82]

Chan 需要检查道路是否状况良好。他必须每条道路至少经过一次。Chan 将从办公室 G 开始并结束，必须最小化检查路线所需的总时间。

对于此检查路线，

(a) 找到所需时间并写出一条可能的路线。必须清楚说明方法和推理。

Chan 想知道是否可以通过从家 B 开始、每条道路至少经过一次并在办公室 G 结束来减少旅行时间。

(b) 通过考虑所有相关节点的配对，找到从 B 到 G 的最小检查路线中需要经过两次的任何弧。必须清楚说明方法并展示计算过程。

(c) 确定以 G 结束的两条路线中哪条更快，从 G 开始的那条还是从 B 开始的那条。必须证明你的答案。

解答

(a)

思路

先找奇度节点。只有 C、D 为奇度节点，因此要得到从 G 出发并回到 G 的闭合巡回路线，必须把 C 与 D 之间的一条最短路径重复一次。最短路径为 C–F–G–D，权重为 7；把它加到网络总权重 82 上，再写出一条覆盖所有道路的可行路线。

答题过程

The only odd nodes are C and D. Their shortest connecting path is

C–F–G–D,\text{C--F--G--D},

with weight

1+3+3=7.1+3+3=7.

Therefore the minimum inspection time is

82+7=89 minutes.82+7=\boxed{89\text{ minutes}}.

One possible route is

G–D–G–J–H–E–A–D–C–A–B–E–F–B–C–F–C–G–F–G.\boxed{ \begin{gathered} \text{G--D--G--J--H--E--A--D--C}\\ \text{--A--B--E--F--B--C--F--C--G--F--G} \end{gathered} }.

(b)

思路

开放路线从 B 开始、在 G 结束。原网络的奇度节点是 C、D；把端点 B、G 也计入后，需要配对的相关节点为 B、C、D、G。比较这四个节点的三种配对方式，选择额外权重最小的一种，并据相应最短路径找出要重复的弧。

答题过程

The relevant nodes are B, C, D and G. The three possible pairings give:

(B,C)+(D,G)= (5+1)+3=9,(B,D)+(C,G)= (5+3+3)+(1+3)=15,(B,G)+(C,D)= (5+3)+(1+3+3)=15.\begin{align*} (\text{B,C})+(\text{D,G}) =&\,(5+1)+3=9,\\ (\text{B,D})+(\text{C,G}) =&\,(5+3+3)+(1+3)=15,\\ (\text{B,G})+(\text{C,D}) =&\,(5+3)+(1+3+3)=15. \end{align*}

The minimum pairing is therefore (B,C)+(D,G)(\text{B,C})+(\text{D,G}). The corresponding shortest paths are

B–F–CandD–G.\text{B--F--C} \quad\text{and}\quad \text{D--G}.

Hence the arcs that must be traversed twice are

BF, CF and DG.\boxed{\text{BF, CF and DG}}.

The minimum route length from B to G is

82+9=91 minutes.82+9=91\text{ minutes}.

(c)

思路

比较 (a) 中从 G 出发并回到 G 的 89 分钟，与 (b) 中从 B 出发、在 G 结束的 91 分钟；两者相差 2 分钟。

答题过程

The route starting at G takes 8989 minutes, whereas the route starting at B takes 9191 minutes.

Therefore the route starting at G is quicker by

91−89=2 minutes.91-89=\boxed{2\text{ minutes}}.