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

计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (26): 76-78.

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

王伟¹,殷志祥^1,2

1.安徽理工大学数理系,安徽淮南 232001
2.华中科技大学控制科学与工程系,武汉430074

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-09-11 发布日期:2007-09-11
通讯作者: 王伟

Analysis for directed Hamilton path problems based on sticker systems

WANG Wei¹,YIN Zhi-xiang^1,2

1.Department of Math. and Physics,Anhui University of Science & Technology,Huainan,Anhui 232001,China
2.Department of Control Science and Engineering,Huazhong University of Science & Technology,Wuhan 430074,China

Received:1900-01-01 Revised:1900-01-01 Online:2007-09-11 Published:2007-09-11
Contact: WANG Wei

摘要/Abstract

摘要： 通过构造粘贴模型模拟解决有向哈密顿路问题,然后用此粘贴系统所产生语言的性质对有向哈密顿路问题进行分析,继而给出了有向哈密顿路的充要条件。对于规模为n有向哈密顿路问题,构造的粘贴系统至多运行n-1步。

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

Abstract: 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.

Key words: DNA computing, sticker system, directed Hamilton path problem

王伟¹,殷志祥^1,2. 基于粘贴系统的有向哈密顿路问题分析[J]. 计算机工程与应用, 2007, 43(26): 76-78.

WANG Wei¹,YIN Zhi-xiang^1,2. Analysis for directed Hamilton path problems based on sticker systems[J]. Computer Engineering and Applications, 2007, 43(26): 76-78.

[1]	谭莉1，应石2. 多目标优化机制下DNA编码序列模型[J]. 计算机工程与应用, 2016, 52(15): 34-37.
[2]	孙守霞1，刘伟2，郭迎3，孟大志4. DNA计算机算术运算的自装配模型（III）—减法[J]. 计算机工程与应用, 2012, 48(32): 39-42.
[3]	臧文科1，夏瑞芳2，刘希玉1. MSC问题的一类表面DNA解法[J]. 计算机工程与应用, 2012, 48(22): 14-17.
[4]	张勋才，郗方. 微流控DNA计算的研究进展及展望[J]. 计算机工程与应用, 2011, 47(32): 37-41.
[5]	朱越. 基于DNA的连续优化算法[J]. 计算机工程与应用, 2011, 47(22): 48-52.
[6]	栗青生¹，杨玉星¹，马季兰². 基于粘贴模型的两类全排问题的DNA算法[J]. 计算机工程与应用, 2010, 46(4): 46-48.
[7]	刘伟¹，郭迎²，孟大志³. DNA计算机算术运算的自装配模型（I）—加法[J]. 计算机工程与应用, 2010, 46(20): 157-160.
[8]	刘伟¹，郭迎²，孟大志3. DNA计算机算术运算的自装配模型（II）—乘法[J]. 计算机工程与应用, 2010, 46(20): 161-163.
[9]	殷脂^1，2，叶春明¹，温蜜². 最小自由能约束的DNA编码设计研究[J]. 计算机工程与应用, 2010, 46(12): 25-27.
[10]	崔光照¹,秦利敏¹,王延峰¹,张勋才². 基于DNA技术的加密方案[J]. 计算机工程与应用, 2009, 45(8): 104-106.
[11]	羊四清^1,2,李小龙²,袁辉勇¹. 图的最小顶点覆盖问题的DNA表面计算模型[J]. 计算机工程与应用, 2009, 45(6): 69-72.
[12]	李珍,王淑栋. DNA编码限制条件与编码策略[J]. 计算机工程与应用, 2009, 45(5): 43-45.
[13]	李金松,张强,周士华. 双链DNA解链温度的最小二乘支持向量机预测方法[J]. 计算机工程与应用, 2009, 45(5): 55-58.
[14]	周康^1,2,魏传佳¹,程珍²,黄玉芳²,许进². DNA计算模型的研究[J]. 计算机工程与应用, 2009, 45(18): 1-5.
[15]	郑学东¹,许进¹,徐菲². 基于特定模数集的并行DNA算术运算[J]. 计算机工程与应用, 2008, 44(6): 51-54.