基于布尔运算的图G的所有极大独立集的求法 几个约定: 已知简单无向图G=<V,E>,且V={1,V2,,n}规定: (1)G的每个顶点Ⅴ当作一个布尔变量; (2)V∧Ⅴ表示包含Ⅴ和v (3)VV表示或者包含一顶点Ⅴ;或者包含一顶点v 或者包含Ⅴ和Ⅴ两个页点
基于布尔运算的图G的所有极大独立集的求法： 几个约定: 已知简单无向图G=<V,E>,且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)