

图论杂项

支配集

设无向图 ，若对任意的 ，都存在 ，使得 ，则称 支配 ，并称 为 的一个支配集。最小支配集的顶点个数记为

独立集

点独立集

设无向图 ，若 中任意两个顶点均不相邻，则称 为 的点独立集，或称独立集。最大点独立集的顶点个数记做

若 中无孤立点， 为 中极大独立集，则 为极小独立集。

匹配

设无向图 ，若 中任意两个边均不相邻，则称 为 的边独立集，或称匹配。最大匹配的边数记做

设 为两个不同的匹配，则 的每个连通分支为 中的边组成的交错圈或交错路径。

相关定义

设 为图 的匹配：

饱和点：匹配 中边关联的点

完美匹配：每个顶点都是 饱和点

增广路：在 和 中交替取边的交错路径，且起点和终点都是 非饱和点

托特定理

阶无向图 有完美匹配当且仅当对于任意的 ， ，其中 表示奇数阶连通分支数。

推论：任何无桥 3 - 正则图都有完美匹配。

覆盖集

点覆盖

设无向图 ，若对于任意的 ，都存在 ，使得 与 相关联，则称 覆盖 ，称 为 中点覆盖集。最小点覆盖集的元素个数记为

点覆盖集必为支配集，但极小点覆盖集不一定是极小支配集。

若 为点覆盖集，则 为点独立集。

边覆盖

设无向图 ，若对于任意的 ，都存在 ，使得 与 相关联，则称 覆盖 ，称 为 中边覆盖集。最小边覆盖集的元素个数记为

边覆盖与匹配的关系：

1. 对于一个最大匹配 ，对其每个非饱和点取一条关联的边组成的边集 ，则 为一个最小边覆盖集。（ ）
2. 对于一个最小边覆盖集 ，若 中存在相邻的边就移去其中的一条边，继续这一过程，直到无相邻边，设移去的边集合为 ，则 为一个最大匹配。
4. 对图 ， 为一个匹配， 为一个边覆盖，则 。等号成立时分别为完美匹配和最小边覆盖。

对图 ， 为一个匹配， 为一个边覆盖， 为一个点覆盖， 为一个点独立集，则：

推论：

对于完全二部图 ，有：

团

设无向图 ，若导出子图 是完全图，则称 为团。最大团的顶点个数称为团数，记做

为 的团当且仅当 为 的独立集。

推论：

Note

到目前为止，求图中的极小（最小）支配集、极小（最小）点覆盖、极大（最大）独立集和极大（最大）团还没有找到有效的多项式时间算法。

---

build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论