匹配
- 匹配：M是G的匹配：G中两两不相邻边构成的集合
- 被饱和的顶点：M中边的端点被M饱和
完美匹配
- 所有顶点都被饱和的匹配
- 阶是偶数
- 包含阶数的一半的边数
包含 个不重的完美匹配
最大匹配
- 极大匹配：势极大的匹配，不是任何匹配的真子集
- 最大匹配：势最大的匹配
匹配的增光路
- M交错路：边交替属于
和 的路 - M增广路：起点和终点未被
饱和的 交错路
最大匹配的充要条件
图
奇分支
- 阶为奇数的连通分支
- 图G的奇分支的数量记作
- 向图中增加边不会增加奇分支的数量
完美匹配的充要条件
图
因子
-因子：图 的 -正则生成子图 -因子：完美匹配 - 可
-因子分解的：图G有一组 -因子的边集构成 的一个划分 是可 -因子分解的 , 是可 -因子分解的
