图同构问题的决策神经网络模型

《计算机学报》2010年第2期，2010，33（2）图同构问题的决策神经网络模型南晋华，齐欢(华中科技大学控制科学与工程系武汉430074)摘要图的同构问题是研究两个图之间相互关系范畴。这对图表面上似乎不同，但本质上完全相同。由于图的同构问题在以系统建模、电路布线等众多问题中有直接的应用，因而，吸引了不少的学者从事这方面的研究。本文意在建立一种局域连接的、模拟人脑决策思维模式的、可用于优化信息处理的神经网络模型。文中在过去建立求解图的同构问题人工神经网络模型的基础上，拟应用人脑决策局域化的思想，提出了一种新的用于图的同构问题的人工神经网络模型。该模型中增加了一个自然的约束条件，加快了运算速度。关键词图；同构；决策；神经网络中图分类号TP301Thedecision-makingneuralnetworksmodelforsolvingthegraphisomorphismproblemNANJin-Hua1)QIHuan1)1)(DepartmentofControlScienceandEngineering，HuazhongUniversityofScienceandTechnology，Wuhan430074)AbstractThegraphisomorphismproblemistostudytherelationshipbetweentwographswhichseemtobedifferent,butessentiallyidentical.Thisproblemcanbewidelyusedinthesystemmodeling,circuitwiringandmanyotherissues.Therefore,thispaperisaimedtoestablishakindofneuralnetworksmodelthatareoflocal-connection,simulationhuman’sdecision-makingthinking,andalsocanbeappliedtosolvetheoptimizationforinformation.Onthisbasis,weuseanaturalconstraintinthismodelinordertospeeduptheoperations,andthenanewartificialneuralnetworkmodelisproposedtosolvethegraphisomorphismproblem.KeywordsGraph;Isomorphism;Decision-making;Neuralnetworksmodel1引言图的同构问题不仅是数学，特别是图论自身学科研究中的一个核心内容，而且具有良好的应用背景，在工程技术领域，特别是大系统建模、电路设计、机械设计、模式识别以及系统建模中有着广泛的应用。对于系统建模，如果能够证明需建模型与已知模型同构，则可以节省大量人力物力财力。多数学者认为图的同构判定问题属于NP-完全问题。但至今没有定论，即它究竟是P问题还是NP问题？目前关于图的同构问题的判定性算法不少，有诸如经典判定算法[1-8]、对在实际工程中有着广泛应用的图的拟同构问题算法[9-12]、进化计算方法[13]、人工神经网络求解算法[14-18]以及最新的DNA计算模型[19-20]等。在经典的图同构算法中，在此主要介绍两种算法，一种是所谓的矢量列表法，另一种是回溯算法。研究图的同构问题，一个重要的环节是如何表示图的信息。在这个问题上，Comeil与Hffman等人曾引入“模块”这一概念来表示各个顶点及其邻接顶点信息。在此基础上Riaz提出一种有效的判定图同构问题的算法-矢量列表法，即把各顶点所代表的信息用模块表示，所有模块组合在一起构成矢量列表。设计算法依次比较各模块，最终得到《计算机学报》2010年第2期，2010，33（2）同构信息。并在此基础上建立了判定图同构的矢量列表法。图同构的回溯算法是一种利用K-算子表示图结构，然后通过比对序列求解图同构映射的方法。K-算子这一概念最初由Kride等人提出，文献[11-12]对这一算法进行深入的探讨改进，并对这一方法进行了系统的论述，并给出了适合计算机求解的算法。虽然通过仿真结果证明了这种回溯算法的可行性，但是要严格地给出时间复杂度估计不是很容易的事情，尽管如此，这种试图从图的结构上来判定同构性的思想无疑是值得借鉴的，它通过引入算子，把给定图表示成字符串的形式，然后通过回溯模式识别，逐步求得可能的同构序列，最终得到两图是否同构。遗传算法由JohnHolland等人于20世纪60年代末提出，模拟生化机制进行优化计算[21]。图的同构问题稍加扩充，引入成具有一定应用背景的所谓的拟同构的概念。当两个图相近程度达到要求误差范围之内时，称两个图为拟同构图的拟同构的一个很重要的应用就是在模式识别中，通常把事物的特征及其相互作用表示成赋权图。该算法把一个图同构的判定问题分解在GA中进行求解。通过引入初始匹配，进化速度加快，用顶点映射来代替常规算法中的行列交换，鉴于GA求解随机搜索问题的有效性，在图的拟同构判定中，该算法也就显得十分有效。DNA计算是一种以DNA分子与相关生物酶为基本材料，以某些生化反应为基础的一种全新的计算模式。利用DNA特殊的双螺旋结构和碱基互补规律进行信息编码，把运算对象映射DNA分子链，生成数据池，然后把数据运算高度并行的映射成DNA的可控生化过程最后利用分子生物技术，检测出需要的结果。在利用DNA计算求解图论中的问题这一领域已经取得了不少的成果，文献[19]中利用粘贴DNA计算模型建立求解图同构问题的DNA计算模型，文献[22]利用k-臂DNA计算模型建立了另外一种求解图同构问题的模型。应用Hopfield网络研究图的同构问题始于马颂德[15]、陈国良[16-17]等人。其后，有一些学者利用神经网络模型来研究图的同构问题，如Brijnesh与Fritz提出了一种解决严格与非严格赋权图同构的神经网络方法。有别于其他的启发式及关联式算法，该方法巧妙设计了神经计算程序，通过一能量最小化匹配处理减小了搜索空间[23]。本章在已有工作的基础上，通过加入顶点邻域的思想，将顶点度加入到能量函数之中，进而加入到网络的运行方程之中，使得网络的运行速度得以加快，自然也减少了一些局部极小值，建立了一种新的神经网络求解图的同构问题的改进算法。2图的同构两个表面上似乎很不相同的图，本质上可能是完全一样的，或者说，这两个图是同构的。如图1中所示的三组图：M、与M'；H与'H；G与'G，它们表面上不同，但实际上每组图之间是同构的。其中的图M就是著名的Petersen图。在本文中分别用()VG，()EG分别表示图G的顶点集和边集。MM'H'H《计算机学报》2010年第2期，2010，33（2）123456781'3'7'5'4'6'2'8'G'G图1三组同构的图本文所言之图皆指无自环、无重边的有限无向简单图，用)(GV、)(GE(或EV,)分别表示图G的顶点集和边集，两个图G与'G，称为是同构的，如果存在一个从)(GV到)'(GV之间的保持相邻性的1-1映射，换言之，存在1-1映射：：)(GV→)'(GV，且),(,GVvu)(GEuv当且仅当)'()()(GEvu，称是从G到'G的一个同构映射。全体从G到G'的同构映射构成的集合记作)',(GGI。3模型及算法设G与'G是两个同构的图，},,,,{)(21pxxxGV,},,,{)'(21pyyyGV，)'(GGI，且满足pliyxli,,2,1,,)((3.1)置),(liyx为网络的神经元，它表示同构映射把图G的顶点ix映射到图'G的顶点ly。显然，由此而构成的神经网络共有pp个神经元。当网络稳定时，用ilv表示神经元),(liyx的输出，定义:否则若0)(1liilyxv(3.2)例如，图1中第三组中所示的两个图G和'G是同构的，其中一个同构映射为'2'8'3'5'6'4'7'187654321由同构映射可构成一个pp阶矩阵ppilvV)(，称为置换矩阵，如图1给出了两个8-阶的3-正则图G和'G，是一个保持相邻性的从)(GV到)'(GV的同构映射，由(3.2)式可得0000001010000000000001000001000000100000000010000100000000000001V下面来分析一下V的一些基本性质：由是1－l映射，保证了V的每一行、每一列有且仅有一个元素为1，而其余的元素均为0。由此获得：pivplil,,2,1,11(3.3)plvpiil,,2,1,11(3.4)设图G与'G的相邻矩阵分别为A与'A，ppijaA)(，ppijaA)'(',于是，由可保持相邻性有：对于)(,GVxxji)'()()()()'()()()(GElmjiGEijGElmjiGEij(3.5)《计算机学报》2010年第2期，2010，33（2）即0'01'1lmijlmijaaaa(3.6)基于(3.2)和(3.6)，有pmljivvaajmillmij,,2,1,,,,0)('(3.7)令},,,{)(21pxxxGV。设)(GVxi，用)(ix来表示顶点ix在图G中的邻域，用|)(|iixd来表示顶点ix的度数，pi,,2,1。我们约定，一个图G的度序列，记做)(G，是指满足单调递增的度序列：),,,()(21pdddG其中，pddd21同样，},,,{)'(21pyyyGV，且令''')(jjGdyd来表示图'G中顶点jy的度数，pj,,2,1。自然，两个图G与'G是同构的，它们的度序列也应该相同。对于神经元(,)ijxy而言，若)',(GGI，且jiyx)((3.8)则有'jidd(3.9)基于(3.2)、(3.8)和(3.9)，有plivvddililli,,2,1,,0)('(3.10)把满足(3.3)、(3.4)、(3.7)和(3.8)的关于图G与图'G的0-1矩阵V的全体集合记做)',(GGP，于是有：定理1设图G与'G是两个同构的)2(p阶图，则)',(GGI与)',(GGP通过(3.2)等价。证明:对于任一同构映射)',(GGI，令},,,,{)(21pxxxGV},,,{)'(21pyyyGV，且pliyxli,,2,1,,)(令否则若0)(1liilyxv则由ilv构成的矩阵ppilvV)(显然满足(3.2)、(3.4)、(3.7)和(3.10)式。因此，唯一地有)',(GGPV反过来，对于)',(GGPV，由于V满足(3.3)式和(3.4)式，因此，每行每列有且只有一个元素为1，其余元素皆为0。当),,2,1,()(,1pliyxvliil，则由(3.3)、(3.4)两式知，是从)(GV到)'(GV之间的一个1－1映射。下面，来证明是保持相邻性的1－1映射。对于)(,GVxxji，如果《计算机学报》2010年第2期，2010，33（2）(i))(GExxji，且mjliyxyx)(,)(，则有1,1jmilijvva，代入(3.7)式，有011)1('lma即1'lma此即，)'()()(GEyyxxmlji(ii))(GExxji，且mjliyxyx)(,)(，则0ija，1jmilvv，代入(3.7)得到0'lma。从而推得：)'()()(GEyyxxmlji。综合(i)、(ii)，证明了是保持相邻性的1－1映射，故知V唯一地找到一个)',(GGI，从而本定理获证。在上述工作