一种判定树同构的BULT算法

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

无向图同构的快速算法

规范标记算法和顶点划分算法是判断无向图同构的两种重要途径,其缺点是要么无法对图进行规范标记,从而不能进行判断；要么必须进行不断地回溯和试探,从而造成指数阶时间开销.对于任何两个同构的无向图,各自新增一个顶点和若干条关联边,可获得父图.当且仅当新增顶点的邻接点在原同构图中保持同构关系时,父图同构.根据这个充要条件,文中使...     

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

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

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

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

简单无向图的同构判定问题的研究

图的同构判定问题是图论学科的基本问题之一,但是要判定两个图是否同构却是一件非常不简单的事情。本文旨在研究简单无向图的同构判定问题;并提出了一种新的简单无向图同构的必要条件。     

无向无权图同构判别算法简

首先,分析判别同构图的一种常用实现方法:基于邻接矩阵存储,并讨论其存在的时间复杂度为O(N!).接着,针对两图中结点数、边数、每个结点的度均相同的特殊图形提出无向无权图同构判别的另一算法:采用结点之间距离及关联边进行判别.最后通过实例进行算法测试和比较,证明了该算法是完全行之有效的.     

无向无权图同构判别算法

首先,分析判别同构图的一种常用实现方法:基于邻接矩阵存储,并讨论其存在的时间复杂度为O(N!).接着,针对两图中结点数、边数、每个结点的度均相同的特殊图形提出无向无权图同构判别的另一算法:采用结点之间距离及关联边进行判别.最后通过实例进行算法测试和比较,证明了该算法是完全行之有效的.     

图同构判定的新方法

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

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

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

基于时间的关键字路网路径规划

为了便于道路网距离的计算、对象文本信息和时间信息的组织和快速获取,改进G-Tree,在索引结构上增加时间戳和倒排序列相关信息,称包含时间戳和倒排序列相关信息的G-Tree为IGT-Tree.并基于构建的IGT-Tree设计了两种推荐算法：一种是基于时间的目标点查询算法,另一种是在目标点查询算法基础上的路径推荐算法.最后,在基于时间的关键字路网通过实验对比G-Tree的算法验证了所提算法的高效性.     

一种改进的补丁比较模型的研究与实现

补丁比较技术可以定位程序补丁前后的差异,在漏洞发掘、病毒变种分析等领域得到了广泛的应用。以结构化比较技术为基础,建立了层次化的补丁比较模型IPCTM(Improved Patch Comparison Technique Model);改进了固定点传播算法,提出了一种针对错误匹配的修正机制;设计了控制流图重构和代码辅助匹配策略,增加了对未配对函数和基本块的补充处理。实验结果表明,IPCTM能够准确识别语义变动,消除部分非语义变动带来误差,有效减少了后续分析的工作量。     

3－W_n图的优美性

证明了在齿轮图ｎ个齿的顶端各加上三条长度为１的边所得的图是优美的，从而对齿轮图的优美性作了推广．     

基于基本块签名和跳转关系的二进制文件比对技术

基于基本块签名和跳转关系的二进制文件结构化比对技术,对已有的二进制结构化比对算法进一步改进,提出一种基于基本块签名和基本块之间跳转关系的函数控制流图比对算法。即首先提取二进制文件反汇编后的函数控制流图信息,然后对图中的基本块进行签名匹配,在签名匹配的基础上再进一步利用邻接矩阵进行边匹配,最后利用匹配的基本块计算函数相似度和文件相似度,并开发出比对工具BinCompae。研究结果表明:相对于源码比对工具和几个常用的二进制补丁比对工具,针对常见的代码抄袭方式,BinCompae均能检测出99%以上的相似度;此外,BinCompare还能检测出语义不变,代码形式改变的抄袭方式。因此,基于基本块签名和跳转关系的结构化比对算法针对二进制文件比对具有很高的准确性和实用性。     

任意n个完备二分图的并图的优美性

优美图是图论中的一个重要分支,至今对非连通优美性的研究并不多,特别是对n个图的并图的优美性研究就更少.本文证明了任意n个完备二分图的并图是优美图,且是交错图.     

一类串图的优美性

给出了一些图的优美标号,特别给出了串图ωm1,m2,mn,mn＋1当m1,m2,…,mn≡0（mod4）,mn＋1≡3（mod4）的优美标号,以及串图ωm1,m2,,m2n当mi≡2（mod4）（i=1,2,…,2n）,m2k-1＜m2k,（k=1,2,…,n）时的优美标号.     

关于Km，n并图的优美性

对于自然数k，m，n，本文给出一类非连通图↑k∪↓i=1Kmi.ni；通过构造标号函数的方法，证明了当max{mi，ni}≥3，min{mi，ni}≥2(i=1，2，…，k)时这类图既是优美图，也是交错图；从而给出构造一类任意个图的并图是优美图的一种方法，拓宽了优美图及其应用的道路。     

图U∧C_(4,m_i)from i=1 to n的优美性

优美图是图论中的一个重要分支,至今对非连通优美性的研究并不多,特别是对n个图的并图的优美性研究就更少.本文证明了一类任意n个二分图∧C4,m的并图4,1inmiC=U∧是优美图,且是交错图.     

再论图Pn^3的优美性

给出图Pn3的另一种优美标号,证明其图是优美图且是交错图.另外指出文献[1]中的一个错误和给出了相应正确的结果,同时证明了严谦泰,张忠辅给出的标号以及我们改正的标号都是交错的.     

图∪ from i=1 to n(F_(mi,4))的优美性

给出图∪ni=1Fmi,4 的一类非连通图 ,并证明这类图是优美图 ,且也是交错图 .     

关于图n∪i=1(～P)4和n∪i=1(～P)8的优美性

棱柱图(～P)n是由2个回路v1,v2,v3,…,vn和u1,u2,u3,…,un,加上边uivi后所组成的图形.图n∪i=1(～P)4是n个(～P)4的不交并图,图n∪i=1(～P)8是n个(～P)8的不交并图,证明了2类非连通图n∪i(～P)4和n∪i=1(～P)8是优美图且是交错图.