一种对称无向图的同构判定算法

文章在电路模拟法的基础上提出了一种对称无向图的同构判定算法。电路模拟法对随机图的同构判定问题非常有效,但是对于处理对称度较高的图,判定效率明显降低甚至失效。该文提出的算法针对对称无向图的特性,在电路模拟法的基础上结合Dijkstra算法,综合得到顶点属性和最短距离序列来搜索顶点之间的映射关系,能够有效判定这类图的同构问题。     

图同构判定的新方法

图的同构问题由来已久，并且它的应用十分广泛。例如：确定一个图的自同构群的构造的问题和它有紧密联系；在有机化学上我们可以利用图的同构判定方法来确定同分异构物。因此，寻求图同构的判定方法是一项引人入胜的工作。提出了一个新的判定方法（定理1）可以方便的确定两个图是否同构。此外，还得到了桌一类图的同构判定的一个较强的条件（定理2）。     

图同构判定的新方法

图的同构问题由来已久,并且它的应用十分广泛。例如:确定一个图的自同构群的构造的问题和它有紧密联系;在有机化学上我们可以利用图的同构判定方法来确定同分异构物。因此,寻求图同构的判定方法是一项引人入胜的工作。提出了一个新的判定方法(定理1)可以方便的确定两个图是否同构。此外,还得到了某一类图的同构判定的一个较强的条件(定理2)。     

循环图的同构

判定两个图是否同构是图论中尚未解决的难题。即使对同一类型的两个图,要判定它们是否同构也是较困难的。例如,判定两个正则图是否同构的问题,至今也尚未解决。 对循环图的同构,也是人们非常关心的问题。本文找到了判定两个循环图是否同构的方法。文中所述判定两个三度循环图同构的方法更为简捷,使用起来非常方便。     

一种判定树同构的BULT算法

将判定两棵树的同构问题转化成"图的同构"问题和"两棵树根结点之间的对应关系"问题的判定.基于图与树的关系,提出一种自底向上分层遍历图结点(Bottom-Up Layer Traversing)的方法,简称 BULT方法,解决以上两个问题,从而得到一种线性的时间复杂度与空间复杂度的树同构判定算法,并给出了算法正确性证明.该算法很容易扩展为图同构的判定算法.     

非正则图同构的算法改进及分析

对于非正则图的同构问题,给出了新的判定方法,并且对该方法的复杂度进行了简单的分析,最后用实例证明新方法比以往的方法简单方便。     

无向图同构的充要条件以及判定

通过对两个图邻接矩阵的特征值以及特征向量分析,利用对角化过程中的正交特征向量矩阵的特殊性质,得到了一种新的无向图同构的充要条件,并且由此条件得到同构图之间存在的关系,从而使得判定图的同构更加方便,尤其是在需要找出变换矩阵、判定同谱图时非常有效.     

1-可区分图的同构判定问题

判定两个图是否同构的算法复杂性至今还是一个开问题。作者研究一类图的同构问题,给出了K-可区分图及K-标准图的定义〔0相似文献   

n阶极大外平面图的构造法

图的同构的判定是图论研究中的重要课题之一,非同构的极大外平面图的计数问题尚未解决.提出一种判定图同构的方法,其原理是赋予每个无标号极大外平面图一个n×(n-3)阶0-1矩阵,证明了矩阵与极大外平面图一一对应,矩阵相同的图彼此同构.构造所有可能的n阶极大外平面图,并用上述方法除去其中同构者,所有n阶无标号极大外平面图被不重不漏地构造出来,同时得到其总个数,解决了有关极大外平面图同构与计数问题.     

基于邻接矩阵的σ全一问题判定方法

在已知的σ全一问题的集合形式判定方法的基础上,运用图的邻接矩阵给出简单图的σ全一问题的代数形式的判定方法。     

禁用两个子图的图的全控制数

设G=V(V,E)是一个简单无向图.一个点悬挂三个一度点的图称为爪图,D图是一个三角形其中两个点各悬挂一条长为2的路.如果图G的任何导出子图都不同构于爪图也不同构于D图,则称G为无爪和无D图.设S是V的非空子集,如果不在S的点一定与S中的某个点相邻,则称S为G的控制集.如果G中的点一定与S中的某个点相邻,则S称为G的全控制集.最小全控制集包含顶点的数目称为全控制数.给出了当G是N阶连通的无爪和无D图时全控制数紧的上界.     

基于无向图转有向图的同构判别

