基础概念二分图简单说就是两个阵营的图比如左边是「男生」集合A右边是「女生」集合B边代表男生和女生能配对没有跨阵营内部的边比如男生之间不连边。完美匹配左边每个男生都能找到一个唯一的女生配对右边每个女生也只配一个男生相当于全员配对成功。霍尔条件对于左边集合A的任意子集SS中节点的邻居集合N(S)的大小必须 ≥≥ S的大小。即 ∣()∣≥∣∣∣N(S)∣≥∣S∣ 对所有 ⊆S⊆A 成立。最大流把二分图变成水流网络源点水龙头往左边男生送水男生往能配对的女生送水女生往汇点水池送水最大流就是最多能送多少水对应最多能配对多少对。例子贯穿全文设定左边男生集合A {甲, 乙, 丙}3人右边女生集合B {A, B, C}3人边能配对的关系甲→A、甲→B乙→B、乙→C丙→C目标判断能不能实现「完美匹配」同时搞懂霍尔定理和最大流是怎么解决这个问题的。霍尔定理——用子集检查判断能不能匹配核心思路要实现完美匹配左边任意一个子集S能配对的女生数量N(S)必须 ≥≥ 这个子集的男生数量。简单说不管你从左边挑几个男生他们能选的女生都不能比挑的男生少——不然就有男生配不上。步骤拆解结合例子一步步来我们要检查「左边所有可能的子集」看是否都满足女生数 ≥≥ 男生数霍尔条件。子集规模1挑1个男生挑甲能配对的女生是{A,B}2人≥≥ 1人满足挑乙能配对的女生是{B,C}2人≥≥ 1人满足挑丙能配对的女生是{C}1人≥≥ 1人满足子集规模2挑2个男生挑甲乙能配对的女生是{A,B,C}3人≥≥ 2人满足挑甲丙能配对的女生是{A,B,C}3人≥≥ 2人满足挑乙丙能配对的女生是{B,C}2人≥≥ 2人满足子集规模3挑所有男生即SA能配对的女生是{A,B,C}3人≥≥ 3人满足霍尔定理的结论例子中所有子集都满足霍尔条件所以「存在完美匹配」。比如甲→A、乙→B、丙→C或其他组合。注意事项霍尔定理只告诉你能不能匹配不告诉你具体怎么匹配如果有一个子集不满足就一定不能完美匹配。比如若丙只能配对B边改成丙→B挑乙丙能配对的女生只有{B}1人2人就不能完美匹配复杂度坑左边有n个男生子集总数是 22n比如n10就有1024个子集n稍微大一点比如20就查不过来指数级复杂度只能用于小数据判断。最大流——用水流模拟算出怎么匹配、能匹配多少核心思路把二分图改成水流系统用水流能不能流满模拟能不能完美匹配加两个辅助点源点s水龙头、汇点t水池源点s→每个男生水流容量1意思是每个男生最多配1个女生每个男生→能配对的女生水流容量1意思是每个男生和女生最多配1次每个女生→汇点t水流容量1意思是每个女生最多配1个男生最大流就是最多能流多少水到水池水流的路径就是配对的方式。步骤拆解结合例子一步步来我们用简单水流模拟不用复杂算法就能看出最大流是多少。构建水流网络对应例子源点s → 甲容量1、s→乙容量1、s→丙容量1甲→A1、甲→B1乙→B1、乙→C1丙→C1A→t1、B→t1、C→t1第一次流水找一条路径路径s→甲→A→t水流1此时甲、A、这条路径的容量都用完不能再流水已流水量1对应1对配对甲→A第二次流水再找一条路径路径s→乙→B→t水流1此时乙、B、这条路径的容量都用完已流水量2对应2对配对甲→A、乙→B第三次流水再找一条路径路径s→丙→C→t水流1此时丙、C、这条路径的容量都用完已流水量3对应3对配对甲→A、乙→B、丙→C检查是否还能流水源点s到男生的路径都用完甲、乙、丙都流了1单位水没有新的路径能流水到汇点t流水结束最大流的结论例子中最大流3和左边男生数量3相等所以「存在完美匹配」而且流水路径就是具体的配对方式甲→A、乙→B、丙→C。注意事项最大流不仅能判断能不能匹配还能给出具体匹配方案复杂度友好用常用的Dinic算法复杂度是多项式级别比如n1000也能快速算出适合实际做题、工程使用水流容量1是因为每个点只能配对1次如果是一个男生能配多个女生容量改一下就行比如容量2就是能配2个。核心对比与术语规范两者核心对比对比维度霍尔定理最大流二分图匹配核心作用判断能不能完美匹配理论条件算出最多能匹配多少对具体怎么匹配实际算法核心思路检查左边所有子集是否满足 ∣()∣≥∣∣∣N(S)∣≥∣S∣构建流网络模拟水流求最大流水量能否给出匹配方案不能只给能/不能的结论能流水路径就是匹配方案复杂度(2)O(2n)指数级小数据可用(2)O(V2E)多项式级大数据首选两者关联霍尔条件满足 ↔ 最大流左边节点数完美匹配最大流算法本质是间接验证霍尔条件不用枚举子集使用建议理解原理、判断小数据不用实际计算实际做题、解决问题直接用比如编程、刷题正式术语对照文档用语标准术语英文说明小团体子集Subset图论中的标准术语能配对的女生邻居集合NeighborhoodN(S)表示子集S的所有邻居水流网络流网络Flow Network最大流问题的标准模型水龙头/水池源点/汇点Source/Sink流网络中的特殊节点霍尔定理的严格表述定理Hall, 1935设G(X,Y,E)是一个二分图其中 ∣∣∣∣∣X∣∣Y∣。则G存在完美匹配当且仅当对于X的任意子集S都有 ∣()∣≥∣∣∣N(S)∣≥∣S∣。等价表述最大匹配的大小 ∣∣−max⁡⊆(∣∣−∣()∣)∣X∣−maxS⊆X​(∣S∣−∣N(S)∣)推论若对于所有 ⊆S⊆X 都有 ∣()∣≥∣∣∣N(S)∣≥∣S∣k则存在大小为 ∣∣∣X∣k 的匹配允许部分节点不匹配。算法细节补充最大流算法核心概念残余网络Residual Network原图中每条边(u,v)容量为c在残余网络中保留正向边(u,v)容量c同时添加反向边(v,u)容量0允许撤销之前的匹配增广路径Augmenting Path在残余网络中从源点到汇点的一条路径路径上的最小残余容量称为瓶颈容量沿增广路径发送瓶颈容量的流量最大流最小割定理最大流的值 最小割的容量割是将节点分为S和T两部分其中源点∈S汇点∈T主要算法对比算法时间复杂度核心思想适用场景Ford-Fulkerson(×max_flow)O(E×max_flow)DFS找增广路径简单实现小规模Edmonds-Karp(2)O(VE2)BFS找最短增广路径保证多项式时间Dinic(2)O(V2E)层次图阻塞流稠密图大规模Hopcroft-Karp()O(EV​)多路增广二分图匹配专用匈牙利算法(3)O(V3)增广路径翻转二分图匹配二分图匹配的匈牙利算法算法步骤从任意未匹配节点开始寻找增广路径交替路径沿增广路径翻转匹配状态重复直到无法找到增广路径与最大流的关系匈牙利算法本质上是最大流算法在二分图上的特例。边界情况与扩展左右节点数不相等情况∣∣∣∣∣X∣∣Y∣ 或 ∣∣∣∣∣X∣∣Y∣处理若 ∣∣∣∣∣X∣∣Y∣最大匹配数 ≤∣∣≤∣X∣霍尔条件需修改为 ∣()∣≥∣∣∣N(S)∣≥∣S∣ 对所有 ⊆S⊆X若 ∣∣∣∣∣X∣∣Y∣最大匹配数 ≤∣∣≤∣Y∣需检查Y的子集实际应用任务分配中员工数可能多于或少于任务数。不存在完美匹配时的最大匹配定理最大匹配数 ∣∣−max⁡⊆(∣∣−∣()∣)∣X∣−maxS⊆X​(∣S∣−∣N(S)∣)例子文档中修改后的例子丙只能配对Bmax⁡⊆(∣∣−∣()∣)1maxS⊆X​(∣S∣−∣N(S)∣)1取S{乙,丙}最大匹配数 3−123−12。带权二分图问题最大权匹配Maximum Weight Matching算法KM算法Kuhn-Munkres(3)O(V3)转化为最小费用最大流应用员工分配任务时不同员工完成不同任务有不同效率。多重匹配问题一个节点可以匹配多个节点如一个员工可做多个任务处理修改流网络中边的容量源点到左边节点的容量 该节点可匹配数右边节点到汇点的容量 该节点可匹配数实际应用场景场景1人员分配最常用例子公司有5名员工甲、乙、丙、丁、戊5项工作A、B、C、D、E每名员工只能做1项工作每项工作只能1人做员工擅长的工作如下甲→A、B乙→B、C丙→C、D丁→D、E戊→E、A。霍尔定理的作用判断能不能让所有员工都分配到擅长的工作完美匹配。检查所有员工子集比如挑甲、乙、丙他们擅长的工作是A、B、C、D4项≥≥ 3人所有子集都满足条件说明能全员分配。最大流的作用算出具体怎么分配比如甲→A、乙→B、丙→C、丁→D、戊→E如果员工数多于工作数还能算出最多能分配多少名员工最大匹配数。场景2资源分配例子学校有3间实验室A、B、C4个科研小组1、2、3、4每间实验室只能容纳1个小组每个小组只能用1间实验室小组适配的实验室如下小组1→A、B小组2→B、C小组3→A、C小组4→A。霍尔定理的作用判断能不能让3个小组用上实验室完美匹配实验室数量少小组选3个。挑小组1、2、3适配的实验室是A、B、C3间≥≥ 3人满足条件说明能实现3个小组分配。最大流的作用确定哪3个小组用哪间实验室比如小组1→A、小组2→B、小组3→C同时能算出最多能让几个小组用上实验室这里是3个避免资源浪费。场景3任务调度例子老师有5项作业批改任务3名学生志愿者每名志愿者最多批改2项作业每项作业只能由1名志愿者批改志愿者能批改的作业类型如下志愿者1→作业1、2志愿者2→作业2、3、4志愿者3→作业4、5。霍尔定理的作用判断能不能让所有作业都被批改这里志愿者最多能批改3×26项作业5项检查子集比如挑作业1、2、3能批改的志愿者是1、22人可批改4项 ≥≥ 3项满足条件说明能全部批改。最大流的作用调整水流容量志愿者→作业的容量2算出具体调度方案比如志愿者1→作业1、2志愿者2→作业3、4志愿者3→作业5确保高效完成所有任务。场景4在线广告投放场景广告位左边与广告主右边的匹配约束每个广告位只能展示一个广告每个广告主有预算限制可匹配多个位置广告位和广告主有相关性边存在条件建模二分图广告位 vs 广告主边相关性超过阈值容量广告主的预算权重点击率或收益场景5课程表安排场景课程左边与时间段右边的分配约束每个课程需要特定数量的时间段每个时间段只能安排一门课程某些课程不能安排在某些时间段建模二分图课程 vs 时间段边课程可以安排的时间段容量课程需要的时间段数目标最大化安排的课程数核心总结不管是人员、资源还是任务只要涉及两个阵营的配对且每个个体只能匹配1个或固定数量对象都能用到两者想快速判断能不能实现全员/全量匹配用霍尔定理小数据场景比如10人以内想算出具体怎么匹配最多能匹配多少用最大流大数据、实际落地场景比如几十、上百人/任务。代码示例二分图最大匹配Python - Hopcroft-Karp算法from collections import defaultdict, dequeclass BipartiteMatching:def __init__(self, n_left, n_right):self.n_left n_leftself.n_right n_rightself.graph defaultdict(list)def add_edge(self, u, v):添加左边节点u到右边节点v的边self.graph[u].append(v)def bfs(self, match_left, match_right, dist):BFS寻找增广路径queue deque()for u in range(self.n_left):if match_left[u] -1:dist[u] 0queue.append(u)else:dist[u] float(inf)dist[-1] float(inf)while queue:u queue.popleft()if dist[u] dist[-1]:for v in self.graph[u]:if dist[match_right[v]] float(inf):dist[match_right[v]] dist[u] 1queue.append(match_right[v])return dist[-1] ! float(inf)def dfs(self, u, match_left, match_right, dist):DFS寻找增广路径if u ! -1:for v in self.graph[u]:if dist[match_right[v]] dist[u] 1:if self.dfs(match_right[v], match_left, match_right, dist):match_right[v] umatch_left[u] vreturn Truedist[u] float(inf)return Falsereturn Truedef max_matching(self):计算最大匹配match_left [-1] * self.n_leftmatch_right [-1] * self.n_rightdist [-1] * (self.n_left 1)matching 0while self.bfs(match_left, match_right, dist):for u in range(self.n_left):if match_left[u] -1:if self.dfs(u, match_left, match_right, dist):matching 1return matching# 使用示例bm BipartiteMatching(3, 3)bm.add_edge(0, 0) # 甲→Abm.add_edge(0, 1) # 甲→Bbm.add_edge(1, 1) # 乙→Bbm.add_edge(1, 2) # 乙→Cbm.add_edge(2, 2) # 丙→Cprint(f最大匹配数: {bm.max_matching()}) # 输出: 3最大流算法DinicPython实现from collections import dequeclass Dinic:def __init__(self, n):self.n nself.graph [[] for _ in range(n)]self.level [0] * nself.ptr [0] * ndef add_edge(self, u, v, cap):添加边u-v容量为capself.graph[u].append([v, cap, len(self.graph[v])])self.graph[v].append([u, 0, len(self.graph[u]) - 1])def bfs(self, s, t):BFS构建层次图self.level [-1] * self.nself.level[s] 0queue deque([s])while queue:u queue.popleft()for v, cap, rev in self.graph[u]:if cap 0 and self.level[v] -1:self.level[v] self.level[u] 1queue.append(v)return self.level[t] ! -1def dfs(self, u, t, f):DFS寻找阻塞流if u t:return ffor i in range(self.ptr[u], len(self.graph[u])):v, cap, rev self.graph[u][i]if cap 0 and self.level[v] self.level[u] 1:pushed self.dfs(v, t, min(f, cap))if pushed 0:self.graph[u][i][1] - pushedself.graph[v][rev][1] pushedreturn pushedself.ptr[u] 1return 0def max_flow(self, s, t):计算最大流flow 0while self.bfs(s, t):self.ptr [0] * self.nwhile True:pushed self.dfs(s, t, float(inf))if pushed 0:breakflow pushedreturn flow# 使用示例二分图匹配# 节点编号源点0, 左边1-3, 右边4-6, 汇点7dinic Dinic(8)# 源点到左边dinic.add_edge(0, 1, 1) # 源点→甲dinic.add_edge(0, 2, 1) # 源点→乙dinic.add_edge(0, 3, 1) # 源点→丙# 左边到右边dinic.add_edge(1, 4, 1) # 甲→Adinic.add_edge(1, 5, 1) # 甲→Bdinic.add_edge(2, 5, 1) # 乙→Bdinic.add_edge(2, 6, 1) # 乙→Cdinic.add_edge(3, 6, 1) # 丙→C# 右边到汇点dinic.add_edge(4, 7, 1) # A→汇点dinic.add_edge(5, 7, 1) # B→汇点dinic.add_edge(6, 7, 1) # C→汇点print(f最大流: {dinic.max_flow(0, 7)}) # 输出: 3霍尔条件检查Pythonfrom itertools import combinationsdef check_hall_condition(graph, n_left, n_right):检查二分图是否满足霍尔条件graph: 邻接表graph[u] [v1, v2, ...] 表示左边节点u连接的右边节点# 检查所有非空子集for size in range(1, n_left 1):for subset in combinations(range(n_left), size):# 计算邻居集合neighbors set()for u in subset:neighbors.update(graph[u])# 检查霍尔条件if len(neighbors) size:return False, subset, neighborsreturn True, None, None# 使用示例graph {0: [0, 1], # 甲→A,B1: [1, 2], # 乙→B,C2: [2] # 丙→C}result, subset, neighbors check_hall_condition(graph, 3, 3)if result:print(满足霍尔条件存在完美匹配)else:print(f不满足霍尔条件子集{subset}的邻居{neighbors}不足)可视化演示二分图匹配过程初始状态甲 ─── A│ ╲│ ╲乙 ─── B│ ╲│ ╲丙 ─── C匹配过程甲→A匹配1乙→B匹配2丙→C匹配3最终状态甲 ═══ A (匹配)│乙 ═══ B (匹配)│丙 ═══ C (匹配)最大流过程流网络构建源点 ──┬── 甲 ──┬── A ──┬── 汇点│ │ │├── 乙 ─┼── B ──┤│ │ │└── 丙 ─┴── C ──┘流量变化初始所有边流量为0路径1源点→甲→A→汇点流量1路径2源点→乙→B→汇点流量1路径3源点→丙→C→汇点流量1无更多增广路径最大流3残余网络变化初始残余网络源点 →甲 (容量1, 流量0)甲 →A (容量1, 流量0)A →汇点 (容量1, 流量0)发送1单位流量后源点 →甲 (容量0, 流量1) ← 正向边饱和甲 →源点 (容量1, 流量0) ← 反向边可撤销甲 →A (容量0, 流量1)A →甲 (容量1, 流量0)A →汇点 (容量0, 流量1)汇点 →A (容量1, 流量0)推荐演示工具在线可视化VisuAlgo (https://visualgo.net/)支持最大流算法可视化Graph Online (https://graphonline.ru/)可绘制二分图本地工具Graphviz绘制图结构Matplotlib NetworkXPython绘图总结一句话记住霍尔定理是裁判只看能不能配对最大流是选手不仅能判断还能实际完成配对而且效率高。实际用的时候永远用最大流不用霍尔定理枚举。入门建议先搞懂二分图完美匹配的概念再看例子里的水流模拟理解最大流的路径怎么来霍尔定理只要记住∣()∣≥∣∣∣N(S)∣≥∣S∣这个核心条件不用死记公式和证明重点是理解和最大流的关联。复杂度对比问题算法时间复杂度适用规模完美匹配存在性霍尔定理枚举(2)O(2n)n ≤≤ 20最大匹配匈牙利算法(3)O(V3)V ≤≤ 1000最大匹配Hopcroft-Karp()O(EV​)V ≤≤ 10⁵最大流Dinic(2)O(V2E)V ≤≤ 10⁴最大权匹配KM算法(3)O(V3)V ≤≤ 500