题目
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.
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.
(c) Explain why it is not possible to find a complete matching.
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.
(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) 中找到的改进匹配开始，使用最大匹配算法找到完全匹配。你应该列出你使用的交替路径，并说明你的完全匹配。