第五章独立集与匹配
第五章 独立集与匹配
独立集、支配集、覆盖集、匹配
独立集、支配集、覆盖集、匹配
独立集 >设G=是简单图无向图,S∈V,S≠若S 中任何两个顶点都不相邻则称这个顶点集合S 为图G的独立集。 >若S是图G的独立集,但是任意增加一个顶点 就破坏它的独立性则称这个独立集S为极大独 立集。 >独立集S称为最大独立集如果不存在独立集S 使|S|>|S|,其中S为集合S的数。 >G的最大独立集S的基数称为G的独立数记作 (G)
➢ 设G=是简单图无向图, 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
基于布尔运算的图G的所有极大独立集的求法 几个约定: 已知简单无向图G=,且V={1,V2,,n}规定: (1)G的每个顶点Ⅴ当作一个布尔变量; (2)V∧Ⅴ表示包含Ⅴ和v (3)VV表示或者包含一顶点Ⅴ;或者包含一顶点v 或者包含Ⅴ和Ⅴ两个页点
基于布尔运算的图G的所有极大独立集的求法： 几个约定: 已知简单无向图G=,且V={V1 ,V2 ,…,Vn },规定: (1)G的每个顶点Vi当作一个布尔变量; (2)ViVj表示包含Vi和Vj ; (3) ViVj表示或者包含一顶点Vi ;或者包含一顶点Vj ; 或者包含Vi和Vj两个顶点
根据以上约定,布尔积∧和布尔和∨有以下几个性质: (1)VAV=VA,VvV=VV(交换) (2)(7∧)AV=A(AF),(VV)VF=Vv)(结合) (3)V∧F=V,VvV=V(等幂) (4)V∧(vH)=(AV)(A7),(AF)=(VT)入(v7)(分配) (5)Vv(AV)=V1,VA(VVV)=V(吸收) (6)(∧V)=VvV,(vV)=V∧V(德摩根律 这些运算性质,都可以通过离散数学中数理逻辑部分的真值表加以证明
说明:V∧V对应在图G中过顶点而,V的边(,V)。作布尔表达式 q=、(VAV),即p中的每一项∧对应于G的一条边,是对所有的边 (V1,V)∈E 求布尔和。由德·摩根律,我们有q=A(VVV)。设=Vg2y…VQ,q (,)∈E 和φ都是含有布尔变量12…Vn的表达式,因G的极大独立集不包含任何一边 的两个端点,故表达式φ在任一极大独立集上取布尔值0(F);反之,使g取值0 的点集是独立集。 即布尔表达式φ取布尔值0是独立集的充要条件,换句话说,使φ取布尔值 l(T)是独立集的充要条件。由于=四2y…V,只要其中任一项为1,则 φ=1。故分别使叭1、q2,…以取布尔值1的点集都是极大独立集
例:通过布尔变量的运算,求下图所示图G的极大独立集。 5 VIG 解:构造布尔函数 P=U,,ADVUADVUAUVU,AUV(U AUAV(UAAUSVUADOVUSAU P=UVU2AULVUSAU VD)AU2 VU4)A U VUAUAVUAQUVUA(UVU
U1VU)∧(U1v (UVU2)(UVD2)AU3 (UAUDVU2AUVUAU3)V(U2AU3 U1V(b∧b1)V(U1∧b2)V(U2∧L U1V(U2∧U (UVDA)A(U2VUA)=04V(0AU2 (USVUAAQUAVUS)=U4VU3AUS (4V)A(Yu)=(4A)