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 new DNA algorithm to solve graph coloring problem

Using a small quantity of DNA molecules and little experimental time to solve complex problems successfully is a goal of DNA computing. Some NP-hard problems have been solved by DNA computing with lower time complexity than conventional computing. However, this advantage often brings higher space complexity and needs a large number of DNA encoding molecules. One example is graph coloring problem. Current DNA algorithms need exponentially increasing DNA encoding strands with the growing of problem size. Here we propose a new DNA algorithm of graph coloring problem based on the proof of four-color theorem. This algorithm has good properties of needing a relatively small number of operations in polynomial time and needing a small number of DNA encoding molecules (we need only 6R DNA encoding molecules if the number of regions in a graph is R).     

A new DNA algorithm to solve graph coloring problem

Using a small quantity of DNA molecules and little experimental time to solve complex problems successfully is a goal of DNA computing. Some NP-hard problems have been solved by DNA computing with lower time complexity than conventional computing. However, this advantage often brings higher space complexity and needs a large number of DNA encoding molecules. One example is graph coloring problem. Current DNA algorithms need exponentially increasing DNA encoding strands with the growing of problem size. Here we propose a new DNA algorithm of graph coloring problem based on the proof of four-color theorem. This algorithm has good properties of needing a relatively small number of operations in polynomial time and needing a small number of DNA encoding molecules (we need only 6R DNA encoding molecules if the number of regions in a graph is R).     

关于标定不相交图并图的树的计数

本文就不相交的标定图的并图G =(V ,E) ,讨论当顶点选自V ,而边不属于E时所能构成树的棵数 ,其中得到的一些结果为文[1 ] [2 ] 等的一些结论的推广 .     

完全图的全符号控制数

设G是n个顶点的完全图,得到了完全图的全符号控制数。     

完全图的全符号控制数

设G是n个顶点的完全图,得到了完全图的全符号控制数。     

完全二部图K5，n的点可区别IE-全染色

设G是简单图,图G的一个k-点可区别IE-全染色（简记为k-VDIET染色）f是指一个从V（G）∪E（G）到{1,2,…,k}的映射,且满足：A↓uv∈E（G）,有f（u）≠f（v）;A↓u,v∈V（G）,u≠v,有C（u）≠C（v）,其中C（u）={f（u）}∪{f（uv）｜uv∈E（G）}。数min{k}G有一个k-VDIET染色}称为图G的点可区别IE-全色数,记为χut^ie（G）。本文给出了完全二部图K5,n（n≥6）的点可区别IE-全色数。     

双外平面图的点染色

图染色问题是图论研究中的重要问题之一,本文针对双外平面图G的点色数进行研究,并证明了：（1）不加剖分点时,当顶点数为6n＋k（n=1,2,…）（k=1,2,3）时,xv=4;否则xv=3.（2）xv=4时,当在相同面上两端的顶点标号冲突时,若剖分点加在这个标号相对的边上时,仍然有xv=4;否则xv=3.     

S-系包含图

设S是一个半群,M是S-系。M的包含图记为G(M),G(M)是无向简单图,它的顶点集由M的非平凡子系构成,顶点集中任意不同的两点是连接的当且仅当其中一个非平凡子系包含在另一个非平凡子系之中。基于该定义对这类图的完全性、连通性、直径、围长、团数和色数等性质进行了研究。     

基于四元数图神经网络的知识图谱嵌入

针对当前大多数知识图谱嵌入方法对实体和关系的表示能力低、难以处理复杂关系的问题,提出一种基于四元数图神经网络的知识图谱嵌入方法,用于解决知识图谱的链路预测问题。该方法为了包含更丰富的关系信息,将四元数引入到知识图谱嵌入中对实体和关系建模,并考虑两者之间的共现关系。模型利用勒维图变换将知识图谱中的实体和关系转换为图网络中的节点,采用两者的共现关系构建图中的边;将四元数图神经网络(quaternion graph neural networks, QGNN)作为编码器模块,学习图节点的四元数嵌入;利用四元数空间内的哈密顿乘积构造评分函数对生成三元组进行排序。实验结果表明,所提模型能够很好地捕捉到实体与关系之间潜在的相互依赖关系,在知识图谱嵌入方面优于现有的嵌入模型。     

修改一类G着色图的一个算法

