点支配集
- 支配：任意 V-V* 中的顶点，都有存在 V* 中的顶点和它通过边相连通
- 点支配集：V-V* 中的每个顶点都是 V* 中某个顶点的邻接顶点
- 极小配集：点支配集 V* 任何真子集都不是点支配集
- 最小支配集：顶点数最小的支配集
- 点支配数：最小支配集中的顶点个数
点覆盖集
- 覆盖：任何一条边，都能在 V* 中的找到至少一个顶点
- 点覆盖集：覆盖所有边的点集
- 极小点覆盖集：点覆盖集 V* 的任何真子集都不是点覆盖集
- 最小点覆盖集：顶点最小的点覆盖集
- 点覆盖数：最小点覆盖中的顶点个数
点独立集
- 点独立集：V* 中任何两个顶点均不相邻
- 极大点独立集：V* 中加入任何点都不在时独立集
- 最大点独立集：顶点数最多的点独立集
- 点独立数：最大点独立集中的顶点个数
边覆盖集
- 边覆盖集：任意顶点都有边在 E* 中
- 极小边覆盖：边覆盖集 E* 中任何真子集都不是边覆盖集
- 最小边覆盖：边数最小
- 边覆盖数：最小的边覆盖中边数
边独立集（匹配）
- 边独立集： E* 中任何两条边都不相邻
- 极大匹配：E* 中加入任何一条边都不再是边独立集
- 最大匹配：边数最多
- 边独立数：最大匹配中的边数
版权声明：本文为博主原创文章，未经博主允许不得转载。http://xiang578.top/