二分图应用场景

dw_dz · 2025-07-12 20:42:49 · 算法·理论

二分图在信息学奥林匹克竞赛（信奥）中的应用主要集中在关系建模、冲突规避与最优分配三大方向，以下是其核心用途及典型题型分类：

一、基础判定：二分图染色法

通过DFS/BFS对图进行二着色，判断是否满足二分图性质（无奇环），是信奥基础考点：

1. 社交网络分组
   用户分为敌对两群组，若关系图可二染色则存在可行方案（如Luogu P1525 关押罪犯）。
2. 课程冲突检测
   学生选课若存在时间重叠则连边，可染色法判断能否无冲突排课。

⚔️ 二、匹配优化：匈牙利算法

求解二分图最大匹配，解决两类对象间的最优配对问题：

1. 任务分配
   人员与任务匹配（如人员技能满足任务要求），最大化匹配数。
2. 棋盘覆盖
   M×N棋盘用1×2骨牌覆盖（黑白染色后行列二分图匹配）。

🔍 三、二分答案+二分图验证

将最值问题转化为判定问题，结合二分答案与图论验证：

1. 最小化最大冲突值
   （如关押罪犯）二分仇恨值阈值mid，建图（>mid的边连接囚犯）后用染色法判断能否二分图划分。
2. 资源调度优化
   服务器分配任务时延上限mid，检验任务-服务器二分图是否存在满足时延约束的匹配。

四、二分图模型扩展

特殊问题转化为二分图特性求解：

1. 最小点覆盖
   监控问题（选最少的点覆盖所有边）→ König定理：最小点覆盖 = 最大匹配数。
2. 最大独立集
   互不攻击的棋子布局 → 最大独立集 = 总点数 - 最小点覆盖。

💡 信奥题型速查表

✅ 备考要点

1. 染色法模板：需熟练写出非递归BFS染色代码，注意处理非连通图。
2. 匈牙利优化：掌握邻接表存图与递归匹配实现，复杂度O(VE)。
3. 逆向思维：当直接建模困难时，尝试将边权/冲突转化为二分图判定条件。

二分图的核心价值在于 将复杂关系约束转化为两类集合的交互，掌握染色法与匈牙利算法即可解决信奥中90%的二分图题型。