84独立集,覆盖 1点覆盖和独立集 定义8.15:设无自环图G=(V,E若V的 个子集I中任意两个顶点在G中都不相邻, 则称是G的一个独立集。若G中不含有 满足的独立集',则称I为G的最大 独立集。它的顶点数称为G的独立数,记 为β(G) 对于无自环的图,单点是独立集8.4独立集, 覆盖 1.点覆盖和独立集 定义 8.15:设无自环图G=(V,E),若V的一 个子集I中任意两个顶点在G中都不相邻, 则称I是G的一个独立集。若G中不含有 满足|I'|>|I|的独立集I', 则称I为G的最大 独立集。它的顶点数称为G的独立数, 记 为0 (G)。 对于无自环的图,单点是独立集