4度循环图的同构因子分解

本文证明了对４度循环图的同构因子分解，可分性条件是充分条件。     

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.     

某些偶数度循环图的同构因子分解

根据连通循环图的性质，证明了循环图的同构因子分解，对于某些偶数度循环图结论成立，得到了Ｃｎ〈ｊ１，ｊ２，…，ｊｒ〉及Ｃｎ〈１，２，…，ｒ〉的同构因子分解条件．     

循环图的′Ad′am同构

任意两个同构循环图不一定是′Ad′am同构的。因此,寻找两个循环图是′Ad′am同构的充要条件很有意义。本文找到了任意两个连通循环图是′Ad′am同构的充要条件,同时还找到了两个同构循环图C_n与C_n是′Ad′am同构的另一充分条件。     

奇数度循环图的性质

本文得到了奇数度循环图是连通图的充要条件及C_n×k_2(krn/2)为循环图的充要条件,证明了三度连通循环图C_n同构于C_n<1,n/2>或C_n<2,n/2>。这一结果颇有意义。     

2—有向循环图的同构

本文得到了2-有向循环图 G(a,b,N)与 G(a＇,b＇,N)同构的充要条件为:(a,b,N)=(a＇,b＇,N)=K且 a＇b≡ab＇(mod KN);或 a＇a≡b＇b(mod KN),这里(x,y,z)表示整数 x,y,z 的最大公约数。     

循环图的连通度

根据循环图的原子部分的性质，得出了循环图Ｇ＝Ｃｎ〈ｊ，ｊ２，…，ｊｒ〉的连通度Ｋ（Ｇ）的求法及连通度Ｋ（Ｇ）≥ｗ（ｗ＝ρ（Ｇ））的循环图的构造方法     

图的同构性质

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

多重图的同构

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

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

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

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

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

两个循环图的邻接矩阵的乘积矩阵对应图的研究

讨论了两个循环图的邻接矩阵的乘积矩阵所对应的图 ,得到了以下结果 :1) [Cn(0 ,1,0 ,… ,0 ) ]2 =Cn(2 ,0 ,1,0 ,… ,0 )　　 2 ) [Cn(0 ,1,1,… ,1,0 ) ]2 =Cn(n - 2 ,n - 4,… ,n - 4,n - 2 )　　 3)Cn(a0 ,a1,a2 ,… ,a[n2 ] ) Cn(0 ,1,1,… ,1) =Cn(p -a0 ,p -a1,p -a2 ,… ,p -a[n2 ] )     

切比雪夫多项式与循环图中生成树的个数

生成树的个数是评估图(网络)可靠性的一个重要且被广泛研究的量.利用切比雪夫多项式的性质推出了循环图中计算生成树个数的在线性时间内即可实现的方法,并讨论了渐进特性.     

具有第四大和第五大Merrifield-Simmons指标的n阶单圈图

讨论n阶单圈图的第四大和第五大的Merrifield-Simmons指标,得到Merrifield-Simmons指标第四大和第五大的n阶单圈图.     

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.