演算法›Ch4 圖論演算法第 2 題/共 111 題
2. 二分圖匹配、Maximum Matching
#AL-04-002易二分圖匹配Maximum Matching
A company needs to assign 3 workers to 3 tasks. Each worker can perform only the tasks listed below:
- Worker : Tasks
- Worker : Task
- Worker : Tasks
Each worker can be assigned to at most one task, and each task to at most one worker. Which of the following statements is true?
參考答案與解析
答案 (E):W2 只能做 T1,故必先指派 W2→T1;剩下 W1 只能選 T2(T1 被占),W3 只能選 T3(T2 被占)。三人三工作恰好一一對應,是完美匹配(perfect matching),且這個指派是唯一的(每一步都被強迫),所以 (D) 說有兩組不同的最大匹配是錯的。
📄 台大115
▤完整推導請見《WH 資工筆記 · 演算法》Ch4 圖論演算法