第五章独立集与匹配
第五章 独立集与匹配
独立集、支配集、覆盖集、匹配
独立集、支配集、覆盖集、匹配
独立集 >设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>是简单图无向图, SV, S, 若S 中任何两个顶点都不相邻,则称这个顶点集合S 为图G的独立集。 ➢ 若S是图G的独立集，但是任意增加一个顶点 就破坏它的独立性,则称这个独立集S为极大独 立集。 ➢ 独立集S称为最大独立集,如果不存在独立集S’, 使 S’> S ,其中S为集合S的数。 ➢ G的最大独立集S的基数称为G的独立数,记作 (G)。 独立集
说明: (1)简单无向图G的独立集,实际是对图 G的顶点进行着色的结果。把图G的顶点集 V划分成若干不相交的子集,每个子集中的 各结点着同一色。上述不相交的子集的最 少个数即为图G的色数。 (2)图G的极大独立集不是唯一的,最大 独立集也不唯一
说明: （1）简单无向图G的独立集，实际是对图 G的顶点进行着色的结果。把图G的顶点集 V划分成若干不相交的子集，每个子集中的 各结点着同一色。上述不相交的子集的最 少个数即为图G的色数。 （2）图G的极大独立集不是唯一的，最大 独立集也不唯一
(2) 图5.1.1 显然,图G的极大独立集不一定是唯一的,且最大独立集也不一定唯一 例如,图511(1)所示中,{2,8}与{2,47都是G的极大独立集,同时{245,7} 也是G的最大独立集,而{13,68}也是最大独立及集,因而G的独立数 a(G)=4;图511(2)所示中,5},的,,的,号,和{2,V,v6,n3都 是G的独立集,且都是极大独立集,其中{,n,,V}和{2,v4,v,n}都是最大独 立集,a(G)=4