CalcGospel 國際數學圖譜
返回

IAL 2019 June D1 Q1

A Level / Edexcel / D1

IAL 2019 June Paper · Question 1

题目

Problem

Figure 1 shows the possible allocations of six workers, A, B, C, D, E and F, to six tasks, 1, 2, 3, 4, 5 and 6. Each task must be assigned to exactly one worker and each worker must be assigned to exactly one task.

(a) Write down the technical name given to the type of graph shown in Figure 1.

(1)

Figure 2 shows an initial matching.

(b) Starting from the given initial matching, use the maximum matching algorithm to find an alternating path from C to 1. Hence find an improved matching. You should list the alternating path you use, and state your improved matching.

(3)

(c) Explain why it is not possible to find a complete matching.

(1)

After training, task 5 is added to worker C’s possible allocation.

(d) Starting from the improved matching found in (b) use the maximum matching algorithm to find a complete matching. You should list the alternating path you use, and state your complete matching.

(3)

(Total 8 marks)

题目中文翻译

图 1 显示了六名工人 A、B、C、D、E 和 F 分配到六个任务 1、2、3、4、5 和 6 的可能分配方案。每个任务必须恰好分配给一名工人，每名工人必须恰好分配给一个任务。

(a) 写出图 1 所示图类型的技术名称。

图 2 显示了一个初始匹配。

(b) 从给定的初始匹配开始，使用最大匹配算法找到从 C 到 1 的交替路径。由此找到一个改进的匹配。你应该列出你使用的交替路径，并说明你的改进匹配。

(c) 解释为什么不可能找到完全匹配。

培训后，任务 5 被添加到工人 C 的可能分配中。

(d) 从 (b) 中找到的改进匹配开始，使用最大匹配算法找到完全匹配。你应该列出你使用的交替路径，并说明你的完全匹配。

解答

(a)

思路

圖中的頂點分為「工人」與「工作」兩組，所有邊都只連接不同組的頂點，因此這類圖稱為二分圖。

答题过程

It is a bipartite graph.

(b)

思路

從尚未配對的工人 CC 出發，尋找通往尚未分配工作 11 的交替路徑。沿路交替經過未配對邊與已配對邊，再把路徑上所有邊的配對狀態互換，便可使配對數增加一個。

答题过程

An alternating path from CC to task 11 is

C−4=F−6=A−3=B−1,C-4=F-6=A-3=B-1,

where == represents an edge in the current matching. Changing the status of the edges along this path gives

C=4−F=6−A=3−B=1.C=4-F=6-A=3-B=1.

Hence an improved matching is

A=3,B=1,C=4,D=5,F=6,\begin{aligned} A&=3,\quad B=1,\quad C=4,\\ D&=5,\quad F=6, \end{aligned}

with EE unmatched.

(c)

思路

檢查工人 C,E,FC,E,F 可執行的工作集合。這三名工人合起來只能執行工作 44 和 66，因此三人無法同時獲得不同工作；這違反了完整配對所需的條件。

答题过程

Workers CC, EE and FF can collectively perform only tasks 44 and 66. Thus three workers have only two possible tasks between them, so a complete matching is impossible.

(d)

思路

新增邊後，從未配對的工人 EE 出發，可經由新增的工作 55 建立增廣路徑。官方評分資料給出兩條有效的交替路徑；互換任一條路徑上的邊，都能得到完整配對。

答题过程

Method 1

An alternating path is

E−6=F−4=C−5=D−2.E-6=F-4=C-5=D-2.

Changing the status of its edges gives

E=6−F=4−C=5−D=2.E=6-F=4-C=5-D=2.

Together with the unchanged assignments, a complete matching is

A=3,B=1,C=5,D=2,E=6,F=4.\begin{aligned} A&=3,\quad B=1,\quad C=5,\\ D&=2,\quad E=6,\quad F=4. \end{aligned}

Method 2

Alternatively, use the alternating path

E−6=F−4=C−5=D−3=A−2.E-6=F-4=C-5=D-3=A-2.

Changing the status of its edges gives

E=6−F=4−C=5−D=3−A=2.E=6-F=4-C=5-D=3-A=2.

This gives the complete matching

A=2,B=1,C=5,D=3,E=6,F=4.\begin{aligned} A&=2,\quad B=1,\quad C=5,\\ D&=3,\quad E=6,\quad F=4. \end{aligned}