给出了修改一类G着色图的一算法 ,并证明了通过第n次循环获得的G_Vo的第n +1个着色图一定不同于前n个G_Vo的着色图中的任何一个 ,和具有两个同一分支的连续循环过程不可能无休止地进行下去     

外平面图的平方图的点荫度

图G的平方图G2是以V(G)作为它的点集，两个点在G2中相邻当且仅当它们在G中的距离至多为2.证明了：若G是一个最大度Δ6的外平面图,则G2的点荫度va(G2)=「Δ+12?;特别地，一棵树T的平方图T2的点荫度va(T2)=「Δ+12?.     

最大度为6且不含5圈或6圈的平面图可8全染色

G,G的k 全染色是指用k种颜色给G的点和边进行染色,使G的任意邻接点或邻接边均染不同的颜色,且G的任一点与该点的任一关联边均染不同的颜色．证明了最大度为6且不含5 圈或6 圈的平面图是可8 全染色的．     

完全偶图的定向图

完全偶图是具有二分类（X,Y）的简单偶图，其中X的每个顶点与Y的每个顶点相连，若｜X｜=m,｜Y｜=n，则这样的图记为K_m,n。本文主要研究了Kn,n的定向图。证明了如下结论：对于非负整数a和b，若存在满足每个顶点的入度是a或者是b的一个Kn,n的定向图，则存在非负整数s和t满足方程s+t=2n和as+bt=n2。进一步，对于满足特定条件的非负整数a，b和n，存在K_n,n的定向图使得每个顶点的入度非a即b。     

图数据库中有向二分图构建的服务组合

云计算与大数据时代的到来促进了Web服务的发展。由于用户需求的复杂性,单个服务无法满足要求时,可将多个服务组合在一起提供解决方案。然而云中存在大量服务,查找合适的服务组合成为一个非确定性多项式(NP,non-deterministic polynomial)难问题。文章提出了一种利用图数据库解决组合问题的方法,通过构建基于有向二分图的服务组合图,对服务进行预组合并存储在Neo4j图数据库中,使用最少服务数组合查询和Dijkstra搜索算法来寻找服务数量最少或服务质量(QoS,quality of service)优化解。此外,能够根据服务的可用性对图数据库进行删除、添加、更新。实验结果表明,该方法能够在较短时间内在图数据库中寻找到满足用户需求的服务组合。     

一类无三角正则图的性质

图为无三角正则图,它满足不相邻的顶点恰有两个公共相邻顶点.先从代数的角度去研究它的特征值,得到了它的顶点个数只能取一些特殊的整数,然后证明了其点连通度与边连通度相等,而且存在完美匹配,最后猜想:(1)x(G)=x'(G)=k;(2)图G是Hamilton图.     

完全二部图K5,n的点可区别IE全染色

设G是简单图, 图G的一个k 点可区别IE 全染色(简记为k VDIET染色) f是指一个从V(G)∪E(G)到｛1,2,…,k｝的映射, 且满足:uv∈E(G),有f(u)≠f(v);u,v∈V(G), u≠v, 有C(u)≠C(v), 其中C(u)=｛f(u)｝∪｛f(uv)|uv∈E(G)｝。 数min｛k|G有一个k VDIET染色｝称为图G的点可区别IE 全色数,记为χievt(G)。本文给出了完全二部图K5,n(n≥6)的点可区别IE 全色数。     

基于遗传算法的二部图判定算法

应用遗传算法来判定二部图的具体过程是首先将无向图G的节点随机分配到两个不同社区中,然后用遗传算法进行进化操作,优化无向图G的模块化函数Q,当Q取最小值且无向图G的边只存在于两个社区之间,则无向图G为二部图.实例分析结果验证了算法的有效性.     

图的团分解

该文证明了从任何一个ｎ阶图中一个接一个地移去最大团，则移去团的顶点和达ｎ＾２／２后是空图，从而证明了Ｗｉｎｋｌｅｒ猜想。     

二分图中含有大圈的2-因子

设G=(V₁,V₂;E)是一个二分图,其顶点数目满足|V₁|=|V₂|=n≥(k+1)s+1，s和k是满足s≥3并且k≥1的两个正整数. 定义σ_1,1为图G的属于不同分划中的不相邻顶点的最小度和，证明了如果σ_1,1(G)≥2[(1-1/s)n]+2, 则G有一个2-因子包含至少k个圈,使得每个圈的长至少为2s.