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

书书书第３３卷　第２期２０１０年２月计　　算　　机　　学　　报ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳＶｏｌ．３３Ｎｏ．２Ｆｅｂ．２０１０　收稿日期：２００９０７０６；最终修改稿收到日期：２００９１１０６．南晋华，女，１９７２年生，博士，主要研究方向为系统工程、决策支持系统．齐　欢（通信作者），男，１９４８年生，博士，教授，主要研究领域为系统分析与建模等．Ｅｍａｉｌ：[e-mail]．图同构问题的决策神经网络模型南晋华　　齐　欢（华中科技大学控制科学与工程系　武汉　４３００７４）摘　要　图的同构问题是研究两个图之间相互关系范畴．这对图表面上似乎不同，但本质上完全相同．由于图的同构问题在以系统建模、电路布线等众多问题中有直接的应用，因而，吸引了不少的学者从事这方面的研究．该文意在建立一种局域连接的、模拟人脑决策思维模式的、可用于优化信息处理的神经网络模型．该文在过去建立求解图的同构问题人工神经网络模型的基础上，拟应用人脑决策局域化的思想，提出了一种新的用于图的同构问题的人工神经网络模型．该模型中增加了一个自然的约束条件，加快了运算速度．关键词　图；同构；决策；神经网络中图法分类号ＴＰ３０１　　　犇犗犐号：１０．３７２４／ＳＰ．Ｊ．１０１６．２０１０．００３００犜犺犲犇犲犮犻狊犻狅狀犕犪犽犻狀犵犖犲狌狉犪犾犖犲狋狑狅狉犽狊犕狅犱犲犾犳狅狉犛狅犾狏犻狀犵狋犺犲犌狉犪狆犺犐狊狅犿狅狉狆犺犻狊犿犘狉狅犫犾犲犿ＮＡＮＪｉｎＨｕａ　ＱＩＨｕａｎ（犇犲狆犪狉狋犿犲狀狋狅犳犆狅狀狋狉狅犾犛犮犻犲狀犮犲犪狀犱犈狀犵犻狀犲犲狉犻狀犵，犎狌犪狕犺狅狀犵犝狀犻狏犲狉狊犻狋狔狅犳犛犮犻犲狀犮犲犪狀犱犜犲犮犺狀狅犾狅犵狔，犠狌犺犪狀　４３００７４）犃犫狊狋狉犪犮狋　Ｔｈｅｇｒａｐｈｉｓｏｍｏｒｐｈｉｓｍｐｒｏｂｌｅｍｉｓｔｏｓｔｕｄｙｔｈｅｒｅｌａｔｉｏｎｓｈｉｐｂｅｔｗｅｅｎｔｗｏｇｒａｐｈｓｗｈｉｃｈｓｅｅｍｔｏｂｅｄｉｆｆｅｒｅｎｔ，ｂｕｔｅｓｓｅｎｔｉａｌｌｙｉｄｅｎｔｉｃａｌ．Ｔｈｉｓｐｒｏｂｌｅｍｃａｎｂｅｗｉｄｅｌｙｕｓｅｄｉｎｔｈｅｓｙｓｔｅｍｍｏｄｅｌｉｎｇ，ｃｉｒｃｕｉｔｗｉｒｉｎｇａｎｄｍａｎｙｏｔｈｅｒｉｓｓｕｅｓ．Ｔｈｅｒｅｆｏｒｅ，ｔｈｉｓｐａｐｅｒｉｓａｉｍｅｄｔｏｅｓｔａｂｌｉｓｈａｋｉｎｄｏｆｎｅｕｒａｌｎｅｔｗｏｒｋｓｍｏｄｅｌｔｈａｔａｒｅｏｆｌｏｃａｌｃｏｎｎｅｃｔｉｏｎ，ｓｉｍｕｌａｔｉｏｎｈｕｍａｎ’ｓｄｅｃｉｓｉｏｎｍａｋｉｎｇｔｈｉｎｋｉｎｇ，ａｎｄａｌｓｏｃａｎｂｅａｐｐｌｉｅｄｔｏｓｏｌｖｅｔｈｅｏｐｔｉｍｉｚａｔｉｏｎｆｏｒｉｎｆｏｒｍａｔｉｏｎ．Ｔｈｅａｕｔｈｏｒｓｕｓｅａｎａｔｕｒａｌｃｏｎｓｔｒａｉｎｔｉｎｏｒｄｅｒｔｏｓｐｅｅｄｕｐｔｈｅｏｐｅｒａｔｉｏｎｓ，ａｎｄｔｈｅｎｐｒｏｐｏｓｅｄａｎｅｗａｒｔｉｆｉｃｉａｌｎｅｕｒａｌｎｅｔｗｏｒｋｍｏｄｅｌｔｏｓｏｌｖｅｔｈｅｇｒａｐｈｉｓｏｍｏｒｐｈｉｓｍｐｒｏｂｌｅｍ．犓犲狔狑狅狉犱狊　ｇｒａｐｈ；ｉｓｏｍｏｒｐｈｉｓｍ；ｄｅｃｉｓｉｏｎｍａｋｉｎｇ；ｎｅｕｒａｌｎｅｔｗｏｒｋｓｍｏｄｅｌ１　引　言图的同构问题不仅是数学，特别是图论自身学科研究中的一个核心内容，而且具有良好的应用背景，在工程技术领域，特别是大系统建模、电路设计、机械设计、模式识别以及系统建模中有着广泛的应用．对于系统建模，如果能够证明需建模型与已知模型同构，则可以节省大量人力物力财力．多数学者认为图的同构判定问题属于ＮＰ完全问题．但至今没有定论，即它究竟是Ｐ问题还是ＮＰ问题？目前关于图的同构问题的判定性算法不少，有诸如经典判定算法［１８］、对在实际工程中有着广泛应用的图的拟同构问题算法［９１２］、进化计算方法［１３］、人工神经网络求解算法［１４１８］以及最新的ＤＮＡ计算模型［１９２０］等．在经典的图同构算法中，在此主要介绍两种算法，一种是所谓的矢量列表法，另一种是回溯算法．研究图的同构问题，一个重要的环节是如何表示图的信息．在这个问题上，Ｃｏｍｅｉｌ与Ｈｆｆｍａｎ等人曾引入“模块”这一概念来表示各个顶点及其邻接顶点信息．在此基础上Ｒｉａｚ提出一种有效的判定图同构问题的算法———矢量列表法，即把各顶点所代表的信息用模块表示，所有模块组合在一起构成矢量列表．设计算法依次比较各模块，最终得到同构信息．并在此基础上建立了判定图同构的矢量列表法．图同构的回溯算法是一种利用Ｋ算子表示图结构，然后通过比对序列求解图同构映射的方法．Ｋ算子这一概念最初由Ｋｒｉｄｅ等人提出，文献［１１１２］对这一算法进行了深入的探讨和改进，对这一方法进行了系统的论述，并给出了适合计算机求解的算法．虽然通过仿真结果证明了这种回溯算法的可行性，但是要严格地给出时间复杂度估计不是很容易的事情．尽管如此，这种试图从图的结构上来判定同构性的思想无疑是值得借鉴的，它通过引入算子，把给定图表示成字符串的形式，然后通过回溯模式识别，逐步求得可能的同构序列，最终得到两图是否同构的结论．遗传算法由Ｈｏｌｌａｎｄ等人于２０世纪６０年代末提出，模拟生化机制进行优化计算［２１］．图的同构问题稍加扩充，引伸成具有一定应用背景的所谓的拟同构的概念．当两个图相近程度达到要求误差范围之内时，称两个图为拟同构．图的拟同构的一个很重要的应用就是在模式识别中，通常把事物的特征及其相互作用表示成赋权图．该算法把一个图同构的判定问题分解在ＧＡ中进行求解．通过引入初始匹配，进化速度加快，用顶点映射来代替常规算法中的行列交换，鉴于ＧＡ求解随机搜索问题的有效性，在图的拟同构判定中，该算法也就显得十分有效．ＤＮＡ计算是一种以ＤＮＡ分子与相关生物酶为基本材料，以某些生化反应为基础的一种全新的计算模式．利用ＤＮＡ特殊的双螺旋结构和碱基互补规律进行信息编码，把运算对象映射成ＤＮＡ分子链，生成数据池，然后把数据运算高度并行地映射成ＤＮＡ的可控生化过程，最后利用分子生物技术，检测出需要的结果．在利用ＤＮＡ计算求解图论中的问题这一领域已经取得了不少的成果，文献［１９］中利用粘贴ＤＮＡ计算模型建立求解图同构问题的ＤＮＡ计算模型．文献［２２］利用犽臂ＤＮＡ计算模型建立了另外一种求解图同构问题的模型．应用Ｈｏｐｆｉｅｌｄ网络研究图的同构问题始于马颂德［１５］、陈国良［１６１７］等人．其后，有一些学者利用神经网络模型来研究图的同构问题，如Ｂｒｉｊｎｅｓｈ与Ｆｒｉｔｚ提出了一种解决严格与非严格赋权图同构的神经网络方法．有别于其它的启发式及关联式算法，该方法巧妙设计了神经计算程序，通过一能量最小化匹配处理减小了搜索空间［２３］．本文在已有工作的基础上，通过加入顶点邻域的思想，将顶点度加入到能量函数之中，进而加入到网络的运行方程之中，使网络的运行速度得以加快，自然也减少了一些局部极小值，从而建立了一种新的求解图的同构问题的神经网络算法．２　图的同构两个表面上似乎很不相同的图，本质上可能是完全一样的，或者说，这两个图是同构的．如图１中所示的三组图：犕与犕′；犎与犎′；犌与犌′，它们表面上不同，但实际上每组图之间是同构的．其中的图犕就是著名的Ｐｅｔｅｒｓｅｎ图．在本文中分别用犞（犌），犈（犌）分别表示图犌的顶点集和边集．图１　三组同构的图本文所言之图皆指无自环、无重边的有限无向简单图，用犞（犌）、犈（犌）（或犞，犈）分别表示图犌的顶点集和边集，两个图犌与犌′，称为是同构的，如果存在一个从犞（犌）到犞（犌′）之间的保持相邻性的１１映射，换言之，存在１１映射：σ：犞（犌）→犞（犌′），且狌，狏∈犞（犌），狌狏∈犈（犌）当且仅当σ（狌）σ（狏）∈犈（犌′），称σ是从犌到犌′的一个同构映射．全体从犌到犌′的同构映射构成的集合记作犐（犌，犌′）．１０３２期南晋华等：图同构问题的决策神经网络模型３　模型及算法设犌与犌′是两个同构的图，犞（犌）＝｛狓１，狓２，…，狓狆｝，犞（犌′）＝｛狔１，狔２，…，狔狆｝，σ∈犐（犌，犌′）且满足σ（狓犻）＝狔犾，犻，犾＝１，２，…，狆（１）　　置（狓犻，狔犾）为网络的神经元，它表示同构映射σ把图犌的顶点狓犻映射到图犌′的顶点狔犾．显然，由此而构成的神经网络共有狆×狆个神经元．当网络稳定时，用狏犻犾表示神经元（狓犻，狔犾）的输出，定义：狏犻犾＝１，σ（狓犻）＝狔犾０，｛否则（２）例如，图１中第三组中所示的两个图犌和犌′是同构的，其中一个同构映射为σ＝１２３４５６７８１′７′４′６′５′３′８′２（）′．由同构映射σ可构成一个狆×狆阶矩阵犞σ＝（狏犻犾）狆×狆，称为置换矩阵，如图１中两个８阶的３正则图犌和犌′，σ是一个保持相邻性的从犞（犌）到犞（犌′）的同构映射，由式（２）可得犞σ＝１０００００００００００００１００００１０００００００００１００００００１０００００１００００００００００００１烄烆烌烎０１００００００．　　下面来分析一下犞σ的一些基本性质：由σ是１犾映射，保证了犞σ的每一行、每一列有且仅有一个元素为１，而其余的元素均为０．由此获得∑狆犾＝１狏犻犾＝１，犻＝１，２，…，狆（３）∑狆犻＝１狏犻犾＝１，犾＝１，２，…，狆（４）　　设图犌与犌′的相邻矩阵分别为犃与犃′，犃＝（犪犻犼）狆×狆，犃′＝（犪′犻犼）狆×狆，于是，由σ可保持相邻性有：对于狓犻，狓犼∈犞（犌），犻犼∈犈（犌）σ（犻）σ（犼）＝犾犿∈犈（犌′）犻犼犈（犌）σ（犻）σ（犼）＝犾犿犈（犌′｛）（５）即犪犻犼＝１犪′犾犿＝１犪犻犼＝０犪′犾犿＝｛０（６）基于式（２）和式（６），有　（犪犻犼－犪′犾犿）狏犻犾狏犼犿＝０，犻，犼，犾，犿＝１，２，…，狆（７）　　令犞（犌）＝｛狓１，狓２，…，狓狆｝．设狓犻∈犞（犌），用Γ（狓犻）来表示顶点狓犻在图犌中的邻域，用犱犻＝｜Γ（狓犻）｜来表示顶点狓犻的度数，犻＝１，２，…，狆．我们约定，一个图犌的度序列，记做π（犌），是指满足单调递增的度序列：π（犌）＝（犱１，犱２，…，犱狆），其中，犱１犱２…犱狆，同样，犞（犌′）＝｛狔１，狔２，…，狔狆｝，且令犱′犌′（狔犼）＝犱′犼来表示图犌′中顶点狔犼的度数，犼＝１，２，…，狆．自然，两个图犌与犌′是同构的，它们的度序列也应该相同．对于神经元（狓犻，狔犼）而言，若σ∈犐（犌，犌′），且σ（狓犻）＝狔犼（８）则有犱犻＝犱′犼（９）基于式（２）、（８）和式（９），有（犱犻－犱′犾）狏犻犾狏犻犾＝０，犻，犾＝１，２，…，狆（１０）把满足式（３）、（４）、（７）和式（８）的关于图犌与图犌′的０１矩阵犞σ的全体集合记做犘（犌，犌′），于是有如下定理．定理１．　设图犌与犌′是两个同构的狆（２）阶图，则犐（犌，犌′）与犘（犌，犌′）通过式（２）等价．证明．　对于任一同构映射σ∈犐（犌，犌′），令犞（犌）＝｛狓１，狓２，…，狓狆｝，犞（犌′）＝｛狔１，狔２，…，狔狆｝，且σ（狓犻）＝狔犾，犻，犾＝１，２，…，狆，令狏犻犾＝１，σ（狓犻）＝狔犾０，｛否则，则由狏犻犾构成的矩阵犞σ＝（狏犻犾）狆×狆显然满足式（２）、（４）、（７）和式（１０）．因此，唯一地有犞σ∈犘（犌，犌′）．　　反过来，对于犞σ∈犘（犌，犌′），由于犞σ满足式（３）和式（４），因此，每行每列有且只有一个元素为１，其余元素皆为０．当狏犻犾＝１，σ（狓犻）＝狔犾（犻，犾＝１，２，…，狆），则由式（３）、（４）知，σ是从犞（犌）到犞（犌′）之间的一个１１映射．下面，来证明σ是保持相邻性的１１映射．对于狓犻，狓犼∈犞（犌），如果（ｉ）狓犻狓犼∈犈（犌），且σ（狓犻）＝狔犾，σ（狓犼）＝狔犿，则有犪犻犼＝１，狏犻犾＝狏犼犿＝１，代入式（７），有（１－犪′犾犿）×１×１＝０，即犪′犾犿＝１，２０３计　　算　　机　　学　　报２０１０年此即σ（狓犻）σ（狓犼）＝狔犾狔犿∈犈（犌′）．　　（ｉｉ）狓犻狓犼犈（犌），且σ（狓犻）＝狔犾，σ（狓犼）＝狔犿，则犪犻犼＝０，狏犻犾＝狏犼犿＝１，代入式（７）得到犪′犾犿＝０，从而推得σ（狓犻）σ（狓犼）＝狔