图论杂项

支配集

设无向图 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 中的边组成的交错圈或交错路径。

相关定义

M 为图 G 的匹配:

M 饱和点:匹配 M 中边关联的点

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

增广路:在 M E(G)-M 中交替取边的交错路径,且起点和终点都是 M 非饱和点

托特定理

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

边覆盖与匹配的关系:

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

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

  1. |M| \leq |N|
  2. |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

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


评论