说明: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的点集都是极大独立集