摘要：该文基于DNA折纸术,设计了一个通过DNA折纸结构的自组装求解图的顶点着色问题的方法。利用DNA折纸术可以构建出具有特定形状的DNA折纸结构。这些结构可以用来编码图的顶点和边,由于这些结构具有粘性末端,因此可以通过特异的分子杂交组装成为代表了不同的图的顶点着色方案的高级结构。利用DNA-纳米颗粒共聚体的属性和电泳等实验方法,可以筛选出正确的符合条件的图的顶点着色方案。该方法是一种高度并行的方法,可以极大地降低求解图的顶点着色问题的复杂度。

摘要：图的顶点着色问题是指无向图中任意两个相邻顶点都分配到不同的颜色 ,这个问题是著名的NP 完全问题 ,没有非常有效的算法 .但在 1994年Adleman[1] 首次提出用DNA计算解决NP 完全问题 ,设计出一种全新的计算模式—模拟生物分子DNA的结构并借助于分子生物技术进行计算 ,使得NP 完全问题的求解可能得到解决 .本文首先提出了基于分子生物技术的图的顶点着色问题的DNA算法 ,算法的关键是对图中的顶点和顶点的颜色进行恰当的编码 ,以便于使用常规的生物操作及生物酶完成解的产生及最终解的分离 ,依据分子生物学的实验方法 ,本文提出的算法是有效和可行的 ;其次指出了该算法的优点。

摘要：自组装纳米颗粒由于其特殊的结构,具有较好的稳定性,广泛应用于DNA计算中,使用DNA自组装模型可以有效减少运算的复杂度。文章利用自组装纳米金属颗粒求解了图的顶点着色问题。首先,将图的顶点进行自组装设计;其次,根据顶点构造相应的连接探针,二者通过碱基互补配对自动生成初始数据池;最后,利用特殊结构的删除探针对数据池中的方案进行筛选,结合凝胶电泳得到满足条件的解。该模型无需对DNA片段进行编码,操作简单,在检测解时无需酶的参与,降低了复杂度,提高了运算效率。

摘要：建立了抗干涉齿轮集(counter-meshing gears,CMG)机构编码的基本概念,提出了基于迷宫映射的图论设计方法,物理概念清晰、简洁易用。采用迷宫映射方法和“关键阱格点”互斥的“十字叉”判据,将CMG机构的编码问题转换为图论中顶点着色问题,揭示了这种锁机构的组合数学原理。对于导出的图G(V,E),其顶点集V(G)按色数χ(G)着色,可得到CMG机构的优化编码,即复合齿轮的齿轮层数最少。

摘要：我们考虑的问题来自于基于波分复用技术(WDM)的全光环形网络,给定环形网络中一个路(通讯请求)的集合,将每一条路分配一个波长,使得经过相同连接的路必须分配不同的波长,我们的目标就是找一个波长分配方案使所需的波长数目最小,令ω表示为路集中最大两两相交路的个数,本文我们设计了一个可以保证指派到路集的波长数目不超过1.5ω的近似算法,因为ω是路集所需波长最小数目的一个下界,所以该算法的近似比不超过1.5。

摘要：CMG机构是一种密码鉴别机构,齿牙编码是其核心设计问题。应用贪婪算法求解CMG机构优化编码的顶点着色问题,具有时间复杂度低、易于编程的优点,在大多数情况下可满足应用需求。基于这一思路,采用V isual Basic编写了一个用户界面友好的CMG机构优化编码程序。该程序包括两个功能定义清晰的模块,即编码模块和校验模块,可自动求解、校验优化编码。

摘要：通过分析机场停机位分配的特点,以停机位使用数量最少、航空器在机场滑行距离或时间最短且充分考虑机位均衡利用为目标,建立了机场停机位分配问题的优化模型。应用图论的原理将该问题转化为对图的顶点着色问题,在随机序列启发式搜索求解基础上,设计了基于蚂蚁径路搜索规则的迭代寻优算法,即通过设置邻接矩阵,使每只蚂蚁在可行域内一步步构建有化解,该算法有效地避免了启发式搜索易陷入局部最优的缺陷。最后构造了算例,验证了该模型与算法的合理性。