计算机与数字工程
計算機與數字工程
계산궤여수자공정
COMPUTER & DIGITAL ENGINEERING
2015年
5期
766-770,891
,共6页
(3,4)-CNF公式%因子图%(3,4)-双向正则二部图%可满足问题
(3,4)-CNF公式%因子圖%(3,4)-雙嚮正則二部圖%可滿足問題
(3,4)-CNF공식%인자도%(3,4)-쌍향정칙이부도%가만족문제
(3,4)-CNF formula%factor graph%(3,4)-biregular bigraph%satisfiability problem
对于规则的(3,4)-CNF公式F,公式F对应的因子图GF恰好是一个(3,4)-双向正则二部图.利用正则二部图的有关性质,证明了对于任意的(3,4)-CNF公式F,若其对应的因子图GF能够被划分为两个(3,2)-双向正则二部图,则F是可满足的.
對于規則的(3,4)-CNF公式F,公式F對應的因子圖GF恰好是一箇(3,4)-雙嚮正則二部圖.利用正則二部圖的有關性質,證明瞭對于任意的(3,4)-CNF公式F,若其對應的因子圖GF能夠被劃分為兩箇(3,2)-雙嚮正則二部圖,則F是可滿足的.
대우규칙적(3,4)-CNF공식F,공식F대응적인자도GF흡호시일개(3,4)-쌍향정칙이부도.이용정칙이부도적유관성질,증명료대우임의적(3,4)-CNF공식F,약기대응적인자도GF능구피화분위량개(3,2)-쌍향정칙이부도,칙F시가만족적.
