支配集、独立集、覆盖集

1. 定义

1.1 支配集

  • 设无向简单图 G=<V,E>,VV G = \lt V,E \gt, V^* \subseteq V ,若 viVV,vjV \forall v_i \in V - V^*, \exists v_j \in V^* 使得 (vi,Vj)E(v_i,V_j) \in E,则称 VV^*GG 的一个支配集,并称 vjv_j 支配 viv_i

  • VV*GG 的支配集,且 VV* 的任何真子集都不是支配集,则称 VV*极小支配集

  • GG 的顶点最少的支配集称作 GG最小支配集

  • 最小支配集中的顶点个数称作 GG支配数,记作 γ0(G)\gamma_0(G),简记为 γ0\gamma_0

1.2 独立集

1.2.1 点独立集

  • 设无向简单图 G=<V,E>,VV G = \lt V,E \gt, V^* \subseteq V ,若 VV* 中任何两个顶点均不相邻,则称 VV*GG点独立集,简称独立集

  • VV* 中再加入任何其他的顶点都不是独立集,则称 VV*极大点独立集

  • GG 的顶点数最多的点独立集称作 GG最大点独立集

  • 最大独立集的顶点数称作 GG点独立数,记作 β0(G)\beta_0(G),简记为 β0\beta_0

1.2.2 边独立集

  • 设无向简单图 G=<V,E>,VV G = \lt V,E \gt, V^* \subseteq V ,若 EE^* 中任何两条边均不相邻,则称 EE^*GG边独立集,也称作 GG匹配

  • 若在 *GG^* 中再加任意一条边后,所得集合都不是匹配,则称 EE^*极大匹配

  • GG 的边数最多的匹配称作最大匹配

  • 最大匹配中的边数称作边独立数匹配数,记作 β1(G)\beta_1(G),简记为 β1\beta_1

  • MM 为图 G=<V,E> G = \lt V,E \gt 的一个匹配:

  1. MM 中的边为匹配边,不在 MM 中的边为非匹配边
  2. 与匹配边相关联的顶点为饱和点,不与匹配边相关联的顶点为非饱和点
  3. GG 中每个顶点都是饱和点,则称 MMGG完美匹配
  4. GG 中由匹配边和非匹配边交替构成的路径称作交错路径,起点和重点都是非饱和点的交错路径称作可增广的交错路径
  5. GG 中由匹配边和非匹配边交替构成的圈称作交错圈
  • G=<V1,V2,E> G = \lt V_1,V_2,E \gt 为二部图,V1V2 |V_1| \leq |V_2| MMGG 的一个匹配且 M=V1 |M| = |V_1| ,称 MMV1V_1V2V_2完备匹配

1.3 覆盖集

1.3.1 点覆盖集

  • 设无向简单图 G=<V,E>,VV G = \lt V,E \gt, V^* \subseteq V ,若 eE,vV \forall e \in E, \exists v \in V^* 使得 vvee 相关联,则称 VV^*GG点覆盖集,简称为点覆盖,并称 vv 覆盖 ee

  • VV^*GG 的点覆盖,若 VV^* 的任何真子集都不是点覆盖,则称 VV^*极小点覆盖

  • GG 的顶点个数最少的点覆盖称为 GG最小点覆盖

  • 最小点覆盖中的顶点个数称作 GG点覆盖数,记作 α0(G)\alpha_0(G),简记为 α0\alpha_0

1.3.2 边覆盖集

  • 设无向简单图 G=<V,E> G = \lt V,E \gt 没有孤立点,EEE^* \subseteq E,若 vV,eE \forall v \in V, \exists e \in E^* 使得 vvee 相关联,则称 EE^*边覆盖集,简称为边覆盖,并称 ee 覆盖 vv

  • EE^* 为边覆盖,若 EE^* 的任何真子集都不是边覆盖集,则称 EE^*极小边覆盖集

  • GG 的边数最少的边覆盖称为 GG最小边覆盖

  • 最小边覆盖中的边数称作 GG边覆盖数,记作 α1(G)\alpha_1(G),简记为 α1\alpha_1

2. 性质

  • 无向简单图的极大点独立集都是极小支配集。

  • 设无向简单图 G=<V,E>,VV G = \lt V,E \gt, V^* \subseteq V ,则 VV^*GG 的点覆盖集当且仅当 V=VV \overline{V^*} = V - V^* GG 的点独立集。

推论

α0+β0=V{\begin{array}{c} \alpha_0 + \beta_0 = |V| \end{array}}

  • nn 阶图 GG 中无孤立点:
  1. MMGG 的一个最大匹配,对 GG 中每个非饱和点均取一条与其关联的边,组成边集 NN,则 W=MN W = M \cup N GG 的最小边覆盖。
  2. W1W_1GG 的一个最小边覆盖,若 W1W_1 中存在相邻的边就移去其中的一条,设移去的边集为 N1N_1,则 M1=W1N1 M_1 = W_1 - N_1 GG 的最大匹配。
  3. GG 的边覆盖数 α1\alpha_1 与匹配数 β1\beta_1 满足:α1+β1=n \alpha_1 + \beta_1 = n

推论

设图 GG 无孤立点,MMGG 的一个匹配,WWGG 的一个边覆盖,则 MW|M| \leq |W|,且当等号成立时,MMGG 的完美匹配,WWGG 的最小边覆盖。

  • 二部图 G=<V1,V2,E> G = \lt V_1,V_2,E \gt 的完备匹配是最大匹配,但最大匹配不一定是完备匹配。当 V1=V2 |V_1| = |V_2| 时,完备匹配是完美匹配。

  • (相异性条件):设二部图 G=<V1,V2,E> G = \lt V_1,V_2,E \gt ,其中 V1V2 |V_1| \leq |V_2| ,则 GG 中存在 V1V_1V2V_2 的完备匹配当且仅当 V1V_1 中任意 k(k=1,2,,V1)k(k = 1,2,\cdots,|V_1|) 个顶点至少与 V2V_2 中的 kk 个顶点相邻。

  • (t 条件):设二部图 G=<V1,V2,E> G = \lt V_1,V_2,E \gt ,如果存在正整数 tt,使得 V1V_1 中每个顶点至少关联 tt 条边,而 V2V_2 中每个顶点至多关联 tt 条边,则 GG 中存在 V1V_1V2V_2 的完备匹配。


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!