题目

Problem

[The total weight of the network is 494]

Direct roads between nine factories, A, B, C, D, E, F, G, H and J, are represented in Figure 3.

The number on each arc represents the lengths, in kilometres, of the corresponding road.

The table below shows the shortest distances, in kilometres, between the nine factories.

	A	B	C	D	E	F	G	H	J
A	-	15	7	25	15	42	64	51	46
B	15	-	22	40	30	57	49	36	31
C	7	22	-	32	22	49	71	58	53
D	25	40	32	-	10	17	57	70	71
E	15	30	22	10	-	27	67	66	61
F	42	57	49	17	27	-	40	53	72
G	64	49	71	57	67	40	-	13	32
H	51	36	58	70	66	53	13	-	19
J	46	31	53	71	61	72	32	19	-

Table of shortest distances

(a) Starting at A, use Prim’s algorithm to find a minimum spanning tree for the table of shortest distances. You must state the order in which you select the arcs of your tree.

(3)

(b) State the weight of the minimum spanning tree.

(1)

A route is needed that minimises the total distance to traverse each road at least once.

The route must start at E and finish at F.

(2)

It is now decided to start the route at C and finish the route at A. The route must include every road at least once and must still minimise the total distance travelled.

(d) By considering the pairings of all relevant nodes, find the roads that need to be traversed twice.

(4)

Naoko needs to visit all nine factories, starting and finishing at the same factory, and wishes to minimise the total distance travelled.

(e) Starting at B, use the nearest neighbour algorithm on the table of shortest distances to find an upper bound for the length of Naoko’s route. Write down the cycle, obtained from the table of shortest distances, which gives this upper bound.

(2)

(f) By deleting C and all of its arcs, use the values in the table of shortest distances to find a lower bound for the length of Naoko’s route.

(2)

题目中文翻译

[该网络的总权重为 494。]

图 3 表示九座工厂 A、B、C、D、E、F、G、H 和 J 之间的直达道路。

每条弧上的数字表示相应道路的长度，单位为千米。

下表给出九座工厂之间的最短距离，单位为千米。

	A	B	C	D	E	F	G	H	J
A	-	15	7	25	15	42	64	51	46
B	15	-	22	40	30	57	49	36	31
C	7	22	-	32	22	49	71	58	53
D	25	40	32	-	10	17	57	70	71
E	15	30	22	10	-	27	67	66	61
F	42	57	49	17	27	-	40	53	72
G	64	49	71	57	67	40	-	13	32
H	51	36	58	70	66	53	13	-	19
J	46	31	53	71	61	72	32	19	-

最短距离表

(a) 从 A 开始，对最短距离表使用 Prim 算法求一棵最小生成树。必须写明选择树中各条弧的次序。

(b) 写出最小生成树的权重。

现需要一条总距离最短的路线，使每条道路至少被经过一次。

该路线必须从 E 出发并在 F 结束。

现决定将路线改为从 C 出发并在 A 结束。该路线必须包含每条道路至少一次，并且总行驶距离仍须最小。

(d) 考虑所有相关顶点的配对，找出需要重复经过的道路。

Naoko 需要访问全部九座工厂，从同一座工厂出发并返回该工厂，并希望总行驶距离最小。

(e) 从 B 开始，对最短距离表使用最近邻算法，求 Naoko 路线长度的一个上界。写出由最短距离表得到、给出该上界的回路。

(f) 删除 C 及其所有弧，使用最短距离表中的数值求 Naoko 路线长度的一个下界。

解答

(a)

解法一

思路

展开

从 A 开始，每一步都从当前树内的顶点连向树外顶点，并选择权重最小的弧。出现权重相同的弧时可以任选其一，但必须保持后续选择符合 Prim 算法。这里采用官方评分资料列出的第一种并列处理次序。

答题过程

展开

Starting at A, one valid order for selecting the arcs is

\boxed{AC,\ AB,\ AE,\ DE,\ DF,\ BJ,\ HJ,\ GH}.

Thus all nine vertices are joined without forming a cycle, so these arcs form a minimum spanning tree.

Because of the tie between arcs of weight 15, the alternative order

AC,\ AE,\ DE,\ AB,\ DF,\ BJ,\ HJ,\ GH

is also valid.

(b)

解法一

思路

展开

把上一问选出的八条弧的权重相加，即得到最小生成树的总权重。

答题过程

展开

The weight of the minimum spanning tree is

7+15+15+10+17+31+19+13 =\boxed{127\text{ km}}.

(c)

解法一

思路

展开

原网络的奇度顶点为 C、E、F、H。开放式中国邮递员路线从 E 出发、在 F 结束，因此 E、F 应保留为奇度顶点，只需把 C、H 配成一对，并重复它们之间的最短路径。

答题过程

展开

The odd vertices of the original network are C, E, F and H.

Since the route starts at E and finishes at F, E and F must remain odd. Therefore the shortest path between C and H must be repeated. From the table, this distance is 58 km.

Hence the minimum route length is

494+58=\boxed{552\text{ km}}.

(d)

解法一

思路

展开

