第３１卷第ｌ２期 计 算 机 学 报 Ｖｏ１．３１ Ｎｏ．１２ ２００８年１２月 ＣＨＩＮＥＳＥ ＪＯＵＲＮＡＬ ＯＦ ＣＯＭＰＵＴＥＲＳ Ｄｅｃ．２００８ 经典Ｒａｍｓｅｙ数ＤＮＡ计算模型（Ｉ）：位序列计算模型 许 进” 范月科。’ （北京大学信息科学技术学院高可信软件技术教育部重点实验室北京 １００８７１） （华中科技大学分子生物计算机研究所 武汉４３００７４） 摘 要 Ｒａｍｓｅｙ数问题是组合数学乃至整个数学中最具魅力的研究领域，也是最困难的数学问题之一．对于经典 Ｒａｍｓｅｙ数，至今只有９个Ｒａｍｓｅｙ数得到解决．按照传统的算法，其搜索空间太大，当前的电子计算机无法胜任．研 究表明，ＤＮＡ计算在求解困难的ＮＰ一完全问题上优于电子计算机．目前已经建立了众多求解ＮＰ－完全问题的ＤＮＡ 计算模型，但未见到用于求解Ｒａｍｓｅｙ数的ＤＮＡ计算模型．作者建立了一种新颖的ＤＮＡ计算模型，用于一般经典 Ｒａｍｓｅｙ数的求解．全文共分两篇，该文属首篇，建立了一种可适用于ＤＮＡ计算模式的所谓的求解Ｒａｍｓｅｙ数的位 序列计算模型，其中的位序列是以图的相邻矩阵下三角阵中行从左到右、列从上到下的排列次序．文中重点对该模 型的机理与使用方法进行了分析研究． 关键词 经典Ｒａｍｓｅｙ数；ＤＮＡ计算；位序列计算模型 中图法分类号ＴＰ３０１ Ｃｌａｓｓｉｃａｌ Ｒａｍｓｅｙ Ｎｕｍｂｅｒ ＤＮＡ Ｃｏｍｐｕｔｉｎｇ Ｍｏｄｅｌ（Ｉ）： Ａｄｄ－Ｂｉｔ—Ｓｅｑｕｅｎｃｅ Ｍｏｄｅｌ ｘｕ Ｊｉｎ ’ ＦＡＮ Ｙｕｅ—Ｋｅ。 ”（Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｓｏｆｔ７ＡＫｌｒｅ．Ｓｃｈｏｏｌ ｏｆ Ｅｌｅｃｔｒｏｎｉｃｓ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ， Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏｆ Ｈｉｇｈ Ｃｏｎｆｉｄｅｎｃｅ Ｓｏｉｔ７．￣２ｒｅ Ｔｅｃｈｎｏｌｏｇｉｅｓ ｏｆ Ｍｉｎｉｓｔｒｙ ｏｆ Ｅｄｕｃａｔｉｏｎ，Ｐｅｋｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ １００８７１） ’（Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｂｉｏｍｏｌｅｃｕｌａｒ Ｃｏｍｐｕｔｅｒ，Ｈｕａｚｈｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｗｕｈａｎ ４３００７４） Ａｂｓｔｒａｃｔ Ｃｌａｓｓｉｃａｌ Ｒａｍｓｅｙ ｎｕｍｂｅｒ ｐｒｏｂｌｅｍ ｉｓ ａ ＮＰ ｃｏｍｐｌｅｔｅ ｐｒｏｂｌｅｍ．Ｉｔ ｔａｋｅｓ ｅｘｐｏｎｅｎｔｉａｌ ｔｉｍｅ ｔｏ ｓｏｌｖｅ ｃｌａｓｓｉｃａｌ Ｒａｍｓｅｙ ｎｕｍｂｅｒ ｐｒｏｂｌｅｍ ｗｉｔｈ ｔｒａｄｉｔｉｏｎａｌ ｅｌｅｃｔｒｏｎｉｃｓ ｃｏｍｐｕｔｅｒ．Ｉｔ ｉｓ ｎｅｃｅｓｓａｒｙ ｔｏ ｓｔｕｄｙ ｎｅｗ ｃｏｍｐｕｔａｔｉｏｎ ｍｅｔｈｏｄｓ ｂｅｃａｕｓｅ ｔｒａｄｉｔｉｏｎａｌ ｅｌｅｃｔｒｏｎｉｃｓ ｃｏｍｐｕｔｅｒ ｆａｃｅｓ ｗｉｔｈ ｇｒｅａｔｌｙ ｄｉｆｆｉ— ｃｕｌｔｙ ｉｎ ｓｏｌｖｉｎｇ ＮＰ ｃｏｍｐｌｅｔｅ ｐｒｏｂｌｅｍ．ＤＮＡ ｃｏｍｐｕｔｉｎｇ ｐｏｓｓｅｓｓｅｓ ｈｉｇｈ ｐａｒａｌｌｅｌｉｓｍ ｉｎ ｄａｔａ ａｎｄ ｈｉｇｈｅｒ ｓｔｏｒａｇｅ ｃａｐａｃｉｔｙ ｔｈａｎ ｎｏｒｍａｌ ｓｙｓｔｅｍｓ．Ｈｅｎｃｅ，ｉｎ ｔｈｅｏｒｙ，ｉｔ ｉｓ ｆｅａｓｉｂｌｅ ｔｏ ｓｏｌｖｅ ＮＰ ｔｏｍ— ｐｌｅｔｅ ｐｒｏｂｌｅｍｓ ｗｉｔｈ ＤＮＡ ｃｏｍｐｕｔｉｎｇ．Ａ ｎｏｖｅｌ ｍｅｔｈｏｄ ｉｓ ｐｒｏｐｏｓｅｄ ａｎｄ ｕｓｅｄ ｔｏ ｓｏｌｖｅ ｔｈｅ ｃｌａｓｓｉｃａｌ Ｒａｍｓｅｙ ｎｕｍｂｅｒ ｐｒｏｂｌｅｍ ｉｎ ｔｈｉｓ ｐａｐｅｒ．Ｆｉｒｓｔｌｙ，ａ ｍｅｔｈｏｄ ｆｏｒ ＤＮＡ ｓｅｑｕｅｎｃｅ ｃｏｄｅ ｂａｓｅｄ ｏｎ ｇｒａｐｈ— ｉｃ ｓｅｑｕｅｎｃｅ ｉｓ ｐｒｅｓｅｎｔｅｄ．Ｉｎ ｏｒｄｅｒ ｔｏ ｒｅｆｌｅｃｔ ａｌｌ ｐｏｓｓｉｂｌｅ ｉｎｆｏｒｍａｔｉｏｎ ｏｆ Ｐ—ｏｒｄｅｒ ｇｒａｐｈｓ，ｉｔ ｉｓ ｆｏｃｕｓｅｄ ｏｎ ｔｈｅ ｅｎｃｏｄｉｎｇ ｏｆ Ｐ—ｏｒｄｅｒ ｃｏｍｐｌｅｔｅ ｇｒａｐｈ．Ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｔｈｅ ｅｄｇｅｓ ｉｎ ｔｈｅ ｇｒａｐｈ ｉｓ Ｐ＊（ 一１）／２ １．Ｔｈｅ ｄｅｌｔａ—ｅｎｃｏｄｉｎｇ ｍｅｔｈｏｄ ｉｓ ｓｅｌｅｃｔｅｄ．Ｔｈｅ ｓｅｑｕｅｎｃｅｓ ｏｆ ｅｎｃｏｄｉｎｇｓ ａｒｅ ｔｈｅ ｅｄｇｅｓ １，２，…，Ｐ＊（ｐ一１）／２ １．Ｈｅｒｅ，ｔｈｅ ｅｄｇｅｓ １，２，…，Ｐ＊（户一１）／２ １ ｒｅｐｒｅｓｅｎｔ ａｄｊａｃｅｎｔ ｌｏｗｅｒ ｔｒｉａｎｇｕ— ｌａｒ ｍａｔｒｉ ｘ ａｒｒａｙ ｉｎ ｏｒｄｅｒ ｆｒｏｍ ｌｅｆｔ ｔｏ ｒｉｇｈｔ，ｔｏｐ ｔｏ ｂｏｔｔｏｍｉｎ ｔｈｅ ｇｒａｐｈ Ｇ．Ｔｈｅ ｃｈａｒａｃｔｅｒ ｏｆ ｔｈｉｓ ｅｎ— ｃｏｄｉｎｇ ｉｓ ｔｏ ｓｏｒｔ ｔｈｅｍ ｉｎｔｏ ｐ一１ ｃｌａｓｓｅｓ，ａｎｄ ｔｈｅ ｅｄｇｅｓ ｉｎ ｔｈｅ ｉ ｃｌａｓｓ ａｒｅ ｃｏｍｐｏｓｅｄ ｏｆ｛ ｌ， ＋ｌ｝， ｛ ２，７３ｉ＋１，…，｛ ， １．１），ｉ一１，２，…，Ｐ一１．Ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｅｎｃｏｄｉｎｇ，ｔｈｅ ｌｅｎｇｔｈ Ｐ＊（ 一１）／Ｚ！ ｏｆ ０－１ ｓｅｑｕｅｎｃｅ ｃａｎ ｂｅ ｍａｐｐｅｄ ｔｏ ａｌｌ ｌａｂｅｌｅｄ ｓｕｂ—ｇｒａｐｈｓ ｗｉｔｈ Ｐ ｖｅｒｔｅｘｅｓ．Ｉｔ ｍｅａｎｓ ｔｈａｔ ａｒｂｉｔｒａｒｙ ０－１ ｓｅｑｕｅｎｃｅ ｗｉｔｈ ｌｅｎｇｔｈ Ｐ＊（ 一１）／２ １ ｃｏｒｒｅｓｐｏｎｄｓ ｔｏ ｔｈｅ ｇｒａｐｈ ｗｉｔｈ ｔｈｅ ｏｒｄｅｒ Ｐ；Ｏｎ ｔｈｅ ｏｔｈｅｒ ｈａｎｄ，ａｎｙ ｏｒｄｅｒ Ｐ ｆｏｒ ｔｈｅ ｌａｂｅｌｅｄ ｇｒａｐｈ ｃｏｒｒｅｓｐｏｎｄｓ ｔｏ ０－１ ｓｅｑｕｅｎｃｅ ｗｉｔｈ ｌｅｎｇｔｈ Ｐ＊（ｐ一１）／２ １． 收稿日期：２００８—１０—３０．许进，男，１９５９年生，教授，博士生导师，研究兴趣为ＤＮＡ计算和ＤＮＡ计算机、神经网络、遗传算法、图论等 范月科，男，１９５９年生，博士，研究兴趣为ＤＮＡ计算和ＤＮＡ计算机、图论等． ２０７４ 计 算 机 学 报 ２００８年 Ｓｅｃｏｎｄｌｙ，ｓｏｍｅ ｐｒｏｂｌｅｍｓ ａｒｅ ｄｉｓｃｕｓｓｅｄ，ｓｕｃｈ ａｓ ｔｈｅ ｓｅｔ ｐｒｏｂｌｅｍ ｏｆ ｌａｂｅｌｉｎｇ ｓｕｂ—ｇｒａｐｈ ａｎｄ ｕｎ—ｌａ— ｂｅｌｉｎｇ ｓｕｂ—ｇｒａｐｈ，ｅｓｐｅｃｉａｌ ｔｈｅ ｍｅｔｈｏｄ ｏｆ ｓｅｑｕｅｎｃｅ ｄｅｎｏｔｅｄ．Ｆｉｎａｌｌｙ，ｉｎ ｏｒｄｅｒ ｔｏ ｄｅｌｅｔｅ ｔｈｅ ｉｎｃｏｒ— ｒｅｃｔ ｓｏｌｕｔｉｏｎｓ ｉｎ ｔｈｅ ｆｉｒｓｔ，ｔｈｅ ｉｄｅａ，ｍｅｔｈｏｄ ａｎｄ ｐｒｏｃｅｓｓ ｏｆ ｄｅｌｅｔｉｎｇ ｉｎｃｏｒｒｅｃｔ ｓｏｌｕｔｉｏｎｓ ａｒｅ ｐｒｅｓｅｎ— ｔｅｄ，ａｎｄ ａｎ ｉｎｓｔａｎｃｅ ｉｓ ｐｒｅｓｅｎｔｅｄ ｔｏ ｉｌｌｕｍｉｎａｔｅ ｔｈｅ ｐｒｏｐｏｓｅｄ ｍｅｔｈｏｄ．Ｔｈｅ ｂａｓｉｃ ｉｄｅａ ｉｓ ｔｏ ｃｏｎ— ｓｔｒｕｃｔ ａ ｇｒａｐｈ ｂｙ ｂｉｔ ｂｙ ｓｔｅｐ．Ｉｎ ｏｒｄｅｒ ｔｏ ｄｅｌｅｔｅ ｉｎｃｏｒｒｅｃｔ ｓｏｌｕｔｉｏｎｓ ａｓ ｓｏｏｎ ａｓ ｐｏｓｓｉｂｌｅ ｔｈｅ ｇｒａｐｈ ｃｏｎｓｔｒｕｃｔｅｄ ｄｏｓｅ ｎｏｔ ｉｎｃｌｕｄｅ ｔｈｅ Ｋ ａｎｄ Ｎ ．Ｔｈｅ ｍｅｔｈｏｄ，ｗｈｉｃｈ ｄｅｌｅｔｅｓ ｔｈｅ ｓｅｔ ｏｆ ｓｕｂ—ｇｒａｐｈｓ ｉｎ— ｃｌｕｄｉｎｇ Ｋ ａｎｄ Ｎ ｆｒｏｍ ｔｈｅ ｓｅｔ ｏｆ ａｌ１ Ｋ 一ｏｒｄｅｒ ｓｕｂ—ｇｒａｐｈ ｌａｂｅｌｅｄ，ｄｅｌｅｔｅｓ ｔｈｅ ｃｏｒｒｅｓｐｏｎｄｉｎｇ ｂｉｔ， ｗｈｉｃｈ ｉｓ ｃｏｒｒｅｓｐｏｎｄｉｎｇ ｔｏ ｔｈｅ ｅｄｇｅｓ ｓｅｔ ｏｆ ａｌｌ 一ｏｒｄｅｒ Ｃｏｍｐｌｅｔｅ ｓｕｂ—ｇｒａｐｈ，ｆｒｏｍ ｔｈｅ ｃｏｒｒｅｓｐｏｎｄ— ｉｎｇ ｓｅｑｕｅｎｃｅ Ｌ口；ｉｎｃｌｕｄｉｎｇ ｔｈｅ ｓｅｔ ｏｆ ｓｅｑｕｅｎｃｅｓ ｃｏｒｒｅｓｐｏｎｄｉｎｇ ｂｉｔ．Ｔｈｅ ｋｅｙ ｓｔｅｐ ｆｏｒ ｔｈｅ ｂｉｔ ｓｅ— ｑｕｅｎｃｅ ｂａｓｅｄ—ｏｎ ＤＮＡ ｃｏｍｐｕｔａｔｉｏｎ ｃａｎ ｄｅｌｅｔｅ ｔｈｅ ｉｎｃｏｒｒｅｃｔ ｓｏｌｕｔｉｏｎ ｗｈｅｎｅｖｅｒ ｉｔ ｉｓ ｂｒｏｕｇｈｔ ｕｐ． Ｃｏｎｓｅｑｕｅｎｔｌｙ，ｉｔ ｃａｎ ｗｅａｋｅｎ ｔｈｅ ｓｐｅｅｄ ｏｆ ｗｈｉｃｈ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｓｕｂ—ｇｒａｐｈ ｉｎｃｒｅａｓｅｓ，ａｎｄ ａｌｓｏ ｐｒｏ— ｖｉｄｅｓ ａ ｆｅａｓｉｂｌｅ ｍｅｔｈｏｄ ｆｏｒ ｆｉｎｄｉｎｇ ｔｈｅ Ｒａｍｓｅｙ ｎｕｍｂｅｒ ｗｉｔｈ ｍｕｃｈ ｈｉｇｈｅｒ ｏｒｄｅｒ．Ｉｎ ａｄｄｉｔｉｏｎ，ｉｔ ｉｓ ｄｅｍｏｎｓｔｒａｔｅｄ ｔｈｅ ｐｏｓｓｉｂｉｌｉｔｙ ｏｆ ｕｓｉｎｇ ｔｈｅ ａｄｖａｎｔａｇｅ ｉｎｈｅｒｅｎｔ ｉｎ ＤＮＡ ｃｏｍｐｕｔａｔｉｏｎ，ｉｎｃｌｕｄｉｎｇ ｖａｓｔ ｉｎｆｏｒｍａｔｉｏｎ ｓｔｏｒａｇｅ ｃａｐａｃｉｔｉｅｓ ａｎｄ ｍｕｃｈ ｈｉｇｈｌｙ ｃｏｍｐｕｔｉｎｇ ａｂｉｌｉｔｙ．Ｔｈｅ ｍｏｒｅ ｄｅｔａｉｌ ｒｅｓｅａｒｃｈｅｓ ａｂｏｕｔ ｈｏｗ ｔｏ ｓｏｌｖｅ ｔｈｅ Ｒａｍｓｅｙ ｎｕｍｂｅｒ ｕｓｉｎｇ ＤＮＡ ｃｏｍｐｕｔｅｒ ｗｉｔｈ ｂｅ ｇｉｖｅｎ ｉｎ ｔｈｅ ｓｅｃｏｎｄ ｐａｐｅｒ． Ｋｅｙｗｏｒｄｓ Ｒａｍｓｅｙ ｎｕｍｂｅｒ；ＤＮＡ ｃｏｍｐｕｔｉｎｇ；ａｄｄ—ｂｉｔ—ｓｅｑｕｅｎｃｅ ｃｏｍｐｕｔｉｎｇ ｍｏｄｅｌ 已找到６５６个４２阶Ｒａｍｓｅｙ（５，５）一图，人们推测 引 目 给定任意两个正整数ｋ， ，总存在一个最小的 正整数ｒ（ｋ，ｚ），使得任意ｒ（ｋ， ）个顶点的图，或者含 有ｋ个顶点的团，或者含有ｚ个顶点的独立集．我们 把这个最小的正整数，－（ｋ，Ｚ）称为关于（ｋ， ）的 Ｒａｍｓｅｙ数．容易算出ｒ（１，ｚ）一ｒ（志，１）一１，ｒ（２，ｚ）一ｚ， ｒ（矗，２）一是，ｒ（是，Ｚ）一ｒ（ｚ，ｋ）．我们把ｒ（ｋ，１）称为经 典Ｒａｍｓｅｙ数． ４３～４９阶Ｒａｍｓｅｙ（５，５）一图可能存在（这些结果参 见文献Ｅｌ１）．注意，每个Ｒａｍｓｅｙ（５，５）一图的补图也 是Ｒａｍｓｅｙ（５，５）一图． 近２Ｏ年来，电子计算机在求解Ｒａｍｓｅｙ数问题 的研究上起到了巨大的促进作用，如Ｒａｍｓｅｙ数 ｒ（３，８）和ｒ（４，５）均是借助于电子计算机来完成 的Ｉ２ ］．但随着问题规模的增大，如ｒ（３，１０）至少需 要从４Ｏ个顶点的图集中搜索是否存在Ｒａｍｓｅｙ图， 而这个搜索次数理论上需要约２ 。个图，显然电子 计算机对此是无法实现的．这就迫使科学家在 Ｒａｍｓｅｙ数问题的研究上另辟蹊径． 本文所言之图皆指有限、无向、简单图．设正整数 ｍ，”，ｐ １，Ｒａｍｓｅｙ（ｍ，ｎ）一图是指既不含 个顶点 的团也不含ｎ个顶点独立集的图；Ｒａｍｓｅｙ（ｍ， ， ）一 图是指阶数为Ｐ的Ｒａｍｓｅｙ（ｍ，ｎ）一图．分别用 Ｇ（ｍ，ｎ），Ｇ（ｍ， ，Ｐ）表示所有Ｒａｍｓｅｙ（ｍ，ｎ）一图和 Ｒａｍｓｅｙ（ｍ，ｎ，户）一图的集合．Ｒａｍｓｅｙ数ｒ（ｍ，ｎ）定 义为不存在Ｒａｍｓｅｙ（ｍ，ｎ， ）一图的最小数Ｐ．目前 已确定的经典Ｒａｍｓｅｙ数有：ｒ（３，３）一６，只有１个 Ｒａｍｓｅｙ图；ｒ（３，４）一９，共有３个Ｒａｍｓｅｙ图； ｒ（３，５）一１４，只有１个Ｒａｍｓｅｙ图；ｒ（３，６）一１８，共 最近１Ｏ多年来，ＤＮＡ计算机的研究得到了长 足的发展，已建立了不少求解组合优化中ＮＰ一完全 问题的ＤＮＡ计算模型，诸如Ｈａｍｉｌｔｏｎ路与圈问 题＿４ ］、图的最大团与最大独立集问题口 ］、图顶点 着色问题ｌ９ 、中国邮递员问题Ｉ１ 、０—１规划问 题＿１ ¨］等，但至今尚未见到一篇关于求解Ｒａｍｓｅｙ 数这个组合数学领域困难问题的ＤＮＡ计算模型． ２００７年，我们在ＤＮＡ计算机研究方面有一个较大 的突破：给出了消除解空间指数爆炸问题的一种新 方法，在此基础上建立了一个求解６１个顶点图的 有１９１个Ｒａｍｓｅｙ图；ｒ（３，７）一２３，共有１９１个 Ｒａｍｓｅｙ图；ｒ（３，８）：：：２８，已知道它有４３０２１５个 Ｒａｍｓｅｙ图；ｒ（３，９）一３６，只有１个Ｒａｍｓｅｙ图； ｒ（４，４）一１８，只有１个Ｒａｍｓｅｙ图；ｒ（４，５）一２５，已 ３一着色问题ＤＮＡ计算模型并成功地进行了实验， 这标志着ＤＮＡ计算机不仅已经具备了进行某些大 规模信息处理的能力，而且也可以用于解决电子计 算机无法解决的问题了．正是受到这个工作的启迪， 我们在本文中建立了用于求解经典Ｒａｍｓｅｙ数的 发现３５０９０４个Ｒａｍｓｅｙ图（可能更多）［１ ］． 目前已找到１０５个３４阶Ｒａｍｓｅｙ（４，６）一图，人 们推测３５￣４０阶Ｒａｍｓｅｙ（４，６）一图可能存在．目前 １２期 许进等：经典Ｒａｍｓｅｙ数ＤＮＡ计算模型（Ｉ）：位序列计算模型 ２０７５ ＤＮＡ计算机模型． 借助于电子计算机在求解经典Ｒａｍｓｅｙ数模型 的研究上，Ｍｃｋａｙ等人作出了杰出的贡献ｌ２ ］．他们 所建立模型的基本思想是利用图的自同构群来删除 同构子图，其具体做法是：首先建立１Ｏ个顶点所有 非标定子图的集合，然后以这１０个顶点非标定子图 的集合为基础，进一步构造所需要的图集合． Ｍｃｋａｙ等人在进一步构造所需的图集合时，一 般通过每次增加一个顶点来完成．但是，即使如此， 一下子增加的非解也是很多，从而导致电子计算机 超过一定的范围就无能为力．这也就是目前利用电 子计算机求解Ｒａｍｓｅｙ数停滞不前的根本原因 所在． 本文提出的模型，在非解的删除上与Ｍｃｋａｙ等 人的模型相比，只增加一个位，也就是说，只增加一 条边所占位置的一半，这样可以过早地删除非解，使 ｌ ２ ３ ４ ５； 得非解空间大大降低．例如，对于一个Ｐ阶图而言，２ ｐＣ １ ２ ４ ７； 按照Ｍｃｋａｙ的方法，需要增加的位数是２（Ｐ一１），卜 ｌ 而按照本文的方法，仅仅１位．也就是说，Ｍｃｋａｙ一 ２ ｐ Ｃ 次增加的解空间为２ ｚ ｃｐ 倍，而本模型仅为２倍．３ ５ ８．．． 我们把这种模型称为求解经典Ｒａｍｓｅｙ数的边 ＋ ２ 序列模型，而Ｍｃｋａｙ的模型称为点序列模型．边序 列模型适应于电子计算机的计算，更适应于ＤＮＡ 计算机模型． 文中约定，在整篇论文中，从 个元素中取出 个元素的组合数的两种表示方式，ｃ 和（ 、 ）是一样 的，可根据不同的排版需要任意选取．有关图与 Ｒａｍｓｅｙ数方面的术语与记号可参见文献［１５—１６］． ２序列编码 由于我们所采用信息处理的“数据”是线性 ＤＮＡ序列，因而必须将一个给定图的全部信息在一 个序列中完整地反应出来．众所周知，用图的顶点序 列是不可能反应出图的完整的信息，而图的边序列 可完整地反应出图的信息． 为了反应出所有可能的Ｐ一阶图的信息，我们针 对Ｐ一阶完全图进行编码．Ｐ一阶完全图共有边的数 目是： （Ｐ、厶。，） 一告户（厶 户一１）． 因此，给定的编码序列为１，２，…，ｃ ．那么，边 如何排序呢？即，序列１，２，…，Ｃ；中每个元素如何 与这Ｃｊ条边一一对应起来．我们在本文中选择了所 谓的△一编码方法．具体方法如下：对于具有Ｐ个顶 点的图Ｇ，令图的顶点集Ｖ—Ｖ（Ｇ）一｛ ，７３ｚ，…， ），边集Ｅ一｛｛ ， ，｝；ｉ， ∈Ｖ，毋 ）．编码的序列， 即边的排列序列为１，２，…，ｃ；．其中１，２，…，Ｃ；所 表示的边为图Ｇ相邻矩阵中下三角阵依次从左到 右、从上到下的次序，如图１所示． ９ １０ Ｃ；一１＋３……ｃ； 圈１码的定义 现在以 一６为例给予说明： ＝＝：｛ ，７３２， ，７３ ， ， ｝，序列的长度为Ｃ：一１５，即序列为１，２，…， １５，其中， １一｛ ｌ， ２），２＝：：｛ ｌ， ３｝，３一｛７３２， ３｝，４一｛ ｌ， ４｝， ５一｛７３２，７３４｝，６一｛ ３，口４），７一｛ １， ｓ｝，８一｛７３２， ５）， ９一｛７３３，７３５｝，ｌＯ一｛口４， ５｝，１１一｛ ｌ， ６｝，１２一｛ ２， ６｝，１３一｛ ３， ６｝，１４一｛ ４， ６｝，１５一｛ ５， ６｝． 这种编码的特点是将码分成了 一１类，第ｉ类 中的边的构成是｛ ｌ， …｝，｛７．１２ ｍ＋１），｛ ３，７３…），…， ｛ ， 件 ｝，其中， 一１，２，…，ｐ一１． 按照这种编码，长度为Ｃ；的０—１序列集合与具 有Ｐ个顶点的所有标定子图构成的集合之间，通过 映射： 厂ｃｅ— ， ， 一｛ ： Ｅ Ｅ （Ｇ； ｃ 可建立起一一对应的关系．也就是说，任意一个长度 为Ｃ：的０—１序列，通过式（１）唯一对应一个阶数为 Ｐ的标定图；反过来，任意一个阶数为Ｐ的标定图唯 一对应于一个Ｃ；的０—１序列．下面举例给予说明． 例１． 对于５一圈图Ｃ ，如图２所示，共有５条 边，分另Ｕ是１一｛ ｌ， ２），３一｛ ２， ３｝，６一｛ ３， ４｝， ７一｛７２） ，７３ ｝，１０：＝：｛ ４， ｝，这５条边对应位置为１， 其余为０，于是，这个图对应的序列为１０１００１１００１． 按这种编码，我们自然会提出下列问题． ２ 图２ ５～圈图 计 算 机 学 报 问题：什么样的序列对应的标定图是同构的？如 何消除？如１０１００１１００１，１０１１００００１１，１０００１１１０１０， １１００１０００ｌ１，１００１０１０ｌ１０，ｌ１０００１０１０１，０１ｌ０１０１００１， Ｏ１１１０００１０１，０１００１１１１００，０１０１１００１１０，００１１１０１０１０， ００１１０１１１００．按照式（１）所对应的图依次由图３给 出．显然，这些图均是同构的，但对应的０—１序列却 不同．这个事实使得我们需要构造的，或者寻找 Ｒａｍｓｅｙ图显得非常困难． 图３ １２个同构的图 ２．应用对照表，得到所删除对应序列中的位置集合； ３非解的删除问题 本模型的基本思想是：按位逐步构造出所需要 的，既不含Ｋ 也不含Ｎ 的图．这样的目的是尽可能 早地删除非解． ３．构造出含有可构成 一阶完全空图Ⅳ 的Ｃ；个集合； ４．应用对照表，得到所删除对应序列中的位置集合． ４求解ｒ（３，４）的计算实例 业已得知ｒ（３，４）＝９，即需要从８个顶点的图 集中找到Ｒａｍｓｅｙ图，而８个顶点共有长度为Ｃｉ一 一２８位的０—１序列．具体步骤如下． 步骤１．建立对照表． 表１对照表 序列位 对应边 （１，２｝ ｛１，３） ｛２，３｝ ｛１，４） ｛２，４） （３，４｝ ｛１，５） ｛２，５） ｛３，５） 从标定的所有Ｐ一阶子图集合Ｇ 中删除既含有 Ｋ 且Ｎ 的子图集合方法是从对应的序列Ｌ。中删 除对应含有所有可能的构成 一完全子图对应的边 集合对应位，以及含有所有可能的构成 一完全空图 的所有边的对应位的序列集合．也就是说，需要删除 的次数是 序列位 ｌ１ １１２ ｌｌ３ １ ２ ４ ｌｌ ５ １１６ ￡１７ ￡１８ １１９ 对应边 （１，６｝ ｛２，６｝ ｛３，６） ｛４，６｝ ｛５，６） （１，７｝ ｛２，７｝ ｛３，７） ｛４，７｝ 序列位 ｆ２Ｉ Ｚ２２ ｌｓａ １２４ ｌｚｓ ｌｚ６ ｌｚ７ Ｚ２８ 对应边 （６，７｝ ｛１，８） ｛２，８） ｛３，８） ｛４，８） （５，８） ｛６，８） ｛７，８｝ （ （ ）． 为后面方便，我们约定：Ｇ 的顶点集合用 ｆ１ ｌ２ ｌ３ ｌ４ ｌ５ Ｚ６ ｌ７ Ｚ８ ｌ９ ｛１，２，…，Ｐ｝来代替｛ ，ｕ ，…， ），并在此强调：构 成表示图集合Ｇ 的所有序列构成的集合Ｌ 的第ｉ 位用ｚ 表示，这里，ｉ一１，２，…，ｑ＝ｃ：． 总之，对于ｒ（ｍ， ）而言，需要实实在在地运行 ｌ１０ ｛４，５） １２０ ｛５，７） ＋ 次，特别当ｍ— 时，可设计使运行次数为 ２ｃ 次．且删除算法的步骤简要如下： １．构造出含有可构成 一阶完全子图Ｋ 的ｃ；个集合； 步骤２．确定需要删除Ｋ。的子集合及对应Ｌ。 中的位集合． １２期 许进等：经典Ｒａｍｓｅｙ数ＤＮＡ计算模型（Ｉ）：位序列计算模型 ２Ｏ７７ 对于８个顶点的图，需要删除Ｋ。的子集合的 数目是Ｃｉ一８×７×６／６—５６个．这５６个子集中每个 对应完全子图的边集以及该边集对应序列集Ｌ。中 ｛３，５，６｝一｛３５，３６，５６｝一｛Ｚ９，Ｚ１ ３，Ｚ１ ｝， ｛３，５，７）一｛３５，３７，５７｝一｛Ｚ ，Ｚ ８，Ｚ２。｝， ｛３，５，８｝一｛３５，３８，５８｝＝｛ｌ９，Ｚ２ ，Ｚ２６｝， 的位置集合分别是 ｛１，２，３｝一｛１２，１３，２３｝一｛Ｚｌ，ｌ２，Ｚ３）， ｛１，２，４｝一｛１２，１４，２４｝一｛Ｚ１，Ｚ ，Ｚ５）， （１，２，５｝一｛１２，１５，２５｝一｛Ｚ ，Ｚ ，Ｚ ）， ｛１，２，６｝一｛１２，１６，２６｝一｛Ｚ ，Ｚ。 ，Ｚ ２）， ｛１，２，７）一｛１２，１７，２７｝一｛Ｚ１，Ｚ Ｚ１ ｝， ｛１，２，８｝一｛１２，１８，２８｝一｛Ｚ１，Ｚ２２，Ｚ２３）， ｛１，３，４｝一｛１３，１４，３４）一｛Ｚ２，Ｚ ，Ｚ６｝， ｛１，３，５｝一｛１３，１５，３５｝一｛Ｚ２，Ｚ７，Ｚ９｝， ｛１，３，６｝一｛１３，１６，３６｝一｛Ｚ２，Ｚ Ｚ 。｝， ｛１，３，７｝一｛１３，１７，３７｝一｛Ｚ２，Ｚ１６，Ｚ ８｝， ｛１，３，８｝一｛１３，１８，３８｝一｛ ， ２２，Ｚ２ ｝， ｛１，４，５）一｛１４，１５，４５｝一｛２４，Ｚ ，ｚｌ。｝， ｛１，４，６｝一｛１４，１６，４６｝一｛Ｚ ，Ｚ Ｚ ）， ｛１，４，７｝一｛１４，１７，４７）一｛ｌ４，Ｚｌ６，Ｚｌ。｝， ｛１，４，８｝一｛１４，１８，４８）：＝＝｛Ｚ４，Ｚ２２， ２ ｝， ｛１，５，６｝一｛１５，１６，５６｝一｛Ｚ ，Ｚ。 ，Ｚ ）， ｛１，５，７｝一｛１５，１７，５７｝一｛Ｚ７，Ｚ Ｚ２ｏ｝， ｛１，５，８）一｛１５，１８，５８）一｛Ｚ ，Ｚ ｚ２，Ｚ ｝， ｛１，６，７｝一｛１６，１７，６７｝一｛Ｚ Ｚ ，Ｚ２ｌ｝， ｛１，６，８）一｛１６，１８，６８｝一｛Ｚ１。，Ｚ２２，Ｚ２ ｝， ｛１，７，８）一｛１７，１８，７８）一｛Ｚ ，Ｚ２２，Ｚ２８｝， ｛２，３，４｝一｛２３，２４，３４｝一｛Ｚ３，Ｚ５，ｌ６）， ｛２，３，５）一｛２３，２５，３５）一｛Ｚ。，Ｚ８，Ｚ。｝， ｛２，３，６｝一｛２３，２６，３６｝一｛Ｚ。，Ｚ ２，Ｚ 。｝， ｛２，３，７）一｛２３，２７，３７）一｛Ｚ３，ｌｌ ，Ｚ１８｝， ｛２，３，８｝一｛２３，２８，３８）一｛Ｚ。，Ｚ２。， ２ ｝， ｛２，４，５）一｛２４，２５，４５）＝＝＝｛Ｚ５，Ｚ８，Ｚｌｏ）， ｛２，４，６｝一｛２４，２６，４６｝一｛Ｚ ，Ｚ Ｚ ｝， ｛２，４，７）一｛２４，２７，４７｝一｛Ｚ５，￡ Ｚ１。｝， ｛２，４，８）一｛２４，２８，４８）一｛Ｚ ，Ｚ 。，Ｚ ｝， ｛２，５，６｝一｛２５，２６，５６）一｛Ｚ８， １２，Ｚ１ ｝， ｛２，５，７）一｛２５，２７，５７｝一｛Ｚ８，Ｚ Ｚ２ｏ）， ｛２，５，８｝一｛２５，２８，５８｝一｛Ｚ８，Ｚ２３，Ｚ： ）， ｛２，６，７）一｛２６，２７，６７｝一｛Ｚ１２，Ｚｌ７，Ｚ２１｝， ｛２，６，８｝一｛２６，２８，６８｝一｛Ｚｌ２，Ｚ２３，Ｚ２ ｝， ｛２，７，８｝一｛２７，２８，７８｝一｛Ｚ ，Ｚ 。，Ｚ２８｝， ｛３，４，５｝一｛３４，３５，４５｝一｛Ｚ ，Ｚ。，Ｚ１。）， ｛３，４，６）一｛３４，３６，４６）一｛Ｚ ，Ｚ 。，Ｚ１ ｝， ｛３，４，７｝一｛３４，３７，４７）一｛Ｚ ，Ｚ ８，Ｚ ｝， ｛３，４，８｝一｛３４，３８，４８｝一｛Ｚ６，Ｚｚ４，Ｚ２５｝， ｛３，６，７｝一｛３６，３７，６７｝一｛Ｚ Ｚ Ｚ２ｌ｝， ｛３，６，８｝一｛３６，３８，６８）一｛Ｚ１３，Ｚ２４，Ｚ２７｝， ｛３，７，８｝一｛３７，３８，７８｝一｛Ｚｌ８，Ｚ２ ，Ｚ２８｝， ｛４，５，６）一｛４５，４６，５６）一｛ｌ 。，Ｚ ，ｌｌ５）， ｛４，５，７｝一｛４５，４７，５７｝一｛Ｚ１。，Ｚ Ｚ２。｝， ｛４，５，８｝一｛４５，４８，５８｝一｛Ｚ１。，Ｚ２５，Ｚ２６）， ｛４，６，７｝— ｛４６，４７，６７）一｛Ｚ１ ，Ｚ。。，ｌ２ｌ｝， ｛４，６，８｝一｛４６，４８，６８｝一｛Ｚｌ ，Ｚ２５，Ｚ２７）， ｛４，７，８｝一｛４７，４８，７８｝一｛Ｚ Ｚ２ｓ，Ｚ２８｝， ｛５，６，７｝一｛５６，５７，６７｝一｛Ｚ１５，ｌ２。，Ｚ２１）， ｛５，６，８｝一｛５６，５８，６８｝一｛ｌ ，Ｚ２ ，Ｚ２ ｝， ｛５，７，８）一｛５７，５８，７８）＝｛Ｚ２。，Ｚ２。，Ｚ２８｝， ｛６，７，８）一｛６７，６８，７８）一｛Ｚ２１，Ｚ２ ，Ｚ２８｝． 步骤３．确定需要删除Ｎ 的子集合及对应Ｌｓ 中的位集合． 对于８个顶点的图，需要删除Ｎ 的子集合的 数目是：Ｃ：一８×７×６×５／（４×３×２×１）一７０个．这 ７Ｏ个子集中每个对应完全空图的构成的所有空边集 以及该空边集对应序列集Ｌ。中的位置集合分别是 ｛１，２，３，４｝＿＋（１２，１３，２３，１４，２４，３４｝ 一｛Ｚｌ，ｌ２，Ｚ３，Ｚ４，Ｚ５，ｌ６）， ｛１，２，３，５｝一｛１２，１３，２３，１５，２５，３５） 一｛Ｚ１，Ｚ２，Ｚ３，Ｚ７，Ｚ８，Ｚ９｝， ｛１，２，３，６｝一｛１２，１３，２３，１６，２６，３６｝ 一｛Ｚ１，Ｚ２，Ｚ３，Ｚｌｌ，１１２，Ｚｌ３｝， ｛１，２，３，７｝一｛１２，１３，２３，１７，２７，３７｝ 一｛Ｚｌ，Ｚ２，Ｚ３，Ｚ１６，Ｚ１ ７，Ｚ１８）， ｛１，２，３，８｝一｛１２，１３，２３，１８，２８，３８｝ 一｛Ｚ１， ，ｌ３，Ｚ２２，Ｚ２３，ｌ２４｝， ｛１，２，４，５｝— ｛１２，１４，２４，１５，２５，４５） 一｛Ｚ１， ４，Ｚ５，Ｚ７，Ｚ８，Ｚ１０｝， ｛１，２，４，６｝一｛１２，１４，２４，１６，２６，４６） 一｛Ｚ１，Ｚ４，Ｚ５，１Ｉｌ，Ｚｌｚ，Ｚ１４｝， ｛１，２，４，７｝一｛１２，１４，２４，１７，２７，４７｝ 一｛Ｚ１，Ｚ４，Ｚｓ，Ｚ１６，Ｚ１ ７，Ｚ１９｝， ｛１，２，４，８｝一｛１２，１４，２４，１８，２８，４８｝ 一｛Ｚｌ，Ｚ４，Ｚ５，Ｚ２２，Ｚ２３，Ｚ２５｝， ｛１，２，５，６｝一｛１２，１５，２５，１６，２６，５６｝ 一｛Ｚｌ，Ｚ７，Ｚ８，Ｚｌｌ，Ｚ１２，Ｚ１５）， （１，２，５，７｝一｛１２，１５，２５，１７，２７，５７｝ 一｛Ｚｌ，Ｚ７，Ｚ８，Ｚ１ ６，Ｚｌ７，Ｚ２ｏ｝， ２Ｏ７８ 计 算 机 学 报 ２００８拄 ｛１，２，５，８）一｛１２，１５，２５，１８，２８，５８） 一｛１，５，７，８｝一｛１５，１７，５７，１８，５８，７８｝ 一｛Ｚｌ，ｌ７，ｌ８，Ｚ２２，Ｚ２３，Ｚ２６｝， ｛Ｚ７，ｌ１６，Ｚ２０，ｌ２２，Ｚ２６，ｌ２８｝， ｛１，２，６，７｝一｛１２，１６，２６，１７，２７，６７｝ ＝｛１，６，７，８｝＿＋｛１６，１７，６７，１８，６８，７８｝ 一｛ｌ１，Ｚ１ｌ，Ｚ１ ２，ｌ１６，Ｚ１ ７，ｌ２１）， ｛ｌ１，Ｚｌ１，Ｚ１ ｚ，Ｚ２２，１２３，Ｚ２７）， ｛ｌ１１，ｌｌ６，Ｚ２１，ｌ２２，Ｚ２７，ｌ２８｝， ｛１，２，６，８｝一｛１２，１６，２６，１８，２８，６８） 一｛２，３，４，５｝一｛２３，２４，３４，２５，３５，４５） 一｛ｌ３，Ｚ５，ｌ６，ｌ８，ｌ９，ｌｌｏ｝， ｛１，２，７，８）一｛１２，１７，２７，１８，２８，７８｝ 一｛２，３，４，６）一｛２３，２４，３４，２６，３６，４６｝ 一｛Ｚｌ，Ｚ１６，ＺＩ ７，１２２， ３，１。８）， ｛ ，Ｚ５，Ｚ６，Ｚ１２，Ｚｌ３，Ｚ１４｝， ｛１，３，４，５｝一｛１３，１４，３４，１５，３５，４５｝ ＝｛１ｚ，Ｚ４，ｌ６，１７，Ｚ９，ｌｌｏ）， ｛１，３，４，６｝一（１３，１４，３４，１６，３６，４６｝ 一｛Ｚ２，Ｚ４，ｌ６，ｌｌ１，ｌ１３，Ｚ１４）， ｛１，３，４，７）一｛１３，１４，３４，１７，３７，４７） ＝（１２，ｌ４，ｌ６，ｌｌ６， １８，ｌｌ９｝， ｛１，３，４，８｝— ｛１３，１４，３４，１８，３８，４８｝ 一｛Ｚｚ，Ｚ４，ｌ６，ｌ２２，Ｚ２４，Ｚ２５｝， ｛１，３，５，６｝一｛ｌ３，１５，３５，１６，３６，５６｝ ＝｛Ｚ２，Ｚ７，ｌ９，１ｌ１，ｌ１３，Ｚｌ５｝， ｛１，３，５，７）一｛１３，１５，３５，１７，３７，５７｝ 一｛ｌ２，ｌ７，Ｚ９，Ｚ１６，ｌｌ８，ｌ２ｏ）， ｛１，３，５，８｝一｛１３，１５，３５，１８，３８，５８） 一｛ｌ２，Ｚ７，１９，Ｚ２２，ｌ２４，Ｚ２６）， ｛１，３，６，７）一｛１３，１６，３６，１７，３７，６７｝ ：＝＝｛１２，１ｌ１，Ｚｌ３，１ｌ６，１１８，ｌ２ｌ｝， ｛１，３，６，８｝一｛１３，１６，３６，１８，３８，６８） ＝｛Ｚ２，Ｚ１ｌ，Ｚ１３，Ｚ２２，ｌ２４，ｌ２７｝， ｛１，３，７，８｝一｛１３，１７，３７，１８，３８，７８｝ 一｛Ｚ２，Ｚｌ６，ｌ１８，Ｚ２２，Ｚ２４，ｌ２８｝， ｛１，４，５，６｝．一｛１４，１５，４５，１６，４６，５６） ｛１４，Ｚ７，Ｚｌｏ，Ｚｌｌ，Ｚｌ４，ｌ１５｝， ｛１，４，５，７｝一｛１４，１５，４５，１７，４７，５７｝ 一｛Ｚ４，Ｚ７，Ｚ１０，１１６，Ｚ１９，Ｚ２ｏ｝， ｛１，４，５，８｝— ｛１４，１５，４５，１８，４８，５８｝ 一｛厶，ｌ７，ｌｌ０，１２２，Ｚ２５，Ｚ２６｝， ｛１，４，６，７）一｛１４，１６，４６，１７，４７，６７｝ ＝｛Ｚ４，ｌｌｌ，Ｚｌ４，ｌｌ６，Ｚ１９，Ｚ２１｝， ｛１，４，６，８｝一｛１４，１６，４６，１８，４８，６８｝ ＝｛Ｚ４，ｌ１ｌ，ｌｌ４，ｌ２２，Ｚ２ｓ，ｌ２７｝， ｛１，４，７，８）一｛１４，１７，４７，１８，４８，７８） 一｛ｌ４，ｌ１６，Ｚｌ９， ２２，Ｚ２５， ２８）， ｛１，５，６，７｝一｛１５，１６，５６，１７，５７，６７｝ 一｛ｌ７，１１１，１１５，Ｚ１６，Ｚ２０，Ｚ２１）， ｛１，５，６，８｝一（１５，１６，５６，１８，５８，６８｝ 一｛Ｚ７，Ｚ１ｌ，Ｚ１ ５，Ｚ２２，ｌ２６，Ｚ２７｝， ｛２，３，４，７｝一｛２３，２４，３４，２７，３７，４７｝ 一｛Ｚ３，ｌ５，Ｚ６，Ｚｌ ７，Ｚ１８，ｌｌ９）， ｆ２，３，４，８卜＋｛２３，２４，３４，２８，３８，４８｝ 一｛Ｚ３，ｌ５，ｌ６，ｌ２３，Ｚ２４，Ｚ２５｝， ｛２，３，５，６）一｛２３，２５，３５，２６，３６，５６｝ 一｛Ｚ３， ８， ９， １ ２，Ｚｌ３，Ｚｌｓ｝， ｛２，３，５，７｝一｛２３，２５，３５，２７，３７，５７） 一｛Ｚ３，ｌ８，Ｚ９，Ｚｌ７，Ｚ１８，Ｚ２ｏ｝， ｛２，３，５，８｝一（２３，２５，３５，２８，３８，５８｝ 一｛Ｚ３，ｚ８，Ｚ９，Ｚ２３，ｌ２４，ｌ２６）， ｛２，３，６，７）一｛２３，２６，３６，２７，３７，６７） 一｛ｌ３，ｌｌ２，Ｚ１３，Ｚｌ７，ｌｌ８，Ｚ２１｝， ｛２，３，６，８｝一｛２３，２６，３６，２８，３８，６８｝ 一｛ｚ３，Ｚ１ｚ，ｌｌ３，ｚ２３，Ｚｚ４，ｚ２７｝， ｛２，３，７，８｝一｛２３，２７，３７，２８，３８，７８｝ 一｛ｌ３，Ｚｌ７，Ｚ１８，ｌ２３，Ｚ２４，Ｚ２８｝， ｛２，４，５，６｝一｛２４，２５，４５，２６，４６，５６｝ 一｛ｌｓ，ｌ８，Ｚ１ｏ，Ｚｌ２，Ｚ１４，Ｚ１ ５｝， ｛２，４，５，７｝一｛２４，２５，４５，２７，４７，５７｝ 一｛Ｚ５，Ｚ８，Ｚｌｏ，Ｚｌ７，Ｚ１９，Ｚ２ｏ｝， ｛２，４，５，８）一｛２４，２５，４５，２８，４８，５８） 一｛ｌ５，ｌ８，Ｚｌ０，ｌ２３，ｌ２５，ｌ２６｝， ｛２，４，６，７｝一｛２４，２６，４６，２７，４７，６７｝ 一｛ｌ５，ｌｌ２，Ｚ１４，ｌｌ７，Ｚ１ ９，Ｚ２１｝， ｛２，４，６，８｝— ｛２４，２６，４６，２８，４８，６８） 一｛ｌｓ，Ｚｌ２，Ｚｌ４，Ｚｚ３，Ｚ２ｓ，ｌ２７）， ｛２，４，７，８｝一｛２４，２７，４７，２８，４８，７８｝ 一｛ｌ５，Ｚ１ ７，ｌ１９，Ｚ２３，Ｚ２５，ｌ２８｝， ｛２，５，６，７）－— ｛２５，２６，５６，２７，５７，６７｝ 一｛Ｚ８，Ｚ１２， １５，ｌ１７，Ｚ２０，Ｚ２１）， ｛２，５，６，８｝＿＋｛２５，２６，５６，２８，５８，６８｝ 一｛Ｚ８，１１２， ｌ ５，ｌ２３， ２６， ２７｝， ｛２，５，７，８）— ｛２５，２７，５７，２８，５８，７８｝ 一｛Ｚ８，ｌｌ２，Ｚ２０，Ｚｚ３，Ｚ２６，Ｚ２８｝， （２，６，７，８｝一｛２６，２７，６７，２８，６８，７８｝ ＝＝＝｛１１２，ｌｌ７，ｌ２１，ｌ２３，Ｚ２７，ｌ２８｝， １２期 许进等：经典Ｒａｍｓｅｙ数ＤＮＡ计算模型（Ｉ）：位序列计算模型 ２０７９ ｛３，４，５，６）一｛３４，３５，４５，３６，４６，５６｝ 一｛Ｚ６，Ｚ９，Ｚｌｏ，Ｚ１３， １４，Ｚ１ ５｝， ｛３，４，５，７｝＿ ｛３４，３５，４５，３７，４７，５７｝ 一｛Ｚ６，Ｚ９，Ｚ１０，Ｚ１８，Ｚ１９，Ｚ２ｏ）， ｛３，４，５，８｝一｛３４，３５，４５，３８，４８，５８｝ 一｛Ｚ６，Ｚ９，Ｚｌｏ，Ｚ２４，Ｚ２５，Ｚ２６｝， ｛３，４，６，７）一｛３４，３６，４６，３７，４７，６７｝ 一｛Ｚ６， ｌ３，Ｚ１４，Ｚ１８，Ｚ１９，Ｚ２ｌ｝， ｛３，４，６，８｝一｛３４，３６，４６，３８，４８，６８｝ 一｛Ｚ６，Ｚ１ ３，ｌ１４，Ｚ２４，Ｚ２５，ｌｚ７｝， ｛３，４，７，８｝— ｛３４，３７，４７，３８，４８，７８｝ 一｛Ｚ６，Ｚ Ｊ８，Ｚ１９，Ｚ２４，Ｚ２５，Ｚ２８）， ｛３，５，６，７｝一｛３５，３６，５６，３７，５７，６７｝ 一｛ｌ９，ｌ１３，Ｚ１；，Ｚ１８，ｌ２０，Ｚ２１｝， ｛３，５，６，８｝一｛３５，３６，５６，３８，５８，６８｝ 一｛Ｚ９，Ｚｌ３，Ｚ１ ５，Ｚ２４，Ｚ２６，Ｚ２７｝， ｛３，５，７，８｝一｛３５，３７，５７，３８，５８，７８｝ ＝｛Ｚ９，ｌｌ８，Ｚ２０， ２４，Ｚ２６，Ｚ２８｝， ｛３，６，７，８｝一｛３６，３７，６７，３８，６８，７８｝ 一｛Ｚ１３，Ｚｌ８，Ｚ２１，Ｚ２４，Ｚ２７， ２８｝， ｛４，５，６，７）一｛４５，４６，５６，４７，５７，６７｝ 一｛Ｚ１ｏ，Ｚｌ４，Ｚｌ ５，Ｚｌ９，Ｚ２０，￡ｚｌ｝， ｛４，５，６，８｝一｛４５，４６，５６，４８，５８，６８｝ 一｛Ｚｌｏ，Ｚｌ ４，ｌｌ５， ２５，Ｚ２６，Ｚ２７）， ｛４，５，７，８｝一｛４５，４７，５７，４８，５８，７８） 一｛Ｚｌ０，Ｚｌ９，ｌｚ０，Ｚ２５，Ｚ２６，Ｚ２８｝， ｛４，６，７，８｝— ｛４６，４７，６７，４８，６８，７８｝ ＝｛Ｚ１４，Ｚ１９，Ｚ２ｌ，Ｚ２５，Ｚ２７，Ｚ２８｝， ｛５，６，７，８｝一｛５６，５７，６７，５８，６８，７８｝ ：＝：｛Ｚｌ５，Ｚ２０，Ｚ２１，Ｚ２６，Ｚ２７，Ｚ２８）． 通过以上３个步骤的操作最后得出的就是我们 所要找的图． ５ 结 论 以上所述的位序列计算模型其核心就是在加位 过程中随时删除非解，这样就大大地减缓了子图数 目增长的速度，从而为较大阶数的Ｒａｍｓｅｙ数求解 找到了一个可行方法．另外，我们利用存储量更大、 运算速度更快的ＤＮＡ计算机求解使得解决部分 Ｒａｍｓｅｙ数变得有了希望，关于运用ＤＮＡ计算的相 关研究，我们将在本文的（Ⅱ）中给出． 致 谢 陈梅同学对本文给予了详细的校对，并发 现其中的一个错误，给予更正．在此表示感谢！ 参 考 文 献 ［１］ Ｒａｄｚｉｓｚｏｗｓｋｉ Ｓ Ｐ．Ｓｍａｌｌ ｒａｍｓｅｙ ｎｕｍｂｅｒｓ．Ｅｌｅｃｔｒｏｎｉｃ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｂｉｎａｔｏｒｉｃｓ Ｄｙｎａｍｉｃａｌ Ｓｕｒｖｅｙ，２００６，１ １：３－３６ Ｅ２］ Ｍｃｋａｙ Ｂ Ｄ．Ｒａｄｚｉｓｚｏｗｓｋｉ Ｓ Ｐ．Ｒ（４，５）一２５．Ｊｏｕｒｎａｌ ｏｆ Ｇｒａｐｈ Ｔｈｅｏｒｙ，１９９５，１９：３０９—３２２ ［３］ Ｍｃｋａｙ Ｂ Ｄ，Ｚｈａｎｇ Ｋ Ｍ．Ｔｈｅ Ｖａｌｕｅ ｏｆ ｔｈｅ Ｒａｍｓｅｙ Ｎｕｍｂｅｒ Ｒ（３，８）．Ｊｏｕｒｎａｌ ｏｆ Ｇｒａｐｈ Ｔｈｅｏｒｙ，１９９２，１６：９９—１０５ ［４］ Ａｄｉｅｍａｎ Ｌ Ｍ．Ｍｏｌｅｃｕｌａｒ ｃｏｍｐｕｔａｔｉｏｎ ｏｆ ｓｏｌｕｔｉｏｎ ｔｏ ｃｏｍｂｉ— ｎａｔｏｒｉａｌ ｐｒｏｂｌｅｍｓ．Ｓｃｉｅｎｃｅ，１９９４，２６６：１０２卜１０２４ ［５３ Ｌｉｕ Ｗ Ｂ，Ｘｕ Ｊ．Ｔｈｅ ｈａｍｉｌｔｏｎｉａｎ ｃｙｃｌｅ ｐｒｏｂｌｅｍ ｂａｓｅｄ ｏｎ ＤＮＡ ｃｏｍｐｕｔｉｎｇ／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ４ｔｈ Ａｓｉａ—。Ｐａｃｉｆｉｃ Ｃｏｎｆｅｒ—＿ ｅｎｃｅ ｏｎ Ｓｉｍｕｌａｔｅｄ Ｅｖｏｌｕｔｉｏｎ ａｎｄ Ｌｅａｒｎｉｎｇ．２００２，１：３１３－３１７ ［６］ Ｍｏｒｉｍｏｔｏ Ｎ，Ａｒｉｔａ Ｍ，Ｓｕｙａｍａ Ａ．Ｓｏｌｉｄ—ｐｈａｓｅ ＤＮＡ ｓｏｌｕ— ｔｉｏｎ ｔｏ ｔｈｅ ｈａｍｉｌｔｏｎｉａｎ ｐａｔｈ ｐｒｏｂｌｅｍ．Ｄ１ＭＡＣＳ，Ｓｅｒｉｅｓ ｉｎ Ｄｉｓｃｒｅｔｅ Ｍａｔｈｅｍａｔｉｃｓ ａｎｄ Ｔｈｅｏｒｅｔｉｃａｌ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ， １９９９，４８：１９３—２０６ ［７］ Ｏｕｙａｎｇ Ｑ ｅｔ ａ１．ＤＮＡ ｓｏｌｕｔｉｏｎ ｏｆ ｔｈｅ ｍａｘｉｍａｌ ｃｌｉｑｕｅ ｐｒｏｂ— ｌｅｍ．Ｓｃｉｅｎｃｅ，１９９７，２７８：４４６—４４９ ［８］ Ｐａｎ Ｌ Ｑ，Ｌｉｕ Ｙ Ｃ ｅｔ ａ１．Ａ ｓｕｒｆａｃｅ—ｂａｓｅｄ ＤＮＡ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔｈｅ ｍａｘｉｍａｌ ｃｌｉｑｕｅ ｐｒｏｂｌｅｍ．Ｃｈｉｎｅｓｅ Ｊｏｕｒｎａｌ ｏｆ Ｅｌｅｃｔｒｏｎｉｃｓ， ２００２，１１（４）：４６９—４７１ ［９］ Ｘｕ Ｊｉｎ，Ｑｉａｎｇ Ｘｌａｏ－Ｌｉ ｅｔ ａ１．Ａｎ ｕｎｅｎｕｍｅｒａｔｉｖｅ ＤＮＡ ｃｏｍｐｕ— ｔｉｎｇ ｍｏｄｅｌ ｆｏｒ ｖｅｒｔｅｘ ｃｏｌｏｒｉｎｇ ｐｒｏｂｌｅｍ．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｃｏｍｐｕｔｅｒ，２００９，ｔｏ ａｐｐｅａｒ ［１０］ Ｌｉｕ Ｗ Ｂ，Ｘｕ Ｊ．Ａ ＤＮＡ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔｈｅ ｇｒａｐｈ ｃｏｌｏｒｉｎｇ ｐｒｏｂｌｅｍ．Ｊｏｕｒｎａｌ ｏｆ Ｃｈｅｍｉｃａｌ Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｃｏｍｐｕｔｅｒｓ， ２００２，４２（５）：¨７６—１ｌ７８ ［１１］ Ｌｉｕ Ｙ Ｃ，Ｐａｎ Ｌ Ｑ，Ｘｕ Ｊ ｅｔ ａ１．ＤＮＡ ｓｏｌｕｔｉｏｎ ｏｆ ｇｒａｐｈ ｃｏｌｏ— ｒｉｎｇ ｐｒｏｂｌｅｍ．Ｊｏｕｒｎａｌ ｏｆ Ｃｈｅｍｉｃａｌ Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅｓ，２００２，４２（３）：５２９－５３４ ［１２］ Ｙｉｎ Ｚ Ｘ，Ｚｈａｎｇ Ｆ Ｙ，Ｘｕ Ｊ．Ａ Ｃｈｉｎｅｓｅ ｐｏｓｔｍａｎ ｐｒｏｂｌｅｍ ｂａｓｅｄ ｏｎ ＤＮＡ ｃｏｍｐｕｔｉｎｇ．Ｊｏｕｒｎａｌ ｏｆ Ｃｈｅｍｉｃａｌ Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅｓ。２００２，４２（２）：２２４—２２４ ［１３］ Ｙｉｎ Ｚ Ｘ，Ｚｈａｎｇ Ｆ Ｙ，Ｘｕ Ｊ．Ｔｈｅ ｇｅｎｅｒａｌ ｆｏｒｍ ｏｆ ０－１ ｐｒｏ— ｇｒａｍｍｉｎｇ ｐｒｏｂｌｅｍ ｂａｓｅｄ ｏｎ ＤＮＡ ｃｏｍｐｕｔｉｎｇ．Ｂｉｏｓｙｓｔｅｍｓ， ２００３，７０（１）：７３—７９ ［１４］ Ｙｉｎ Ｚｈｉ—Ｘｉａｎｇ，Ｚｈａｎｇ Ｆｅｎｇ—Ｙｕｅ，Ｘｕ Ｊｉｎ．０－１ ｐｌａｎｎｉｎｇ ｐｒｏｂ— ｌｅｍ ｂａｓｅｄ ｏｎ ＤＮＡ ｃｏｍｐｕｔｉｎｇ．Ｊｏｕｒｎａｌ ｏｆ Ｅｌｅｃｔｒｏｎｉｃｓ＆Ｉｎ— ｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ，２００３，２５（１）：６２—６６（ｉｎ Ｃｈｉｎｅｓｅ） （殷志祥，张凤月，许进．０－１规划问题的ＤＮＡ计算．电子与 信息学报，２００３，２５（１）：６２—６６） ［１５］ Ｈａｒａｒｉ Ｆ．Ｇｒａｐｈ Ｔｈｅｏｒｙ．Ｒｅａｄｉｎｇ，Ｍａｓｓ：Ａｄｄｉｓｏｎ—Ｗｅｓｌｅｙ， １９６９ （哈拉里著，李慰萱译．图论．上海：上海科技出版社，１９８０） ［１６］ Ｂｏｎｄｙ Ｊ Ａ，Ｍｕｒｔｙ Ｕ Ｓ Ｒ．Ｇｒａｐｈ Ｔｈｅｏｒｙ ｗｉｔｈ Ａｐｐｌｉｃａｔｉｏｎｓ． Ｌｏｎｄｏｎ：Ｔｈｅ Ｍａｃｍｉｌｌａｎ Ｐｒｅｓｓ Ｌｔｄ，１ ９７６ ２０８０ 计 算 机 学 报 ２００８年 ＸＵ Ｊｉｎ，ｂｏｒｎ ｉｎ １９５９，ｐｒｏｆｅｓｓｏｒ， Ｐｈ．Ｄ．ｓｕｐｅｒｖｉｓｏｒ．Ｈｉｓ ｒｅｓｅａｒｃｈ ｉｎｔｅｒ— ＦＡＮ Ｙｕｅ—Ｋｅ，ｂｏｒｎ ｉｎ １９５９，Ｐｈ．Ｄ．．Ｈｉｓ ｒｅｓｅａｒｃｈ ｉｎｔｅｒ－ ｅｓｔｓ ｉｎｃｌｕｄｅ ＤＮＡ ｃｏｍｐｕｔｉｎｇ ａｎｄ ＤＮＡ ｃｏｍｐｕｔｅｒ，ｇｒａｐｈ ｔｈｅ— ｏｒｙ ｅｔｃ． ｅｓｔｓ ｉｎｃｌｕｄｅ ＤＮＡ ｃｏｍｐｕｔｉｎｇ ａｎｄ ＤＮＡ ｃｏｍｐｕｔｅｒ，ｎｅｕｒａｌ ｎｅｔｗｏｒｋｓ，ｇｅｎｅｔｉｃ ａｌ— ｇｏｒｉｔｈｍｓ，ｇｒａｐｈ ｔｈｅｏｒｙ ｅｔｃ．