题目
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.
Figure 2 shows an initial matching.
(a) Starting from this initial matching, use the maximum matching algorithm to find an improved matching. You should state the alternating path you use and list your improved matching.
(b) Explain why it is not possible to find a complete matching.
After training, task 1 is added to worker A’s possible allocations.
(c) Taking the improved matching found in (a) as the new initial matching, use the maximum matching algorithm to find a complete matching. You should state the alternating path you use and list your complete matching.
题目中文翻译
图 1 显示了六名工人 A、B、C、D、E 和 F 分配到六个任务 1、2、3、4、5 和 6 的可能分配。
图 2 显示了一个初始匹配。
(a) 从此初始匹配开始，使用最大匹配算法找到改进匹配。应说明使用的交替路径并列出改进匹配。
(b) 解释为什么不可能找到完全匹配。
培训后，任务 1 被添加到工人 A 的可能分配中。
(c) 将 (a) 中找到的改进匹配作为新的初始匹配，使用最大匹配算法找到完全匹配。应说明使用的交替路径并列出完全匹配。