路线改为从 C 到 A 后，最终的奇度顶点必须是 C、A。将它们与原网络的奇度顶点集合比较，需要配对的顶点为 A、E、F、H。列出三种完整配对并比较总距离，再把最短距离表中的路径还原成原网络中实际需要重复的道路。

答题过程

展开

The vertices to be paired are A, E, F and H. The three possible pairings are

\begin{array}{c|c} \text{Pairing} & \text{Total distance (km)}\\ \hline AE+FH & 15+53=68\\ AF+EH & 42+66=108\\ AH+EF & 51+27=78 \end{array}

The minimum is obtained from $AE+FH$ .

The shortest path from F to H is $F-G-H$ , with length

40+13=53.

Therefore the roads that must be traversed twice are

\boxed{AE,\ FG,\ GH}.

(e)

解法一

思路

展开

从 B 出发，每一步前往尚未访问且距离当前顶点最近的工厂；访问全部工厂后再回到 B。按表逐步选择并累加相应距离。

答题过程

展开

Applying the nearest neighbour algorithm from B gives the cycle

\boxed{B-A-C-E-D-F-G-H-J-B}.

Its length is

\begin{align*} &\,15+7+22+10+17+40+13+19+31\\ =&\,\boxed{174\text{ km}}. \end{align*}

Therefore an upper bound for Naoko’s route is $174$ km.

(f)

解法一

思路

展开

删除 C 后，上一问最小生成树中的弧 AC 也被删除，剩余八个顶点的生成树权重为 $127-7$ 。再把 C 用与它相连的两条最短弧接回，得到旅行商问题的删点下界。

答题过程

展开

Deleting C removes the arc $AC$ of weight 7 from the minimum spanning tree. Hence a minimum spanning tree on the remaining vertices has weight

127-7=120.

The two shortest arcs incident with C have weights 7 and 22. Therefore the lower bound is

(127-7)+7+22=\boxed{149\text{ km}}.

	A	B	C	D	E	F	G	H	J
A	-	15	7	25	15	42	64	51	46
B	15	-	22	40	30	57	49	36	31
C	7	22	-	32	22	49	71	58	53
D	25	40	32	-	10	17	57	70	71
E	15	30	22	10	-	27	67	66	61
F	42	57	49	17	27	-	40	53	72
G	64	49	71	57	67	40	-	13	32
H	51	36	58	70	66	53	13	-	19
J	46	31	53	71	61	72	32	19	-

	A	B	C	D	E	F	G	H	J
A	-	15	7	25	15	42	64	51	46
B	15	-	22	40	30	57	49	36	31
C	7	22	-	32	22	49	71	58	53
D	25	40	32	-	10	17	57	70	71
E	15	30	22	10	-	27	67	66	61
F	42	57	49	17	27	-	40	53	72
G	64	49	71	57	67	40	-	13	32
H	51	36	58	70	66	53	13	-	19
J	46	31	53	71	61	72	32	19	-

	A	B	C	D	E	F	G	H	J
A	-	15	7	25	15	42	64	51	46
B	15	-	22	40	30	57	49	36	31
C	7	22	-	32	22	49	71	58	53
D	25	40	32	-	10	17	57	70	71
E	15	30	22	10	-	27	67	66	61
F	42	57	49	17	27	-	40	53	72
G	64	49	71	57	67	40	-	13	32
H	51	36	58	70	66	53	13	-	19
J	46	31	53	71	61	72	32	19	-

	A	B	C	D	E	F	G	H	J
A	-	15	7	25	15	42	64	51	46
B	15	-	22	40	30	57	49	36	31
C	7	22	-	32	22	49	71	58	53
D	25	40	32	-	10	17	57	70	71
E	15	30	22	10	-	27	67	66	61
F	42	57	49	17	27	-	40	53	72
G	64	49	71	57	67	40	-	13	32
H	51	36	58	70	66	53	13	-	19
J	46	31	53	71	61	72	32	19	-

IAL 2024 June D1 Q4

题目

解答

(a)

解法一

思路

答题过程

(b)

解法一

思路

答题过程

(c)

解法一

思路

答题过程

(d)

解法一

思路

答题过程

(e)

解法一

思路

答题过程

(f)

解法一

思路

答题过程

	A	B	C	D	E	F	G	H	J
A	-	15	7	25	15	42	64	51	46
B	15	-	22	40	30	57	49	36	31
C	7	22	-	32	22	49	71	58	53
D	25	40	32	-	10	17	57	70	71
E	15	30	22	10	-	27	67	66	61
F	42	57	49	17	27	-	40	53	72
G	64	49	71	57	67	40	-	13	32
H	51	36	58	70	66	53	13	-	19
J	46	31	53	71	61	72	32	19	-

	A	B	C	D	E	F	G	H	J
A	-	15	7	25	15	42	64	51	46
B	15	-	22	40	30	57	49	36	31
C	7	22	-	32	22	49	71	58	53
D	25	40	32	-	10	17	57	70	71
E	15	30	22	10	-	27	67	66	61
F	42	57	49	17	27	-	40	53	72
G	64	49	71	57	67	40	-	13	32
H	51	36	58	70	66	53	13	-	19
J	46	31	53	71	61	72	32	19	-