二分图匹配

二分图把顶点分成两组，每条边都连接不同组。边可以表示某个工人能够承担某项任务，匹配则选择一些不共享端点的边，让每个参与对象至多进入一个配对；最大基数匹配要求配对数尽可能大。

覆盖全部顶点的匹配称为完美匹配，存在最大匹配不代表一定存在完美匹配。两组人数、允许边的分布和孤立顶点等结构都可能限制覆盖；若目标是收益最大而非数量最大，还要引入权重并求不同的优化问题。

参考：[1]

只要看见一条空闲边就配对，可能很快停在非最优结果。设A可配X或Y，B只能配X，若先选A—X，便没有可直接加入的边；但改为A—Y与B—X，可以从一对增加到两对。

增广路的边在未选中与已选中之间交替，两端都是尚未匹配的顶点。把路径上选中状态整体翻转，就少掉若干旧边、加入多一条新边，使匹配数增加一，同时仍不共享端点。算法利用这类重新安排超越只会贪心添加的局部结果。

参考：[2]

可以新增源点和汇点，让源到左侧、右侧到汇的容量均为一，中间保留允许配对的连接。整数增广得到的单位流可解释为配对：两侧容量使一个对象不能同时承担多份流。Princeton归约对中间兼容边使用无穷容量，端点的一单位限制仍控制最终匹配。

二分图还满足Kőnig定理：最大匹配的边数等于最小顶点覆盖的顶点数，覆盖要求每条边至少接触一个所选顶点。这提供另一类最优性证据；该等式不能未经条件检查就推广到任意非二分图。

参考：[3] [1]