边独立集
边独立集
- 边独立集（匹配）：两两不相邻的边
- 极大边独立集（极大匹配）：不是任何边独立集的真子集
- 最大边独立集（最大匹配）：边数最多
- 边独立数
：最大边独立集的势
边独立集与点覆盖集
- 对任何无环边的图
， - 二部图
有饱和 的匹配当且仅当 - 二部图
，
求最小点覆盖的算法
- 一般图：不存在近似比好于1.3606的多项式时间算法（除非P=NP）
- 二部图：存在精确的多项式时间算法
二部图最小点覆盖算法细节
- 求最大匹配
- 未饱和顶点作为第0层
- 根据交错路的距离对其他顶点分层
- 每条边都有一个端点在奇层
- 奇层顶点恰根据匹配中一条边引出一个新的偶层顶点
边独立数的估计
设图
边覆盖集
边覆盖集
是 （ 无孤立点即 ）的边覆盖集： - 极小边覆盖集：任何一个真子集都不再是边覆盖集
- 最小边覆盖集：边数最少
- 边覆盖数
：最小边覆盖集的势
边覆盖集与边独立集
- 若
，则 - 设
，则 ，等号成立当且仅当 有完美匹配
边覆盖集与点独立集
- 设
是二部图且 ，则
边覆盖数的估计
设
无孤立点图中更一般的关系
- 边独立集小于等于边覆盖集，当边独立集为完美匹配，边覆盖集为最小时取等号
- 边独立集小于等于点覆盖集，当边独立集为最大匹配，点覆盖集为最小时取等号
- 点独立集小于等于边覆盖集，当点独立集为最大，边覆盖集为最小时取等号
求最小边覆盖集的算法
- 原理是
- 最大匹配
- 每个未饱和点任取一边
关系小节
求解算法小节
- 最小支配集：近似算法，贪心
- 最大点独立集：最小点覆盖集的补集
- 最小点覆盖集：一般图用近似算法，基于极大匹配；二部图基于最大匹配
- 最大边独立集：即最大匹配求解算法，一般图用Edmonds，二部图用Hopcroft-Karp
- 最小边覆盖集：基于最大匹配
