图论讲义121
需积分: 0 23 浏览量
2022-08-03
22:41:41
上传
评论
收藏 489KB PDF 举报
第八章 独立集和团
§8.1 独立集
独立集：设 S 是 V 的一个子集，若 S 中任意两个顶点在 G 中均不相
邻，则称 S 为 G 的一个独立集。
最大独立集：G 的一个独立集 S 称为 G 的最大独立集，是说：G 不
包含适合
的独立集 。
例子：(见图 8.1)
覆盖：G 的一个覆盖是指 V 的子集 K，使得 G 的每条边都至少有一
个端点属于 K。
例子：在图 8.1 中，两个独立集都是覆盖的补集。
定理 8.1：设 ，则 S 是 G 的独立集当且仅当是 G 的覆盖。
证：按定义，S 是 G 的独立集当且仅当 G 中每条边的两个端点都不同
时属于 S，即当且仅当 G 的每条边至少有一个端点属于，亦即当
且仅当是 G 的覆盖。
独立数：G 的最大独立集的顶点数称为 G 的独立数，记为。
覆盖数：G 的最小覆盖的顶点数称为 G 的覆盖数，记为。
推论 8.1： 。
证：设 S 是 G 的一个最大独立集，K 是 G 的一个最小覆盖。由定理
8.1，是独立集，而是覆盖。因此
评论0