CalcGospel 國際數學圖譜
返回

D1 2019 June 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 所示图类型的技术名称。

(1)

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

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

(3)

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

(1)

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

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

(3)

（总分 8 分）

解答

(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,\begin{align*} &\,C-4=F-6\\ &\,\hspace{2pt}=A-3=B-1, \end{align*}

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.\begin{align*} &\,C=4-F=6\\ &\,\hspace{2pt}-A=3-B=1. \end{align*}

Hence an improved matching is

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

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.

解法二

思路

展开

也可以从任务一侧检查：任务 1,2,3,51,2,3,5 只能由工人 A,B,DA,B,D 完成。四个任务只有三名可用工人，每人又只能承担一个任务，因此至少一个任务无法分配。

答题过程

展开

Only workers AA, BB and DD can perform tasks 11, 22, 33 and 55. These three workers cannot cover four tasks when each worker is assigned to exactly one task. Hence a complete matching is impossible.

(d)

解法一

思路

展开

新增边后，从未配对的工人 EE 出发，经由新增的 CC 到工作 55 的边建立增广路径，再沿 DD 到未分配的工作 22。互换路径上的配对状态，即可得到完全匹配。

答题过程

展开

An alternating path is

 E−6=F−4 =C−5=D−2.\begin{align*} &\,E-6=F-4\\ &\,\hspace{2pt}=C-5=D-2. \end{align*}

Changing the status of its edges gives

 E=6−F=4 −C=5−D=2.\begin{align*} &\,E=6-F=4\\ &\,\hspace{2pt}-C=5-D=2. \end{align*}

Together with the unchanged assignments, a complete matching is

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

解法二

思路

展开

同样从 EE 出发，经 CC 到工作 55，再通过 DD、工作 33 和 AA 到达工作 22。这条增广路径更长，但仍交替经过未配对边与已配对边，互换状态后也能得到完全匹配。

答题过程

展开

Alternatively, use the alternating path

 E−6=F−4 =C−5=D−3 =A−2.\begin{align*} &\,E-6=F-4\\ &\,\hspace{2pt}=C-5=D-3\\ &\,\hspace{4pt}=A-2. \end{align*}

Changing the status of its edges gives

 E=6−F=4 −C=5−D=3 −A=2.\begin{align*} &\,E=6-F=4\\ &\,\hspace{2pt}-C=5-D=3\\ &\,\hspace{4pt}-A=2. \end{align*}

This gives the complete matching

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