支配集
支配集(控制集)
是 支配集： - 极小支配集：任何真子集都不是支配集
- 最小支配集：顶点数最小
- 支配数
：最小支配集的势
支配集与匹配
- 从完美匹配中的每条边任取一个端点构成一个支配集
- 从最大匹配中的每条边中存在一个端点的取法构成支配集
支配集和其补集
- 无孤立顶点的图
中，存在支配集 和 - 无孤立顶点的图
中，极小支配集 的补集 是支配集 - 无孤立顶点的图
中，对任意一个极小支配集 ，必存在另一个极小支配集 ，使得 是支配集且 在 的子集中取极小可得
极小支配集的充要条件
图
支配数的估计
- 无孤立顶点的图
满足
求最小支配集的算法
- 和集合覆盖问题可以相互转化：NP-hard
- 贪心算法：每次迭代总选能支配最多剩余顶点的那个顶点，近似比
- 不存在近似比好于对数的多项式时间算法（除非P=NP），即贪心已经足够好了
支配集的应用
- 奇次支配集：Lights Out
- 最小连通支配集：自组网络中的虚拟骨干网
点独立集
点独立集
是 的点独立集： - 极大点独立集：顶点数极多（不是任何一个点独立集的真子集）
- 最大点独立集：顶点数最多
- 独立数
：最大点独立集的势
点独立集与支配集
- 极大点独立集必然是最小支配集
- 若
是点独立集，则它是极大点独立集当且仅当它是支配集
点独立集与连通度
- 设
，若图 中任意两个不相邻顶点 均有 ，则 - 设
是 阶简单图 。若 ，则
求最大独立集的算法
- 最大独立集即补图中最大团：NP-hard
- 不存在近似比显著好于线性的多项式时间算法（除非P=NP）
独立集的应用
最大带权独立集：图像分割
- 顶点：所有可能的块
- 边：重叠的块
- 权：块的显著程度
点覆盖集
点覆盖集
是 的点覆盖集： - 极小点覆盖集：顶点数极少（任何一个真子集都不是点覆盖集）
- 最小点覆盖集：顶点数最少
- 点覆盖数
：最小点覆盖集的势
点覆盖集与支配集
- 点覆盖集与所有边关联
- 支配集与所有剩余点相邻
- 连通图中点覆盖集一定是支配集，但支配集不一定是点覆盖集
点覆盖集与独立集
是点覆盖集当且仅当 是点独立集 是极小点覆盖集当且仅当 是极大点独立集
求最小点覆盖集的算法
点覆盖集和极大匹配的关系
- 极大匹配饱和的所有顶点构成一个点覆盖集
- 近似比2
- 找极大匹配即可
- 不存在近似比好于1.3606的多项式时间算法（除非P=NP）
- 目前还没有找到近似比显著小于2的多项式时间算法：基于极大匹配的算法还不错
