广义Petersen图的同构问题

本文推广了文[1]的结果,并进一步给出了广义 Petersen 图同构的充分必要条件,从而解决了 Petersen 图簇按同构关系分类问题.     

图的同构性质

本就图论中的一些基本知识在两同构或同态图中的相互关系作初步讨论。     

一类变换图的同构问题

利用度序列的概念,证明变换图G~(--+)与H_n~(--+)同构,当且仅当G与_n同构.以及在G连通的条件下,G~(--+)与C_n~(--+)同构,当且仅当G与_n同构.     

多重图的同构

证明了下列结论：２个多重图同构的充分必要条件是它们有相合的ＶＣ算法。     

图的同构因子分解──概况与问题

系统介绍了图的同构因子分解的已有成果和尚待解决的许多问题．     

图的同构关系判定中必要条件的补充

文章通过对图的同构关系的分析,提出了2个图同构的新的必要条件,并举例讨论了增加这个必要条件后,在简化证明2个图不同构的过程中的实际效果。     

2循环图的同构

设n>1是整数,K(?)N={1,…,n-1}.以V={V_0,V_1,…,v_(n-1)}为点集E={V_iV_j|j-i∈K}为有向边集的图称为循环图,记作G_n(K).证明了当K,H(?)N|K|=|H|=2时,G_n(K)≌G_n(H)蕴含存在自然数r∈N,满足(r,n)=1,使得rK=H.     

正则图的计数

帕撒塞拉西在１９６０年给出了具有给定划分的无向图的计算公式，但由于利用该计算公式计算时所涉及计算项随着无向图顶点个数的增加而急剧上升，所以无法用于实际计算。 本文利用正则图的特性与多元多项式的对称性，提出了在利用帕撒塞拉西的计算公式进行运算中存在同构项的新概念，并在此基础上给出了边计算边合并同构项的新算法。对ｐ≤１２（ｐ为图中顶点数）．计算出了各组正则图的数目，对于ｐ＝１０的３正则图一直被误认为是２０，并由哈拉里收入到名著《图论》中，本文指出其正确数目应为１９．     

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

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

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

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

Algorithm of graph isomorphism with threedimensional DNA graph structures

ResearchonDNAcomputingwasinitializedin1994 ,whenAdleman[1] proposedamethodofsolvingasmallinstanceoftheHamiltonianPathproblembyalaboratoryexperimentinvolvingDNAmolecules .Later,Lipton[2 ] demonstratedhowalargeclassofNP completeproblemscouldbesolvedbyencodingtheprobleminDNAmolecules .Inparticular ,LiptonshowedonefamousNP problem ,theso called“satisfiability”problem (SAT)andsubsequentlytheotherNP problemscouldbeencodedandsolvedusingmolecules .TheadvantagesofDNAcomputingareitsmassivepa…     

Algorithm of graph isomorphism with three dimensional DNA graph structures

An algorithm for solving the graph isomorphism problem with 3-D DNA structures is proposed in this paper. The karmed branched junction molecules are used to code k-degree vertices. Double stranded molecules are used to code edges. Then the molecules are mixed in a tube to be ligated. The result can be detected by gel electrophoresis. The time complexity of the algorithm is O(n2), where n is the number of vertices of the graph.     

双环网的同构类

同构图具有相同的拓扑性质。针对双环网的结构特点,根据步长a,b与结点总数n的不同关系,给出相应的同构映射。得到双环网的几大连接类型,并讨论了其中两同构类的总数。     

四度与五度循环图的同构的研究

得到了任意两个四度及五度连通循环图是同构的充要条件．     

标准算子代数上 Jordan 同构的刻画

设A和B是无限维Banach空间X上的标准算子代数且ψ：A →B是一个保单位的线性双射。证明了如果对任意的A,B∈A且AB＝0,有ψ（A°B）＝ψ（A）°ψ（B）成立,则对任意A,B∈A,要么ψ（AB）＝ψ（A）ψ（B）,要么ψ（ AB）＝ψ（ B）ψ（ A）。     

有向循环圈的A＇da＇m同构的性质

得到了任意两个有向连通循环图是同构的充要条件，及两个有向连通循环图是Ａ’ｄａ’ｍ同构的另一必要条件．     

多种类代数的两个同构定理

设Ａ＝（Ａｉ,ｉ∈Г为Ω－代数,ψ＝ψｉ,ｉ∈Г）和θ＝（θｉ,ｉ∈Г）都是Ａ上同余,Ｂ＝（Ｂｉ,ｉ∈Г）为Ａ的子代数,类似于一个非空集合上代数的情形,定义了ψ／θ和Ｂ＾θ,证明了（Ａ／θ）／（ψ／θ）≌Ａ／ψ,Ｂ／θ↑Ｂ≌Ｂ＾θ／θ↑Ｂ＾θ。     

图同构判定的新方法

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