

图论杂项

支配集¶

设无向图 $G=<V,E>, V^*\subset V$ ，若对任意的 $v_i \in V-V^*$ ，都存在 $v_j \in V^*$ ，使得 $(v_i, v_j) \in E$ ，则称 $v_j$ 支配 $v_i$ ，并称 $V^*$ 为 $G$ 的一个支配集。最小支配集的顶点个数记为 $\gamma_0$

独立集¶

点独立集¶

设无向图 $G=<V,E>, V^*\subset V$ ，若 $V^*$ 中任意两个顶点均不相邻，则称 $V^*$ 为 $G$ 的点独立集，或称独立集。最大点独立集的顶点个数记做 $\beta_0$

若 $G$ 中无孤立点， $V^*$ 为 $G$ 中极大独立集，则 $V^*$ 为极小独立集。

匹配¶

设无向图 $G=<V,E>, E^*\subset E$ ，若 $E^*$ 中任意两个边均不相邻，则称 $E^*$ 为 $G$ 的边独立集，或称匹配。最大匹配的边数记做 $\beta_1$

设 $M_1, M_2$ 为两个不同的匹配，则 $G[M_1 \oplus M_2]$ 的每个连通分支为 $M_1, M_2$ 中的边组成的交错圈或交错路径。

托特定理¶

$n$ 阶无向图 $G$ 有完美匹配当且仅当对于任意的 $V' \subset V(G)$ ， $p_{奇}(G-V')\leq |V'|$ ，其中 $p_{奇}$ 表示奇数阶连通分支数。

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

覆盖集¶

点覆盖¶

设无向图 $G=<V,E>, V^*\subset V$ ，若对于任意的 $e \in E$ ，都存在 $v \in V^*$ ，使得 $v$ 与 $e$ 相关联，则称 $v$ 覆盖 $e$ ，称 $V^*$ 为 $G$ 中点覆盖集。最小点覆盖集的元素个数记为 $\alpha_0$

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

若 $V^*$ 为点覆盖集，则 $V-V^*$ 为点独立集。

边覆盖¶

设无向图 $G=<V,E>, E^*\subset E$ ，若对于任意的 $v \in V$ ，都存在 $e \in E^*$ ，使得 $v$ 与 $e$ 相关联，则称 $e$ 覆盖 $v$ ，称 $E^*$ 为 $G$ 中边覆盖集。最小边覆盖集的元素个数记为 $\alpha_1$

边覆盖与匹配的关系：

对于一个最大匹配 $M$ ，对其每个非饱和点取一条关联的边组成的边集 $N$ ，则 $W=M \cup N$ 为一个最小边覆盖集。（ $\beta_1 \leq \alpha_1$ ）
对于一个最小边覆盖集 $W_1$ ，若 $W_1$ 中存在相邻的边就移去其中的一条边，继续这一过程，直到无相邻边，设移去的边集合为 $N_1$ ，则 $M_1=W_1-N_1$ 为一个最大匹配。
$\alpha_1 + \beta_1 = n$
对图 $G$ ， $M$ 为一个匹配， $W$ 为一个边覆盖，则 $|M| \leq |W|$ 。等号成立时分别为完美匹配和最小边覆盖。

对图 $G$ ， $M$ 为一个匹配， $W$ 为一个边覆盖， $N$ 为一个点覆盖， $Y$ 为一个点独立集，则：

$|M| \leq |N|$
$|Y| \leq |W|$

推论： $\beta_1 \leq \alpha_0, \beta_0 \leq \alpha_1$

对于完全二部图 $K_{r,s}$ ，有： $\alpha_0=\min\{r,s\}=\beta_1, \beta_0=\max\{r,s\}=\alpha_1$

团¶

设无向图 $G=<V,E>, V^*\subset V$ ，若导出子图 $G[V^*]$ 是完全图，则称 $V^*$ 为团。最大团的顶点个数称为团数，记做 $\nu_0$

$V^*$ 为 $G$ 的团当且仅当 $V^*$ 为 $\bar{G}$ 的独立集。

推论： $\nu_0(G) = \beta_0(\bar{G})$

Note

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

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