基于粘贴系统的有向哈密顿路问题分析  

Analysis for directed Hamilton path problems based on sticker systems

作　　者：王伟[1] 殷志祥[1] 

机构地区：[1]安徽理工大学数理系,安徽淮南232001

出　　处：《计算机工程与应用》2007年第26期76-78,共3页Computer Engineering and Applications

基　　金：国家自然科学基金( the National Natural Science Foundation of China under Grant No60274026; No30570431) ;安徽省优秀青年基金( No06042088) ;安徽省教育厅自然科学重点项目( No2006kj068A) ;安徽省优秀人才基金;中国博士后科学基金( No2004035196) ;新纪人才支持计划资助

摘　　要：通过构造粘贴模型模拟解决有向哈密顿路问题,然后用此粘贴系统所产生语言的性质对有向哈密顿路问题进行分析,继而给出了有向哈密顿路的充要条件。对于规模为n有向哈密顿路问题,构造的粘贴系统至多运行n-1步。Through constructs the sticker model to simulate solves directed Hamilton path problems.Then some properties of directed graphs are presented based on the analysis of directed Hamilton path problems according to the properties of languages generated by the sticker systems.For a size n directed Hamilton path problem,the sticker system which constructs run at most n- 1 steps.

关 键 词：DNA计算 粘贴模型 有向哈密顿路问题 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]