二分图匹配：任务与兵力的配对

二分图匹配：任务与兵力的配对

匈牙利数学家的名字挂在了这个问题上：任务清单与队员名册摆在参谋桌上，每名队员只胜任其中若干项，每人至多领一项、每项只派一人，最多能配成多少对？从婚姻介绍所的古老比喻到现代的排班、招录、广告分配，这道"一一配对"题在工程界的出场率经久不衰。本章战役收官，本节把二分图匹配讲透：先用上一节的流模型把它一网打尽，再推演匈牙利算法的增广思路，最后引出匹配、覆盖、独立集之间的对偶关系——它直接通向第 8 章的收尾攻坚。

问题的形态与流模型翻译

二分图的定义来自第 1 章：顶点分属两个阵营，所有边都横跨阵营、阵营内部无边。匹配是边集的子集，要求任何两条边不共享端点——直白说就是"配了对，不劈腿"。最大匹配是边数最多的匹配；若某个匹配让每个顶点都有伴，叫完美匹配。

上一节的流机器在这里直接开动：左阵营运任务、右阵营运队员，胜任关系是边；添一个超级源连向全部任务（容量一），全部队员连向超级汇（容量一），原边容量也设一。容量一的含义恰是"至多配一次"；跑最大流，有流的胜任边构成匹配，流值即匹配数。

增广思路：匈牙利算法的骨架

不必真去架源汇，匈牙利算法把"增广"的思路直接画在二分图上。称一条交替使用"非匹配边与匹配边"的路径为交替路；若交替路从一个未配对的左顶点出发、终结于未配对的右顶点，它是增广路——把路上的边角色互换（非匹配变匹配、匹配变非匹配），匹配数净增一。算法骨架因此极简：对每个左顶点尝试找增广路，找到就增广；全部尝试完毕即达最大。证明"再也增广不了就是最大"要请出对偶：König 定理断言二分图上最大匹配数等于最小顶点覆盖数（能触到每条边的最少顶点数）——匹配与覆盖互为上下界，二分图上恰好咬合；增广路穷尽时的构图恰好给出同值的覆盖，两边同时锁死。这一定理与上一节的最大流最小割同属一族（事实上它就是后者在单位容量二分图上的特例）。

import networkx as nx

def hungarian_match(G, left):
    """匈牙利算法：返回 匹配边列表"""
    match_r = {}                          # 右顶点 -> 已配左顶点
    def try_aug(u, visited):
        for v in G[u]:                    # u 的每个候选
            if v in visited:
                continue
            visited.add(v)
            if v not in match_r or try_aug(match_r[v], visited):
                match_r[v] = u            # 直接配对，或让原配让位
                return True
        return False

    matched = 0
    for u in left:                        # 每个左顶点各试一轮
        if try_aug(u, set()):
            matched += 1
    return [(l, r) for r, l in match_r.items()], matched

B = nx.Graph()
tasks = ["架桥", "侦察", "医护", "通讯", "炊事"]
crew = ["甲", "乙", "丙", "丁"]
pairs = [("架桥","甲"),("架桥","丁"),("侦察","甲"),("侦察","乙"),
         ("医护","乙"),("医护","丙"),("通讯","丙"),("炊事","丙"),("炊事","丁")]
B.add_edges_from(pairs)
edges, size = hungarian_match(B, tasks)
print("匹配:", edges, "| 匹配数:", size)
print("nx 对照:", nx.max_weight_matching(B, maxcardinality=True).__len__())
​

try_aug 的递归是算法的心脏：右顶点 v 若已名花有主，就去说服它的原配让位——原配在剩余候选里再找新欢（递归下探），说服链条一路传导，任何一环成功即整条增广路打通。这种"给老配对重新洗牌"的能力，正是增广路"非匹配边、匹配边交替"在代码里的显形。

复杂度账单：每个左顶点发起一次深度优先尝试，每次最坏扫全图，总计与"左顶点数乘边数"同阶——对排班、招录这类规模绰绰有余；工业级实现（Hopcroft-Karp）按"多路同时增广"组织，把代价压到边数乘根号量级，成为大图上的标准配置。

完美匹配与带权版本

完美匹配要求每个顶点都被配上（两阵营顶点数须相等）。它是否存在有免费的判据——Hall 定理：存在完美匹配，当且仅当左阵营的任何子集，其"邻居集合"都不小于该子集本身。直白版："每批任务，能胜任它们的人数至少与任务数齐平，全体才都能配出去"。Hall 定理的证明用的正是增广失败时的构图（失败时找到的那个"邻居不够"的子集就是反例）——判定与构造又一次互为表里。

带权版本问"配满之外还要总收益最大"：任务有利润、队员有偏好，最大权匹配是另一个世界的问题。经典解法（常被称作 K-M 算法或按线性规划对偶理解的一系方法）引入"顶标"——给每个顶点一个价格，只允许在"边权恰等于两端顶标之和"的相等子图里增广，失败则全面下调顶标扩大相等子图。它的对偶视角与本章一脉相承：最大权匹配等于最小顶标和。带权匹配在广告分配（流量与广告位的竞价匹配）、蛋白质比对（氨基酸相似度网）里担任主力。

def hall_violation(B, left):
    """找 Hall 违例子集：邻居不足的左阵营子集（若无则返回 None）"""
    import itertools
    for k in range(1, len(left)):
        for subset in itertools.combinations(left, k):
            nbs = set()
            for u in subset:
                nbs.update(B[u])
            if len(nbs) < len(subset):
                return subset, nbs
    return None

print("Hall 违例:", hall_violation(B, tasks))
​

示例图里五个任务只有四名队员，Hall 检查立刻点名"人手不足"的子集——完美匹配无望，最大匹配封顶于较小的数。这正体现了 Hall 定理的实用价值：失败时它不只知道"不行"，还知道卡在哪一批任务上。

应用与变体

排班与招录是天然主场：护士排班、课程分配、入职轮岗，凡"双方互选、一夫一妻"皆可套。变体上：带权二分匹配加收益维度（上文顶标法）；稳定匹配改换目标——不追配对数最多，而要"没有两人都更愿意背叛现配"（求婚拒绝算法以轮番求婚达成稳定，奠定了市场设计的 Nobel 级应用）；一般图的匹配去掉二分限制后难度陡增（需处理奇圈的花结构，Blossom 算法），属于进阶篇章。匹配与第 8 章的关系也在此收口：最大匹配是求独立集、顶点覆盖、边覆盖等一系列"极值子集"问题的钥匙孔，二分图上的这一族问题全部有多项式解，而一般图上它们瞬间变脸——这正是下一章要讲的故事。

⚠️ 常见坑：把任意图当二分图跑匈牙利。奇数环（如三角关系）会让"让位递归"绕圈死循环——动手前先用第 1 章的奇环判定（或双色染色）验明正身。

💡 关键直觉：增广路的本质是"谈判链"——新人要进门，原配被请去隔壁找位子，链条传导直到皆大欢喜或彻底碰壁。图论的很多算法都有这种"局部重组、全局受益"的 negotiation 味道。

配对战役收官，网络流与匹配的全套兵法到手。下一章远征队转入收尾攻坚：给冲突排解上色，为哨所选址权衡——图论里最古老也最难缠的一族问题登场。