第３３卷第２期 计 算 机 学 报 Ｖｏ１．３３ Ｎｏ．２ ２０１０年２月 ＣＨＩＮＥＳＥ ＪＯＵＲＮＡＬ ＯＦ ＣＯＭＰＵＴＥＲＳ Ｆｅｂ．２０１０ 图同构问题的决策神经网络模型 南晋华 齐 （华中科技大学控制科学与工程系 摘要 图的同构问题是研究两个图之问相互关系范畴．这对图表面上似乎不同，但本质上完全相同．由于图的同 构问题在以系统建模、电路布线等众多问题中有直接的应用，因而，吸引了不少的学者从事这方面的研究．该文意 在建立一种局域连接的、模拟人脑决策思维模式的、可用于优化信息处理的神经网络模型．该文在过去建立求解图 的同构问题人工神经网络模型的基础上，拟应用人脑决策局域化的思想，提出了一种新的用于图的同构问题的人 工神经网络模型．该模型中增加了一个自然的约束条件，加快了运算速度． 关键词图；同构；决策；神经网络 中图法分类号ＴＰ３０１ ＢＯＩ号：１０．３７２４／ＳＰ．Ｊ．１０１６．２０１０．００３００ Ｔｈｅ Ｄｅｃｉｓｉｏｎ—Ｍａｋｉｎｇ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋｓ Ｍｏｄｅｌ 欢ｆｏｒ Ｓｏｌｖｉ武 汉 ｎｇ ｔｈｅ Ｇｒａｐｈ Ｉｓｏｍｏｒｐｈｉｓｍ Ｐｒｏｂｌｅｍ 船 ∞ ＮＡＮ Ｊｉｎ－Ｈｕａ ＱＩ Ｈｕａｎ （Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｎｔｒｏｌ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｈｕａｚｈｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｗｕｈａｎ ４３００７４） Ａｂｓｔｒａｃｔ Ｔｈｅ ｇｒａｐｈ ｉｓｏｍｏｒｐｈｉｓｍ ｐｒｏｂｌｅｍ ｉｓ ｔｏ ｓｔｕｄｙ ｔｈｅ ｒｅｌａｔｉｏｎｓｈｉｐ ｂｅｔｗｅｅｎ ｔｗｏ ｇｒａｐｈｓ ｗｈｉｃｈ ｓｅｅｍ ｔＯ ｂｅ ｄｉｆｆｅｒｅｎｔ，ｂｕｔ ｅｓｓｅｎｔｉａｌｌｙ ｉｄｅｎｔｉｃａ１．Ｔｈｉｓ ｐｒｏｂｌｅｍ ｃａｎ ｂｅ ｗｉｄｅｌｙ ｕｓｅｄ ｉｎ ｔｈｅ ｓｙｓ— ｔｅｒｎ ｍｏｄｅｌｉｎｇ，ｃｉｒｃｕｉｔ ｗｉｒｉｎｇ ａｎｄ ｍａｎｙ ｏｔｈｅｒ ｉｓｓｕｅｓ．Ｔｈｅｒｅｆｏｒｅ，ｔｈｉｓ ｐａｐｅｒ ｉｓ ａｉｍｅｄ ｔＯ ｅｓｔａｂｌｉｓｈ ａ ｋｉｎｄ ｏｆ ｎｅｕｒａｌ ｎｅｔｗｏｒｋｓ ｍｏｄｅｌ ｔｈａｔ ａｒｅ ｏｆ ｌｏｃａｌ—ｃｏｎｎｅｃｔｉｏｎ．ｓｉｍｕｌａｔｉｏｎ ｈｕｍａｎ’Ｓ ｄｅｃｉｓｉｏｎ－ｍａｋｉｎｇ ｔｈｉｎｋｉｎｇ，ａｎｄ ａｌｓｏ ｃａｎ ｂｅ ａｐｐｌｉｅｄ ｔｏ ｓｏｌｖｅ ｔｈｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｆｏｒ ｉｎｆｏｒｍａｔｉｏｎ．Ｔｈｅ ａｕｔｈｏｒｓ ｕｓｅ ａ ｎａｔｕｒａｌ ｃｏｎｓｔｒａｉｎｔ ｉｎ ｏｒｄｅｒ ｔＯ ｓｐｅｅｄ ｕｐ ｔｈｅ ｏｐｅｒａｔｉｏｎｓ，ａｎｄ ｔｈｅｎ ｐｒｏｐｏｓｅｄ ａ ｎｅｗ ａｒｔｉｆｉｃｉａｌ ｎｅｕｒａｌ ｎｅｔｗｏｒｋ ｍｏｄｅｌ ｔｏ ｓｏｌｖｅ ｔｈｅ ｇｒａｐｈ ｉｓｏｍｏｒｐｈｉｓｍ ｐｒｏｂｌｅｍ。 Ｋｅｙｗｏｒｄｓ ｇｒａｐｈ；ｉｓｏｍｏｒｐｈｉｓｍ；ｄｅｃｉｓｉｏｎ—ｍａｋｉｎｇ；ｎｅｕｒａｌ ｎｅｔｗｏｒｋｓ ｍｏｄｅｌ 有定论，即它究竟是Ｐ问题还是ＮＰ问题？目前关 １ 引 言 于图的同构问题的判定性算法不少，有诸如经典判 定算法口 ］、对在实际工程中有着广泛应用的图的拟 图的同构问题不仅是数学，特别是图论自身学 同构问题算法［９ 、进化计算方法［１ 、人工神经网络 科研究中的一个核心内容，而且具有良好的应用背 求解算法口 。。 以及最新的ＤＮＡ计算模型＿１ 刎等． 景，在工程技术领域，特别是大系统建模、电路设计、 在经典的图同构算法中，在此主要介绍两种算法，一 机械设计、模式识别以及系统建模中有着广泛的应 种是所谓的矢量列表法，另一种是回溯算法． 用．对于系统建模，如果能够证明需建模型与已知模 研究图的同构问题，一个重要的环节是如何表 型同构，则可以节省大量人力物力财力．多数学者认 示图的信息．在这个问题上，Ｃｏｍｅｉｌ与Ｈｆｆｍａｎ等人 为图的同构判定问题属于ＮＰ－完全问题．但至今没 曾引入“模块”这一概念来表示各个顶点及其邻接顶 收稿日期：２００９—０７—０６；最终修改稿收到日期：２００９ １１—０６．南晋华，女，１９７２年生，博士，主要研究方向为系统工程、决策支持系统．齐 欢 （通信作者），男，１９４８年生，博士，教授，主要研究领域为系统分析与建模等．Ｅ－ｍａｉｌ：ｑｉｈｕａｎ＠ｍａｉｌ．ｈｕｓｔ．ｅｄｕ．ｅｎ． ２期 南晋华等：图同构问题的决策神经网络模型 ３０１ 点信息．在此基础上Ｒｉａｚ提出一种有效的判定图同 神经网络方法．有别于其它的启发式及关联式算法， 该方法巧妙设计了神经计算程序，通过一能量最小 化匹配处理减小了搜索空间ｒ２ ．本文在已有工作的 基础上，通过加入顶点邻域的思想，将顶点度加入到 能量函数之中，进而加入到网络的运行方程之中，使 网络的运行速度得以加快，自然也减少了一些局部 构问题的算法——矢量列表法，即把各顶点所代表 的信息用模块表示，所有模块组合在一起构成矢量 列表．设计算法依次比较各模块，最终得到同构信 息．并在此基础上建立了判定图同构的矢量列表法． 图同构的回溯算法是一种利用Ｋ一算子表示图 结构，然后通过比对序列求解图同构映射的方法． 极小值，从而建立了一种新的求解图的同构问题的 神经网络算法． Ｋ一算子这一概念最初由Ｋｒｉｄｅ等人提出，文献［１１— １２］对这一算法进行了深入的探讨和改进，对这一方 法进行了系统的论述，并给出了适合计算机求解的 算法．虽然通过仿真结果证明了这种回溯算法的可 行性，但是要严格地给出时间复杂度估计不是很容 易的事情．尽管如此，这种试图从图的结构上来判定 同构性的思想无疑是值得借鉴的，它通过引入算子， 把给定图表示成字符串的形式，然后通过回溯模式 识别，逐步求得可能的同构序列，最终得到两图是否 同构的结论． 遗传算法由Ｈｏｌｌａｎｄ等人于２Ｏ世纪６Ｏ年代末 提出，模拟生化机制进行优化计算［２ ．图的同构问 题稍加扩充，引伸成具有一定应用背景的所谓的拟 同构的概念．当两个图相近程度达到要求误差范围 之内时，称两个图为拟同构． 图的拟同构的一个很重要的应用就是在模式识 别中，通常把事物的特征及其相互作用表示成赋权 图．该算法把一个图同构的判定问题分解在ＧＡ中 进行求解．通过引入初始匹配，进化速度加快，用顶 点映射来代替常规算法中的行列交换，鉴于ＧＡ求 解随机搜索问题的有效性，在图的拟同构判定中，该 算法也就显得十分有效． ＤＮＡ计算是一种以ＤＮＡ分子与相关生物酶 为基本材料，以某些生化反应为基础的一种全新的 计算模式．利用ＤＮＡ特殊的双螺旋结构和碱基互 补规律进行信息编码，把运算对象映射成ＤＮＡ分 子链，生成数据池，然后把数据运算高度并行地映射 成ＤＮＡ的可控生化过程，最后利用分子生物技术， 检测出需要的结果．在利用ＤＮＡ计算求解图论中 的问题这一领域已经取得了不少的成果，文献１－１９］ 中利用粘贴ＤＮＡ计算模型建立求解图同构问题的 ＤＮＡ计算模型．文献Ｅｚ２；利用ｋ一臂ＤＮＡ计算模型 建立了另外一种求解图同构问题的模型． 应用Ｈｏｐｆｉｅｌｄ网络研究图的同构问题始于马 颂德［１ 、陈国良ｒ１ 等人．其后，有一些学者利用神 经网络模型来研究图的同构问题，如Ｂｒｉｊｎｅｓｈ与 Ｆｒｉｔｚ提出了一种解决严格与非严格赋权图同构的 ２ 图的同构 两个表面上似乎很不相同的图，本质上可能是 完全一样的，或者说，这两个图是同构的．如图１中 所示的三组图：Ｍ与Ｍ ；Ｈ与Ｈ ；Ｇ与Ｇ ，它们表 面上不同，但实际上每组图之间是同构的．其中的图 Ｍ就是著名的Ｐｅｔｅｒｓｅｎ图．在本文中分别用Ｖ（Ｇ）， Ｅ（Ｇ）分别表示图Ｇ的顶点集和边集． Ｍ Ｍ Ｈ Ｈ １ ３ ６ ７ ４ ３ ２， ５・４，８ Ｇ Ｇ １三组同构的图 本文所言之图皆指无自环、无重边的有限无向 简单图，用 （Ｇ）、Ｅ（Ｇ）（或 ，Ｅ）分别表示图Ｇ的 顶点集和边集，两个图Ｇ与Ｇ ，称为是同构的，如果 存在一个从 （Ｇ）到Ｖ（Ｇ ）之间的保持相邻性的１—１ 映射，换言之，存在１—１映射： ：Ｖ（Ｇ）一 （Ｇ ），且 Ｖ ，７２∈Ｖ（Ｇ），ＵＶ∈Ｅ（Ｇ）当且仅当 （ ） （ ）∈ Ｅ（Ｇ ），称 是从Ｇ到Ｇ 的一个同构映射．全体从Ｇ 到Ｇ 的同构映射构成的集合记作 （Ｇ，Ｇ ）． ３０２ 计 算 机 学 报 ３模型及算法 设Ｇ与Ｇ 是两个同构的图，Ｖ（Ｇ）一｛ｚ。， ２，…，ｚｐ｝，Ｖ（Ｇ ）一｛Ｙｌ，Ｙ２，…，Ｙｐ）， ∈Ｉ（Ｇ，Ｇ ）且 满足 ａ（ｘｉ）一Ｙｔ，ｉ，Ｚ＝１，２，…，Ｐ （１） 置（ ，Ｙ ）为网络的神经元，它表示同构映射 把图Ｇ的顶点 映射到图Ｇ 的顶点Ｙ ．显然，由此 而构成的神经网络共有Ｐ×Ｐ个神经元．当网络稳 定时，用口 表示神经元（ ｉ，３， ）的输出，定义： （２． 一１ｆ ０，否则 Ｙ ’） 例如，图１中第三组中所示的两个图Ｇ和Ｇ 是同构 的，其中一个同构映射为 ，１ ２ ３ ４ ５ ６ ７ ８、 盯 Ｉ１，７ ４，６，５，３，８，２ 由同构映射盯可构成一个Ｐ×Ｐ阶矩阵Ｗ一 （ ） ，称为置换矩阵，如图１中两个８一阶的３一正 则图Ｇ和Ｇ ， 是一个保持相邻性的从Ｖ（Ｇ）到 Ｖ（Ｇ ）的同构映射，由式（２）可得 Ｖ ＝ 下面来分析一下 的一些基本性质： 由 是１－ｌ映射，保证了 的每一行、每一列有 且仅有一个元素为１，而其余的元素均为０．由此 获得 ∑ 一１，ｉ一１，２，…，Ｐ （３） ｌ＝１ 户 ∑ “一１， １—１，２，…，Ｐ （４） ｉ一１ 设图Ｇ与Ｇ 的相邻矩阵分别为Ａ与Ａ ，Ａ一 （口 ） ，Ａ 一（口 』） × ，于是，由盯可保持相邻性 有：对于Ｖｚ ， ∈ （Ｇ）， ｆ巧∈Ｅ（Ｇ）ｔＣａ（ｉ）ａ（ｊ）一ｌｍ∈Ｅ（Ｇ … （ｌ 硭Ｅ（Ｇ）ＣＣａ（ｉ）ａ（ｊ）：＝：ｌｍ Ｅ（Ｇ ）． ｂ 即 基于式（２）和式（６），有 （ 一ｎｆｔ ）７Ｊｉｌ Ｊ 一０，ｉ，Ｊ，Ｚ， 一１，２，…，Ｐ（７） 令 （Ｇ）一｛ｚ１，ｚ２，…，Ｘ ）．设ｚ ∈Ｖ（Ｇ），用 Ｆ（ｘ ）来表示顶点Ｘ 在图Ｇ中的邻域，用１ Ｏ Ｏ Ｏ ０ Ｏ ０ Ｏ ｄｉ— ＩＦ（ｘ ）Ｉ来表示顶点 ０ 的度数，ｉ一１，２，…，Ｐ．我们 Ｏ Ｏ Ｏ ０ Ｏ ０ １ 约定，一个图Ｇ的度序列，记做丌（Ｇ），是指满足单 Ｏ Ｏ Ｏ Ｏ Ｏ １ Ｏ Ｏ 调递增的度序列： ０ ０ ｌ ０ Ｏ Ｏ Ｏ Ｏ ７ｒ（Ｇ）一０ （ ｌ，Ｏ ｄ２，…，Ｏ Ｏ ｄ。），１ Ｏ Ｏ ０ 其中， ０ Ｏ Ｏ １ ０ Ｏ Ｏ ０ ｄ１ ０ ｄ２ １ … Ｏ Ｏ ｄ。，Ｏ Ｏ ０ Ｏ 同样，Ｖ（Ｇ ）一｛３， ， ｚ，０ …，Ｏ ３，Ｏｐ），且令ｄ （ Ｏ ０ ０ Ｊｌ ）＝０ ＝＝ｄ：来 表示图Ｇ 中顶点Ｙ 的度数， 一１，２，…，Ｐ．自然，两 个图Ｇ与Ｇ 是同构的，它们的度序列也应该相同． 对于神经元（ｚ ，Ｙ，）而言，若口∈ｊ（Ｇ，Ｇ ），且 ａ（ｘ ）一Ｙ， （８） 则有 ｄ 一ｄ： （９） 基于式（２）、（８）和式（９），有 （ 一ｄ：） “ “一０，ｉ，Ｚ—ｌ，２，…，Ｐ （１０） 把满足式（３）、（４）、（７）和式（８）的关于图Ｇ与图Ｇ 的０—１矩阵 的全体集合记做Ｐ（Ｇ，Ｇ ），于是有如 下定理． 定理１． 设图Ｇ与Ｇ 是两个同构的Ｐ（三三＝２）阶 图，则Ｉ（Ｇ，Ｇ ）与Ｐ（Ｇ，Ｇ ）通过式（２）等价． 证明． 对于任一同构映射 ∈Ｉ（Ｇ， ），令 （Ｇ）一｛ｚ１，Ｘ２，…，Ｘｐ），Ｖ（Ｇ ）一｛Ｙ１，Ｙ２，…，Ｙｐ），且 ａ（ｘ ）一Ｙｆ，ｉ，Ｚ＝１，２，…，Ｐ， 令 ｆ １， ａ（ｘ｛）：＝： ｆ ？Ｐｉｔ一１ｌ，０，否则 否则 ’ 则由Ｖｉ 构成的矩阵Ｗ一（ ） 显然满足式（２）、 （４）、（７）和式（１０）．因此，唯一地有 ∈Ｐ（Ｇ，Ｇ ）． 反过来，对于ＶＶ ∈Ｐ（Ｇ，Ｇ ），由于 满足 式（３）和式（４），因此，每行每列有且只有一个元素为 １，其余元素皆为０．当 ＝＝＝１，ｄ（ｚ ）一 （ｉ，ｚ一１， ２，…，ｐ），则由式（３）、（４）知， 是从 （Ｇ）到Ｖ（Ｇ ） 之间的一个１—１映射．下面，来证明 是保持相邻性 的１－１映射．对于Ｙｘ ， ６Ｖ（Ｇ），如果 （ｉ）ｚ ，∈Ｅ（Ｇ），且ａ（ｘ ）一Ｙｆ，ａ（ｘ ）一 ，则有 ａ ，一１， “一 ， ＝＝：１，代入式（７），有 （１一口： ）×１×１—０， ２期 南晋华等：图同构问题的决策神经网络模型 ３０３ 此即 ａ（ｘｆ） （ｚ ）一Ｙ Ｙ ∈Ｅ（Ｇ ）． （ｉｉ）ｚ ｚ， Ｅ（Ｇ），且ａ（ｘ ）一Ｙｚ，ａ（ｘｉ）一Ｙ ，则 ａ ，一０， “： ：１，代入式（７）得到 ｎ： 一０， 从而推得 ａ（ｘ ）ａ（ｘｊ）一Ｙ 硭Ｅ（Ｇ ）． 综合（ｉ）、（ｉｉ），证明了 是保持相邻性的１一ｌ映 射，故知 唯一地找到一个ｄ∈Ｉ（Ｇ，Ｇ ），从而本定 理获证． 证毕． 在上述工作的基础上，现在来建立具体的能量 函数．与已有的结果相比，此能量函数增加了顶点的 邻域性，即将图顶点度数作为一个“加速参数”加人 到了能量函数之中，进而导入网络的运行方程． 设Ｇ与Ｇ 表示两个同构图，Ｖ（Ｇ）一｛ｚ ， ｚ２，…，ｚ ），Ｖ（Ｇ ）一｛Ｙ１，Ｙｚ，…，Ｙ。｝，置神经元为 （ｚ ，Ｙ，），表示从图Ｇ中的顶点到图Ｇ 的同构映射， 由此而构造的能量函数为 Ｅ一 壹（奎 一１）。＋ Ｂ∑ｎ（ 一１） ＋ ｃ∑∑∑∑ｊ口ｉ一１ ｌ＝１ Ｊ一１ ｍ １ 一。： Ｉ Ｖｉｌ ＋ ∑∑ｆ ｄ — ：ｆ ， 其中（口 ，） ，（口 ） × 分别表示 阶图Ｇ和Ｇ 的邻 接矩阵．其中Ｅ的第１项称为行约束项，当且仅当 中的每一行只有一个１，其余元素为０时，此项为 ０；第２项为列约束，当且仅当每列中只有一个元素 为１，且其余元素为０时，此项为０；第３项为惩罚 项，当且仅当１—１映射 保持相邻性时，此项为０； 第４项为顶点度数惩罚项，当且仅当映射中对应顶 点度数相同时，此项为０． 神经元（ｚ ， ）的运行方程为 ｄ一 ￡ ａ “（￡）’… ｚ—ｌ＇２，…，…’’ …… ） 进而导出 警一Ａ（ 一１）一Ｂ（ 一１）一 ｃ（∑∑ —ｎ Ｉ ）＋ Ｄ（∑∑Ｊ ｄ 一ｄ ） （１２） Ｖｉｌ一丢（１＋ｔａｎｈ警） （１３） 其中，“ （ ）表示神经元（五，ｙ，）在ｔ时刻的状态，Ａ， Ｂ，ｃ，Ｄ以及』９表示实验参数．网络的权值Ｗ ， 和 偏置电流Ｊ 为 ｆＷ 一一Ａ如－－Ｂ３Ｌ ～ｃｌ口 一日 Ｊ—Ｄｌｄ。一日；Ｉ Ｉｆ 一一（Ａ＋Ｂ） ｉ，Ｊ，Ｚ，ｍ一１，２，…，Ｐ （１４） 其中， 一，』１ ０， ｉ≠Ｊ 一 （１５） 基于上述，现给出本文提出求解图的同构问题 人工神经网络模型的具体算法步骤： １．设置￡一０以及Ａ，Ｂ，Ｃ，Ｄ； ２．读人图Ｇ与Ｇ 的邻接矩阵（。 ）（ｉ，Ｊ＝１，２，…，户）， （口 ）（ｚ，优一１，２，…， ）； ３。计算神经元之间的权重Ｗｉ 和输入偏置电流Ｉ ４．ｕ （￡）（ｉ，ｚ一１，２，…，户）的初值在。附近随机产生； ５．计算 ｆ（ ）（ ，ｚ一１，２，…，ｐ）， 为实验参数； ６．利用神经元运行方程计算Ａｕ （ｆ）（ ，ｚ一１，２，… ） Ａｕ （￡）一∑∑Ｗｉｌ，ｊｍ ＋Ｉ ７．根据一阶Ｅｕｌｅｒ法计算Ｕ （￡＋１）， ¨ （￡＋１）一 ｌ＋Ａｕ （￡）Ａｔ，ｉ，￡一１，２，…，Ｐ； ８．若系统达到平衡，终止，否则，转步５． ４ 结 论 本文对图论中的图同构问题算法求解进行了较 为系统的讨论，评述了在图的同构中不同问题的各 种常规的算法，以及在系统优化、模式识别中有着广 泛应用的同构问题的非常规算法．作为图论中有着 广泛应用的一个重要的分支，我们给出的算法有着 很大的现实意义与实用性． 参 考 文 献 ［１３ Ｗｅｓｔ Ｄ Ｂ．Ｉｎｔｏｒｄｕｃｔｉｏｎ ｔｏ Ｇｒａｐｈ Ｔｈｅｏｒｙ（２ｎｄ Ｅｄｉｔｉｏｎ）．ＮＪ： Ｐｒｅｎｔｉｃｅ Ｈａｌｌ Ｕｐｐｅｒ Ｓａｄｄｌｅ Ｒｉｖｅｒ，２００１（ｉｎ Ｃｈｉｎｅｓｅ） （韦斯特．图论导引（第２版）．李建中，骆吉洲译．北京：机 械工业出版社，２００７） Ｅｚｌ Ｘｕ Ｊｕｎ—Ｍｉｎｇ．Ｇｒａｐｈ Ｔｈｅｏｒｙ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎ．Ｈｅｆｅｉ：Ｕｎｉ— ｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ ｏｆ Ｃｈｉｎａ Ｐｒｅｓｓ，２００４（ｉｎ Ｃｈｉｎｅｓｅ） （徐俊明．图论及其应用．合肥：中国科技大学出版社， ２００４） Ｅ３］Ｗａｎｇ Ｓｈｕ—Ｈｅ．Ｇｒａｐｈ Ｔｈｅｏｒｙ．Ｂｅｉｊｉｎｇ：Ｓｃｉｅｎｃｅ Ｐｒｅｓｓ，２００７ （ｉｎ Ｃｈｉｎｅｓｅ） （王树禾．图论．北京：科学出版社，２００７） ［４］Ｒｉａｚ Ｋ，Ｋｈｉｙａｌ Ｍ Ｓ Ｈ，Ａｒｓｈａｄ Ｍ．Ａｎ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍ ｔｏ ｄｉｓｃｏｖｅｒ ｇｒａｐｈ ｉｓｏｍｏｒｐｈｉｓｍ／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ７ｔｈ Ｉｎｔｅｒ— ｎａｔｉｏｎａｌ Ｍｕｌｔｉ Ｔｏｐｉｃ Ｃｏｎｆｅｒｅｎｃｅ（ＩＮＭＩＣ ２００３）．Ｐａｋｉｓｔａｎ， ２００３：３９６—３９９ ３０４ 计 算 机 学 报 ２０１０正 Ｅ５］ Ｂａｙｅｒ Ｔ，Ｊｏｎｅｓ Ｗ，Ｍｉｔｅｈｅｌ Ｓ．Ｌｉｎｅａｒ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｉｓｏｍｏｒ— ｐｈｉｓｍ ｏｆ ｍａｘｉｍａｌ ｏｕｔｅｒｐｌａｎａｒ ｇｒａｐｈｓ．Ｊｏｕｒｎａｌ ｏｆ ｔｈｅ Ａｓｓｏｅｉ— ａｔｉｏｎ ｆｏｒ Ｃｏｍｐｕｔｉｎｇ Ｍａｃｈｉｎｅｒｙ，１９７９，２６：６０３—６１０ ［６３ Ｍｉｔｃｈｅｌｌ Ｓ，Ｂｅｙｅｒ Ｔ，Ｊｏｎｅｓ Ｗ．Ｌｉｎｅａｒ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｉｓｏｍｏｒ— ｐｈｉｓｍ ｏｆ ｍａｘｉｍａｌ ｏｕｔｅｒｐｌａｎａｒ ｇｒａｐｈｓ．Ｊｏｕｒｎａｌ ｏｆ ｔｈｅ ＡＣＭ （ＪＡＣＭ），１９７９，２６（４）：６０３—６１０ ［７］ Ｓｒａｂａｎｉ Ｓ Ｇ，Ｂｈａｂａｎｉ Ｐ Ｓ．Ａ ｓｉｍｐｌｅ ｏ（１ｏｇ Ｎ）ｔｉｍｅ ｐａｒａｌｌｅｌ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔｅｓｔｉｎｇ ｉｓｏｍｏｒｐｈｉｓｍ ｏｆ ｍａｘｉｍａｌ ｏｕｔｅｒｐｌａｎａｒ ｇｒａｐｈｓ．Ｊｏｕｒｎａｌ ｏｆ Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｒｉｂｕｔｅｄ Ｃｏｍｐｕｔｉｎｇ， １９９９，５６（２）：１４４—１５５ ［８］ Ｌｉ Ｆｅｎｇ，Ｓｈａｎｇ Ｈｕｉ—Ｌｉａｎｇ．Ａｎ Ｉｓｏｍｏｒｐｈｉｓｍ Ｔｅｓｔｉｎｇ ａｌｇｏ— ｒｉｔｈｍ ｆｏｒ ｄｉｒｅｃｔｅｄ ｇｒａｐｈｓ：Ｔｈｅ ｉｎ—ｄｅｇｒｅｅ ａｎｄ ｏｕｔ—Ｄｅｇｒｅｅ ｓｅ～ ｑｕｅｎｅｅ ｍｅｔｈｏｄ．Ｊｏｕｒｎａｌ ｏｆ Ａｐｐｌｉｅｄ Ｓｃｉｅｎｃｅｓ，２００２，２０（３）： ２５８—２６２（ｉｎ Ｃｈｉｎｅｓｅ） （李锋，商慧亮．有向图的同构判定算法．应用科学学报， ２００２，２０（３）：２５８—２６２） Ｅｇ－Ｉ Ｋｒｉｄｅｒ Ｌ．Ａ ｆｌｏｗ ａｎａｌｙｓｉｓ ａｌｇｏｒｉｔｈｍ．Ｊｏｕｒｎａｌ ｏｆ ｔｈｅ ＡＣＭ， １９６４，ｌ１（４）：４２９－４３６ Ｅｌｏ３ Ｒｅａｄ Ｒ，Ｃｏｒｎｅｉｌ Ｄ．Ｔｈｅ ｇｒａｐｈ ｉｓｏｍｏｒｐｈｉｓｍ ｄｉｓｅａｓｅ．Ｊｏｕｒｎａｌ ｏｆ Ｇｒａｐｈ Ｔｈｅｏｒｙ，１９７７，１（１）：３３９—３６３ ［１１］ Ｂｅｒｚｔｉｓｓ Ａ Ｔ，Ｗａｔｋｉｎｓ Ｒ Ｐ．Ｄｉｒｅｃｔｅｄ ｇｒａｐｈｓ ａｎｄ ａｕｔｏｍａｔｉｃ ｆｌｏｗｃｈａｒｔｉｎｇ／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ４ｔｈ Ａｕｓｔｒａ１．Ｃｏｍｐ．Ｃｏｎ— ｆｅｒｅｎｃｅ Ａｄｅｌａｉｄｅ．Ｎｅｔｌｅｙ，Ｓｏｕｔｈ Ａｕｓｔｒａｌｉａ：Ｇｒｉｆｆｉｎ Ｐｒｅｓｓ， １９６９：４９５—４９９ ［１２］ Ｂｅｒｚｔｉｓｓ Ａ Ｔ．Ｄａｔａ Ｓｔｒｕｃｔｕｒｅｓ：Ｔｈｅｏｒｙ ａｎｄ Ｐｒａｃｔｉｃｅ．Ｎｅｗ Ｙｏｒｋ—Ｌｏｎｄｏｎ：Ａｃａｄｅｍｉｃ Ｐｒｅｓｓ，１ ９７１ ［１３３ Ｗａｎｇ Ｙ Ｋ，Ｆａｎ Ｋ Ｃ，Ｈｏｒｎｇ Ｊ Ｔ．Ｇｅｎｅｔｉｃ－ｂａｓｅｄ ｓｅａｒｃｈ ｆｏｒ ｅｒｒｏｒ－ｃｏｒｒｅｃｔｉｎｇ ｇｒａｐｈ ｉｓｏｍｏｒｐｈｉｓｍ．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｓｙｓｔｅｍｓ，Ｍａｎ，ａｎｄ Ｃｙｂｅｒｎｅｔｉｃｓ，１９９７，２７（５）；５８８—５９７ ［１４３ Ｘｕ Ｊｉｎ，Ｚｈａｎｇ Ｊｕｎ－Ｙｉｎｇ，Ｂａｏ Ｚｈｅｎｇ．Ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔｈｅ ｉｓｏ— ｍｏｒｐｈｉｓｍ ｏｆ ｇｒａｐｈｓ ｂａｓｅｄ ｏｎ ｈｏｐｆｉｅｌｄ ｎｅｔｗｏｒｋｓ．Ｊｏｕｒｎａｌ ｏｆ Ｅｌｅｃｔｒｏｎｉｃｓ，１９９６，１８（Ｓｕｐｐｌｅｍｅｎｔ）：１１６—１２１（ｉｎ Ｃｈｉｎｅｓｅ） （许进，张军英，保铮．基于Ｈｏｐｆｉｅｌｄ神经网络的图的同构 算法．电子科学学刊，１９９６，１８（增刊）：１１６—１２１） ［１５３ Ｍａ Ｓｏｎｇ－Ｄｅ．Ｎｅｕｒａｌ ｎｅｔｗｏｒｋｓ ａｎｄ ｅｏｍｂｉｎａｔｏｒｉａ１ ｏｐｔｉｍｉｚａ— ｔｉｏｎ／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １ ｓｔ Ｃｈｉｎａ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋｓ．Ｂｅｉｊｉｎｇ，１９９０：２２—２８（ｉｎ Ｃｈｉｎｅｓｅ） ＮＡＮ Ｊｉｌｌ－Ｈｕａ，ｂｏｒｎ ｉｎ １９７２。Ｐｈ．Ｄ．． Ｈｅｒ ｒｅｓｅａｒｃｈ ｉｎｔｅｒｅｓｔｓ ｉｎｃｌｕｄｅ ｓｙｓｔｅｍ ｅｎｇｉｎｅｅｒｉｎｇ，ＤＳＳ ｅｔｃ． （马颂德．神经网络与组合优化／／中国神经网络首届学术大 会论文集．北京，１９９０：２２—２８） ［１６］ Ｃｈｅｎ Ｇｕｃ￣Ｌｉａｎｇ．Ｓｏｌｖｉｎｇ ｃｏｍｂｉｎａｔｏｒｉａｌ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂ— ｌｅｍｓ ｂａｓｅｄ ｏｎ ｎｅｕｒａｌ ｎｅｔｗｏｒｋｓ／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １ｓｔ Ｃｈｉｎａ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋｓ．Ｂｅｉｊｉｎｇ，１９９０：１２２—１２９（ｉｎ Ｃｈｉｎｅｓｅ） （陈国良．神经网络用于求解组合优化问题／／中国神经网络 首届大会论文集．北京，１９９０：１２２—１２９） ［１７３ Ｌｉａｎｇ Ｗｅｉ—Ｆａ．Ｓｏｌｖｉｎｇ ｓｏｍｅ ｈａｒｄ ｐｒｏｂｌｅｍｓ ｉｎ ｇｒａｐｈ ｔｈｅｏｒｙ ｂａｓｅｄ ｏｎ ｎｅｕｒａｌ ｎｅｔｗｏｒｋｓ／／Ｐｒｏｅｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １ｓｔ Ｃｈｉｎａ Ｃｏｎ— ｆｅｒｅｎｃｅ ｏｎ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋｓ．Ｂｅｉｊｉｎｇ，１９９０：９２４—９２７（ｉｎ Ｃｈｉ— ｎｅｓｅ） （梁维发．等用神经网络求解一些困难的图论问题／／中国神 经网络首届大会论文集．北京，１９９０：９２４—９２７） Ｅ１８３ Ａｅ Ｔ，Ａｇｕｓａ Ｋ，Ｆｕｊｉｔａ Ｓ，Ｙａｍａｓｈｉｔａ Ｍ．Ｏｎ ｎｅｕｒａｌ ｎｅｔ－ ｗｏｒｋｓ ｆｏｒ ｇｒａｐｈ ｉｓｏｍｏｒｐｈｉｓｍ ｐｒｏｂｌｅｍ／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＲＮＮＳ／ＩＥＥＥ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｎｅｕｒｏｉｎｆｏｒｍａｔｉｃｓ ａｎｄ Ｎｅｕｒｏ— ｃｏｍｐｕｔｅｒｓ．Ｒｕｓｓｉａ，１９９２：１１４２—１１４８ ［１９］ Ｘｕ Ｊｉｎ，Ｌｉ Ｓａｎ—Ｐｉｎｇ，Ｄｏｎｇ Ｙａ－Ｆｅｉ，Ｗｅｉ Ｘｉａｏ—Ｐｅｎｇ．Ｓｔｉｃｋｅｒ ｍｏｄｅｌ ｏｆ ＤＮＡ ｃｏｍｐｕｔｅｒ（１Ｉ）：ａｐｐｌｉｃａｔｉｏｎ．Ｃｈｉｎｅｓｅ Ｓｃｉｅｎｃｅ Ｂｕｌｌｅｔｉｎ，２００４，４９（４）：２９９－３０７（ｉｎ Ｃｈｉｎｅｓｅ） （许进，李三平，董亚非，魏小鹏．粘贴ＤＮＡ计算机模型 （ＩＩ）：应用．科学通报，２００４，４９（４）：２９９—３０７） ［２Ｏ］ Ｌｉｕ Ｇ Ｗ，Ｙｉｎ Ｚ Ｘ，Ｘｕ Ｊ．Ａｌｇｏｒｉｔｈｍ ｏｆ ｇｒａｐｈ ｉｓｏｍｏｒｐｈｉｓｍ ｗｉｔｈ ｔｈｒｅｅ ｄｉｍｅｎｓｉｏｎａｌ ＤＮＡ ｇｒａｐｈ ｓｔｒｕｃｔｕｒｅｓ．Ｐｒｏｇｒｅｓｓ ｉｎ Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ，２００５，１５（２）：１８卜１８４ ［２１］ Ｈｏｌｌａｎｄ Ｊ Ｈ．Ａｄａｐｔａｔｉｏｎ ｉｎ Ｎａｕｒａｌ ａｎｄ Ａｒｔｉｆｉｃｉａｌ ｓｙｓｔｅｍｓ． Ａｎｎ Ａｒｂｏｒ：Ｍｉｃｈｉｇａｎ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ，１９７５ ［２２３ Ｃｈｅｎ Ｇｕｏ－Ｌｉａｎｇ，Ｗａｎｇ Ｘｕ—Ｆａ．Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ ａｎｄ Ｉｔｓ Ａｐｐｌｉｃａｔｉｏｎ．Ｂｅｉｊｉｎｇ：Ｐｏｓｔｓ＆Ｔｅｌｅｃｏｍ Ｐｒｅｓｓ，１９９６（ｉｎ Ｃｈｉ— ｎｅｓｅ） （陈国良，王煦法．遗传算法及其应用．北京：人民邮电出版 社，１９９６） ［２３］ Ｂｒｉｊｎｅｓｈ Ｊ Ｊ，Ｆｒｉｔｚ Ｗ．Ａ ｎｏｖｅｌ ｎｅｕｒａｌ ｎｅｔｗｏｒｋ ａｐｐｒｏａｃｈ ｔｏ ｓｏｌｖｅ ｅｘａｃｔ ａｎｄ ｉｎｅｘａｃｔ ｇｒａｐｈ ｉｓｏｍｏｒｐｈｉｓｍ ｐｒｏｂｌｅｍｓ／／Ｐｒｏ— ｅｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＩＣＡＮＮ ２００３．Ｉｓｔａｎｂｕｌ，Ｔｕｒｋｅｙ，２００３：２９９— ３Ｏ６ ＱＩ Ｈｕａｎ，ｈｏｒｎ ｉｎ １９４８，Ｐｈ．Ｄ．，ｐｒｏｆｅｓｓｏｒ．Ｈｉｓ ｍａｊｏｒ ｒｅｓｅａｒｃｈ ｉｎｔｅｒｅｓｔｓ ｉｎｃｌｕｄｅ ｓｙｓｔｅｍ ａｎａｌｙｓｉｓ，ｍｏｄｅｌｉｎｇ ａｎｄ ｓｉｍｕｌａｔｉｏｎ．
