首页
学习
活动
专区
圈层
工具
发布
社区首页 >专栏 >支配集、独立集、覆盖集

支配集、独立集、覆盖集

作者头像
hotarugali
发布于 2022-03-01 21:16:26
发布于 2022-03-01 21:16:26
1.9K0
举报

1. 定义

1.1 支配集

  • 设无向简单图 G = \lt V,E \gt, V^* \subseteq V ,若\forall v_i \in V - V^*, \exists v_j \in V^* 使得 (v_i,V_j) \in E则称 V^*为 G 的一个支配集,并称 v_j支配v_i。
  • 设 V*是 G 的支配集,且 V* 的任何真子集都不是支配集,则称V* 为极小支配集。
  • G 的顶点最少的支配集称作 G的最小支配集。
  • 最小支配集中的顶点个数称作 G 的支配数,记作 \gamma_0(G),简记为 \gamma_0​ 。

1.2 独立集

1.2.1 点独立集
  • 设无向简单图 G = \lt V,E \gt, V^* \subseteq V ,若 V*中任何两个顶点均不相邻,则称 V* 为 G 的点独立集,简称独立集。
  • 若 V* 中再加入任何其他的顶点都不是独立集,则称 V*为极大点独立集。
  • G的顶点数最多的点独立集称作 G的最大点独立集。
  • 最大独立集的顶点数称作 G 的点独立数,记作 \beta_0(G),简记为 \beta_0。
1.2.2 边独立集
  • 设无向简单图 G = \lt V,E \gt, V^* \subseteq V ,若 E^* 中任何两条边均不相邻,则称 E^* 为 G 的边独立集,也称作 G的匹配。
  • 若在 G^* 中再加任意一条边后,所得集合都不是匹配,则称 E^*为极大匹配。
  • G 的边数最多的匹配称作最大匹配。
  • 最大匹配中的边数称作边独立数或匹配数,记作 \beta_1(G),简记为 \beta_1​ 。
  • 设 M为图 G = \lt V,E \gt的一个匹配:
  1. 称 M中的边为匹配边,不在 M中的边为非匹配边。
  2. 与匹配边相关联的顶点为饱和点,不与匹配边相关联的顶点为非饱和点。
  3. 若 G 中每个顶点都是饱和点,则称 M为 G 的完美匹配。
  4. G 中由匹配边和非匹配边交替构成的路径称作交错路径,起点和重点都是非饱和点的交错路径称作可增广的交错路径。
  5. G中由匹配边和非匹配边交替构成的圈称作交错圈。
  • 设 G = \lt V_1,V_2,E \gt 为二部图, |V_1| \leq |V_2| ,M 为 G 的一个匹配且 |M| = |V_1| ,称 M 为 V_1 到 V_2的完备匹配。

1.3 覆盖集

1.3.1 点覆盖集
  • 设无向简单图G = \lt V,E \gt, V^* \subseteq V ,若 \forall e \in E, \exists v \in V^* 使得 v与 e 相关联,则称 V^*为 G 的点覆盖集,简称为点覆盖,并称 v覆盖 e 。
  • 设V^*是 G 的点覆盖,若V^* 的任何真子集都不是点覆盖,则称V^*为极小点覆盖。
  • G 的顶点个数最少的点覆盖称为 G的最小点覆盖。
  • 最小点覆盖中的顶点个数称作 G 的点覆盖数,记作 \alpha_0(G),简记为 \alpha_0 。
1.3.2 边覆盖集
  • 设无向简单图 G = \lt V,E \gt 没有孤立点,E^* \subseteq E,若 \forall v \in V, \exists e \in E^* 使得 v与 e 相关联,则称 E^* 为边覆盖集,简称为边覆盖,并称 e覆盖 v 。
  • 设 E^*为边覆盖,若 E^* 的任何真子集都不是边覆盖集,则称E^*为极小边覆盖集。
  • G 的边数最少的边覆盖称为 G 的最小边覆盖。
  • 最小边覆盖中的边数称作 G 的边覆盖数,记作\alpha_1(G),简记为 \alpha_1​ 。

2. 性质

  • 无向简单图的极大点独立集都是极小支配集。
  • 设无向简单图 G = \lt V,E \gt, V^* \subseteq V ,则V^*为 G 的点覆盖集当且仅当 \overline{V^*} = V - V^* 为 G 的点独立集。

推论

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

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

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

  • 二部图 G = \lt V_1,V_2,E \gt 的完备匹配是最大匹配,但最大匹配不一定是完备匹配。当 |V_1| = |V_2| 时,完备匹配是完美匹配。
  • (相异性条件):设二部图 G = \lt V_1,V_2,E \gt 其中 |V_1| \leq |V_2| ,则 G 中存在 V_1到 V_2​ 的完备匹配当且仅当 V_1​ 中任意 k(k = 1,2,\cdots,|V_1|) 个顶点至少与 V_2 中的 k 个顶点相邻。
  • (t 条件):设二部图 G = \lt V_1,V_2,E \gt 如果存在正整数 t,使得 V_1 中每个顶点至少关联 t 条边,而 V_2 中每个顶点至多关联 t条边,则 G 中存在 V_1​ 到 V_2的完备匹配。
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020-09-01,如有侵权请联系 cloudcommunity@tencent.com 删除
目录
  • 1. 定义
    • 1.1 支配集
    • 1.2 独立集
      • 1.2.1 点独立集
      • 1.2.2 边独立集
    • 1.3 覆盖集
      • 1.3.1 点覆盖集
      • 1.3.2 边覆盖集
  • 2. 性质
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档