图论 - 二分图
目录
- 二分图
- 相关资料
- 二分图最大匹配
- 图匹配
- 增广路
- 二分图最大匹配
- 相关资料
- 例题
二分图
二分图 ： 如果无向图 \(G = (V,E)\) 的所有点可以分为两个集合 \(V_1、 V_2\)，所有的边都在 \(V_1\) 和 \(V_2\) 之间，而\(V_1\) 和 \(V_2\) 的内部没有边，称 G 是一个二分图
性质：一个图是二分图当且仅当它没有边为奇数的环 - “奇环”。
可以利用染色法来判断一个图是不是二分图
相关资料
oi wiki - 二分图
dx123 - 二分图判定 染色法
二分图最大匹配
图匹配
在图论中，假设图 \(G = (V,E)\)，其中 V 是点集，E 是边集。
一组两两没有公共点的边集 \((M(M\in E))\) 称为这张图的 匹配。
定义匹配的大小为其中边的数量 |M|，其中边数最大的 M 为 最大匹配。
当图中的边带权的时候，边权和最大的为 最大权匹配。
匹配中的边称为 匹配边，反之称为 未匹配边。
一个点如果属于 M 且为至多一条边的端点，称为 匹配点，反之称为 未匹配点。
- maximal matching：无法再增加匹配边的匹配。不见得是最大匹配。
- 最大匹配（maximum matching）：匹配数最多的匹配。
- 完美匹配（perfect matching）：所有点都属于匹配，同时也符合最大匹配。
增广路
- 交错路（alternating path）始于非匹配点且由匹配边与非匹配边交错而成。
- 增广路（augmenting path）是始于非匹配点且终于非匹配点的交错路。
增广路上非匹配边比匹配边数量多一，如果将匹配边改为未匹配边，反之亦然，则匹配大小会增加一且依然是交错路。
二分图最大匹配
一张二分图上的匹配称作二分匹配
设 G 为二分图，若在 G 的子图 M 中，任意两条边都没有公共节点，那么称 M 为二分图 G 的一个匹配，且 M 的边数为匹配数。
寻找二分图边数最大的匹配称为最大匹配问题。
相关资料
图匹配
增广路
二分图最大匹配