无向同构图指的是在两个图中寻找顶点之间的映射关系,通过映射使原本形式各异的两图中的各条边保持对应的关系.为了有效提高寻找无向同构图的时间效率、简化操作,首先研究了无向图同构的矩阵存储方式,并针对性地提出了把无向图转换为有向图的同构算法.与矩阵存储算法相比,该判定算法的时间更为简短.最后给出了实现该算法的相关程序以及用该算法对无向图进行判定的过程和结果.     

基于路径信息比较的图同构新算法

为了在多项式时间内解决图同构问题,首先证明了2个同构图相等长度的路径信息必相同是图同构判定更为严格的必要条件.然后,根据此条件,提出了一种基于路径信息比较的图同构PIC算法.该算法依次比较各长度的路径信息,对邻接矩阵进行调整,从而实现了2个图的快速同构判定.为了减少路径信息的计算时间,引入Hash函数对PIC算法进行改进,从而得到了HPIC算法.实验结果表明,所提的2种算法均能够正确判定1×104对不同类型、不同大小的随机图是否同构,并且图同构判定的时间复杂度明显降低.HPIC算法的运行速度快于PIC算法;这2种算法在时间性能方面均优于CS算法,略劣于Nauty算法;但对于规则2维网孔图,Nauty算法失效,所提的2种算法则仍能快速进行图同构判定.     

图的同构判定算法:关联度序列法及其应用

提出了图的同构判定新算法,即关联度序列法和黄金分割关联度序列法,后者的计算时间复杂性远远低于2N（N为图的顶点数）,已接近于多项式时间复杂性,该算法可应用于很多能用图来描述的式识别等实际问题。     

余树在图式流形拓扑分类中的应用

图式流形是以一个无向图G为框架产生出的管形曲面M（G）。本文讨论图式流形同胚分类的计数问题,该问题可转化为图的一类2-边着色问题,提出一种新的观点,探讨图式流形的等价分类,以便推进已有的工作。图的计数理论分为两大部分：标定图的计数与非标定图的计数。由于涉及同构判定,非标定图的计数较难。本文运用图论中的向量空间,包括圈空间及割空间,建立基本的计数方法,这一方面简化了群论方法的证明,另一方面更深入地揭示出同胚分类与圈结构的关系。以余树的概念为基础。提出“余树法”。并得出结论：以余树的所有边导出子图为黑边子图,构成卜等价类的一个横贯;同时,以余树中所有不同构的边导出子图为黑边子图。构成似等价类的一个代表系。     

关于广义路代数

通过将箭图的每个顶点放置一个k-代数,路代数的概念被推广到了广义路代数。首先研究了广义路代数的遗传性质。其次讨论了同构问题,证明了当两个正规广义路代数中的箭图都有限且无定向圈时,它们作为代数是同构的当且仅当它们中的箭图及对应顶点上的单代数是同构的。     

齿轮-连杆运动链的拓扑表示及同构判定

从齿轮－连杆机构（ＧＬＭ）的结构拓扑特性出发,提出一种表示齿轮－连杆运动链（ＧＬＫＣ）拓扑关系的组合图法,进而给出了其对应的组合矩阵和ＧＬＫＣ的结构不变量。根据这些结构不变量,利用组合矩阵的幂序列成功地解决了ＧＬＫＣ的同构判定问题。最后给出了具有显明图论依据的ＧＬＫＣ同构判定的一般方法,并编制了一个既可判定平面连杆运动链、又可判定ＧＬＫＣ同构的计算机程序。     

s不超过6的无标号(n,n/2+s)-奇图的计数

一个图称为(n,m)-图,若|V(G)|=n且|E(G)|=m.一个奇图是指每个点的度都是奇数的图.给出了一种新的图同构的定义,计算并给出了不同构无标号(n,n/2+5)-奇图的结果,并对s=4,6给出了不同构无标号(n,n/2+s)-奇图的完整结果.     

有向图的同构

证明“图Ｇ与图Ｆ同构当且仅当它们有机合的ＶＣ算法”的结论,对于简单有向图依然成立。     

基于功能离散的轮系拓扑及同构问题研究

拓扑的同构判定问题一直以来都是周转轮系拓扑综合问题的难点.在前人研究成果的基础上,首先提出了新的拓扑构建方法,即功能离散法,并对常见的周转轮系的拓扑图进行了分层;其次依据建立的拓扑图,提出了新的高效通用的同构判定的新方法;最后以实例的形式给出了具体的判定过程.