图 1 显示了六名工人 A、B、C、D、E 和 F 分配到六个任务 1、2、3、4、5 和 6 的可能分配。

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

(a) 从此初始匹配开始，使用最大匹配算法找到改进匹配。应说明使用的交替路径并列出改进匹配。

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

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

(c) 将 (a) 中找到的改进匹配作为新的初始匹配，使用最大匹配算法找到完全匹配。应说明使用的交替路径并列出完全匹配。

初始匹配为 $B=1,C=2,D=6,F=5$，未匹配工人为 $A,E$，未匹配任务为 3、4。从未匹配工人 $A$ 出发，沿“未匹配边、已匹配边”交替前进，最终到达未匹配任务 4；翻转整条路径上各边的匹配状态，即可把匹配数由 4 增至 5。

Starting from the initial matching

use the alternating path

Changing the status of each edge on this path gives

Keeping the unchanged allocation $B=1$, an improved matching is

with $E$ unmatched.

也可从另一个未匹配工人 $E$ 出发，经任务 2、工人 $C$、任务 5 和工人 $F$ 到达未匹配任务 4。翻转这条较短交替路径后，同样得到含五组分配的改进匹配，但这次未匹配的是 $A$。

Alternatively, use the alternating path

Changing the status of its edges gives

Keeping $B=1$ and $D=6$, the improved matching is

with $A$ unmatched.

任务 1 和任务 3 都只能由工人 $B$ 完成。一个工人不可能同时承担两个任务，因此这两个任务中至少有一个无法分配，完整匹配不存在。

Tasks $1$ and $3$ can both be performed only by worker $B$. Since one worker cannot be matched to two tasks, at least one of these tasks must remain unmatched.

Therefore a complete matching is impossible.

也可从工人一侧说明 Hall 条件失败：$A$ 只能做任务 6，$E$ 只能做任务 2，而 $D$ 也只能做任务 2 或 6。三个工人合计只有两个可选任务，所以三人不可能全部获得不同任务。

Worker $A$ can perform only task $6$, worker $E$ can perform only task $2$, and worker $D$ can perform only tasks $2$ and $6$.

Thus the three workers $A,D,E$ have only the two tasks $2,6$ available between them. Hence they cannot all be matched, so a complete matching is impossible.

承接 (a) 解法一，此时 $E$ 未匹配。新增边 $A-1$ 后，可从 $E$ 出发，经已匹配关系逐步转移，最后由 $B$ 接到未匹配任务 3。翻转整条交替路径后，六名工人均可获得不同任务。

Using the improved matching from Method 1 in part (a), take the alternating path

Changing the status of the edges gives

The allocations $C=5$ and $F=4$ remain unchanged. Therefore the complete matching is

承接 (a) 解法二，此时未匹配工人为 $A$。新增 $A-1$ 后，只需沿 $A-1=B-3$ 翻转状态，便可把 $A$ 分配给任务 1、把 $B$ 移到原本未匹配的任务 3。

Using the improved matching from Method 2 in part (a), take the alternating path

Changing the status of the two edges gives $A=1$ and $B=3$. Keeping the other allocations unchanged gives