摘要
为了得到将三元可满足性问题(3-Satisfiability problem,3SAT)直接转化为哈密尔顿环(Hamilton cycle)的高效转化方法,该文以长年对哈密尔顿环研究计算所探索出的规律为基础进行研究。通过对各种可能实现转化的图形组合进行全面的比较分析,得出用无向图的两个节点模拟3SAT的一个变量,用无向图的13个节点模拟3SAT的一个子式的方法,实现了3SAT到哈密尔顿环的高效转化。研究结果表明:该转化所需要的节点数及其边数是最优的。
In order to get the most efficient transform from 3-Satisfiability Problem(3SAT)to Hamilton cycle,this paper does this research based on the author ' s long time study and calculation of the Hamilton cycle.With the careful comparison and analysis of all kinds of possible graphs which can do this transform,this paper gets the final method:2 vertices to denote a variable of the 3SAT and 13 vertices to denote a clause of the 3SAT,to realize the high efficient transform from 3SAT to Hamilton cycle.The results show that this method needs the least number of vertices and edges.
出处
《南京理工大学学报》
EI
CAS
CSCD
北大核心
2013年第4期506-510,共5页
Journal of Nanjing University of Science and Technology
