独立集 >设G=<V,E>是简单图无向图,S∈V,S≠若S 中任何两个顶点都不相邻则称这个顶点集合S 为图G的独立集。 >若S是图G的独立集,但是任意增加一个顶点 就破坏它的独立性则称这个独立集S为极大独 立集。 >独立集S称为最大独立集如果不存在独立集S 使|S|>|S|,其中S为集合S的数。 >G的最大独立集S的基数称为G的独立数记作 (G)➢ 设G=<V,E>是简单图无向图, SV, S, 若S 中任何两个顶点都不相邻,则称这个顶点集合S 为图G的独立集。 ➢ 若S是图G的独立集，但是任意增加一个顶点 就破坏它的独立性,则称这个独立集S为极大独 立集。 ➢ 独立集S称为最大独立集,如果不存在独立集S’, 使 S’> S ,其中S为集合S的数。 ➢ G的最大独立集S的基数称为G的独立数,记作 (G)。 独立集