独立集,1. 定义 1.1 支配集 设无向简单图 ，若 使得 ，则称 为 的一个支配集，并称 支配 。 设 是 的支配集，且 的任何真子集都不是支配集，则称 为极小...

详情

1. 定义

1.1 支配集

• 设无向简单图 ，若 使得 ，则称 为 的一个支配集，并称 支配 。

• 设 是 的支配集，且 的任何真子集都不是支配集，则称 为极小支配集。

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

• 最小支配集中的顶点个数称作 的支配数，记作 ，简记为 。

1.2 独立集

1.2.1 点独立集

• 设无向简单图 ，若 中任何两个顶点均不相邻，则称 为 的点独立集，简称独立集。

• 若 中再加入任何其他的顶点都不是独立集，则称 为极大点独立集。

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

• 最大独立集的顶点数称作 的点独立数，记作 ，简记为 。

1.2.2 边独立集

• 设无向简单图 ，若 中任何两条边均不相邻，则称 为 的边独立集，也称作 的匹配。

• 若在 中再加任意一条边后，所得集合都不是匹配，则称 为极大匹配*。

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

• 最大匹配中的边数称作边独立数或匹配数，记作 ，简记为 。

• 设 为图 的一个匹配：

1. 称 中的边为匹配边，不在 中的边为非匹配边。
2. 与匹配边相关联的顶点为饱和点，不与匹配边相关联的顶点为非饱和点。
3. 若 中每个顶点都是饱和点，则称 为 的完美匹配。
4. 中由匹配边和非匹配边交替构成的路径称作交错路径，起点和重点都是非饱和点的交错路径称作可增广的交错路径。
5. 中由匹配边和非匹配边交替构成的圈称作交错圈。

• 设 为二部图，， 为 的一个匹配且 ，称 为 到 的完备匹配。

1.3 覆盖集

1.3.1 点覆盖集

• 设无向简单图 ，若 使得 与 相关联，则称 为 的点覆盖集，简称为点覆盖，并称 覆盖 。

• 设 是 的点覆盖，若 的任何真子集都不是点覆盖，则称 为极小点覆盖。

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

• 最小点覆盖中的顶点个数称作 的点覆盖数，记作 ，简记为 。

1.3.2 边覆盖集

• 设无向简单图 没有孤立点，，若 使得 与 相关联，则称 为边覆盖集，简称为边覆盖，并称 覆盖 。

• 设 为边覆盖，若 的任何真子集都不是边覆盖集，则称 为极小边覆盖集。

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

• 最小边覆盖中的边数称作 的边覆盖数，记作 ，简记为 。

2. 性质

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

• 设无向简单图 ，则 为 的点覆盖集当且仅当 为 的点独立集。

推论

• 设 阶图 中无孤立点：

1. 设 为 的一个最大匹配，对 中每个非饱和点均取一条与其关联的边，组成边集 ，则 为 的最小边覆盖。
2. 设 为 的一个最小边覆盖，若 中存在相邻的边就移去其中的一条，设移去的边集为 ，则 为 的最大匹配。
3. 的边覆盖数 与匹配数 满足： 。

推论

设图 无孤立点， 是 的一个匹配， 是 的一个边覆盖，则 ，且当等号成立时， 是 的完美匹配， 是 的最小边覆盖。

• 二部图 的完备匹配是最大匹配，但最大匹配不一定是完备匹配。当 时，完备匹配是完美匹配。

• (相异性条件)：设二部图 ，其中 ，则 中存在 到 的完备匹配当且仅当 中任意 个顶点至少与 中的 个顶点相邻。

• (t 条件)：设二部图 ，如果存在正整数 ，使得 中每个顶点至少关联 条边，而 中每个顶点至多关联 条边，则 中存在 到 的完备匹配。

您还可以搜索:支配集,覆盖集,独立集,与匹配,支配集 覆盖集,支配集和独立集的区别,支配集是什么,支配集问题,支配集和连通支配集,独立集和点覆盖规约证明,支配集npc,支集的定义,点覆盖和独立集④

独立集