跳转至

图论杂项

支配集

设无向图 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饱和点

增广路:在 ME(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^*,使得 ve相关联,则称 v覆盖 e,称 V^*G中点覆盖集。最小点覆盖集的元素个数记为 \alpha_0

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

V^*为点覆盖集,则 V-V^*为点独立集。

边覆盖

设无向图 G=<V,E>, E^*\subset E,若对于任意的 v \in V,都存在 e \in E^*,使得 ve相关联,则称 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. 对图 GM为一个匹配, W为一个边覆盖,则 |M| \leq |W|。等号成立时分别为完美匹配和最小边覆盖。

对图 GM为一个匹配, 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

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


评论