计算机与数字工程
計算機與數字工程
계산궤여수자공정
COMPUTER & DIGITAL ENGINEERING
2013年
5期
686-689
,共4页
(3,4=)-CNF公式%因子图%(3,4)-双向正则二部图%可满足问题
(3,4=)-CNF公式%因子圖%(3,4)-雙嚮正則二部圖%可滿足問題
(3,4=)-CNF공식%인자도%(3,4)-쌍향정칙이부도%가만족문제
合取范式(CNF)公式F是(3,4=)-CNF公式,如果F中每个子句的长度是3,每个变元出现的次数恰好为4次.与(3,4=)-CNF公式所关联的因子图是一类规则的二部图,即每个子句结点的度为3,每个变元结点的度为4,此类规则图被称为(3,4)-双向正则二部图.对于一个(3,4=)-CNF公式F,如果它关联的因子图GF有P7路径因子,则F可满足.
閤取範式(CNF)公式F是(3,4=)-CNF公式,如果F中每箇子句的長度是3,每箇變元齣現的次數恰好為4次.與(3,4=)-CNF公式所關聯的因子圖是一類規則的二部圖,即每箇子句結點的度為3,每箇變元結點的度為4,此類規則圖被稱為(3,4)-雙嚮正則二部圖.對于一箇(3,4=)-CNF公式F,如果它關聯的因子圖GF有P7路徑因子,則F可滿足.
합취범식(CNF)공식F시(3,4=)-CNF공식,여과F중매개자구적장도시3,매개변원출현적차수흡호위4차.여(3,4=)-CNF공식소관련적인자도시일류규칙적이부도,즉매개자구결점적도위3,매개변원결점적도위4,차류규칙도피칭위(3,4)-쌍향정칙이부도.대우일개(3,4=)-CNF공식F,여과타관련적인자도GF유P7로경인자,칙F가만족.
