第五章独立集与匹配,独立集、支配集、覆盖集、匹配,设G=是简单图无向图,SV,S,若S中任何两个顶点都不相邻,则称这个顶点集合S为图G的独立集。若S是图G的独立集，但是任意增加一个顶点就破坏它的独立性,则称这个独立集S为极大独立集。独立集S称为最大独立集,如果不存在独立集S,使SS,其中S为集合S的数。G的最大独立集S的基数称为G的独立数,记作(G)。,独立集,说明:（1）简单无向图G的独立集，实际是对图G的顶点进行着色的结果。把图G的顶点集V划分成若干不相交的子集，每个子集中的各结点着同一色。上述不相交的子集的最少个数即为图G的色数。（2）图G的极大独立集不是唯一的，最大独立集也不唯一。,基于布尔运算的图G的所有极大独立集的求法：几个约定:已知简单无向图G=,且V=V1,V2,Vn,规定:(1)G的每个顶点Vi当作一个布尔变量;(2)ViVj表示包含Vi和Vj;(3)ViVj表示或者包含一顶点Vi;或者包含一顶点Vj;或者包含Vi和Vj两个顶点。,点覆盖,设G=,V*V,(1)V*是点覆盖(点覆盖集）eE，vV*，使e与v关联；(2
