图的路径运算矩阵与哈密顿回路等路径问题

从简单图的邻接矩阵定义了初始路径运算矩阵和一般路径运算矩阵,并定义了一般路径运算矩阵的加法和乘法运算,通过这些运算可以直接求简单图的最长路、最短路、任意两点之间的通路及具有长度约束的路径问题,还可以检测简单图哈密顿回路及计算所有哈密顿回路,结果都显示在最后的路径运算矩阵上。证明了一般路径运算矩阵的幂长公式并得到了简单图存在哈密顿回路的充要条件,分析了矩阵乘法运算的总时间复杂度,结果表明本算法比其他同类方法计算量大大减少,为图论相关路径问题研究提供了一个新的研究方法。     

简单有向连通图关联矩阵右逆的图特征及应用

研究ｎ阶简单有向连通图的ｎ－１传导矩阵,引入了图真值向量及运算,得出ｎ阶简单有向连通图关联矩阵右逆的图特征;提出了一种寻找简单有向连通图全部生成树的方法。     

Pythagorean模糊信息系统属性约简的图论方法

信息系统中,属性约简是知识发现问题的一个研究热点,能达到发掘并简化知识的目的。目前已有很多利用辨识矩阵来进行属性约简的研究,但是当数据维数较大时,算法复杂度往往很大。利用加权欧几里得距离来定义二元关系及辨识矩阵,利用信息系统的约简与生成图的最小顶点覆盖等价的关系,将辨识矩阵求解约简的问题转化为求解生成图中最小顶点覆盖的问题,并给出了Pythagorean模糊信息系统中属性约简的算法;在此基础上,利用基于加权欧几里得距离的相似关系,定义了Pythagorean模糊决策信息系统的辨识矩阵,并给出了用最小顶点覆盖的方法求约简算法,最后利用实例验证了算法的有效性。     

基于权限提升矩阵的攻击图生成方法

目前的攻击图生成算法的复杂度较高,难以应用于大规模网络环境的攻击图生成.本文对攻击图构建过程进行了研究,在攻击模式库和目标环境描述模型的基础上,提出了基于权限提升矩阵的攻击图生成方法,以矩阵描述攻击过程中攻击者的权限提升过程,能够以较低的算法复杂度生成攻击图.搭建实验网络,验证了本文算法的攻击图生成过程.      

利用时偶图求平面图全部回路的一种算法

求平面图的全部回路,对一个较为复杂的图,给出其回路矩阵B_α是很困难的。用观察法求B_α很难保证在查回路时不丢掉一些回路,如果能用一个简单而系统的办法得出一个图的全部回路显然是有意义的。本文利用不完善的对偶图。求回路矩阵B_α,方法简单、直观、能保证不丢回路,不会出现冗余项,使平面图求全部回路大为简化。     

求解大规模稀疏有向图回路的多线程并行算法

传统的基于深度优先遍历的回路求解算法限于计算机内存无法对大规模图进行求解,而已有的分布式图计算系统需要借助计算机集群,成本较高。针对此问题,给出一种可在普通计算机上求解大规模有向图所有回路的多线程并行算法。该算法根据顶点的出度,首先删除出度为0的顶点,然后采用多线程并行求解包含出度较大的顶点的回路,最后使用串行算法求出图剩余部分的回路。实验表明,此算法能够在普通计算机上求得大规模有向稀疏图的所有回路。     

哈密顿回路存在性判定及输出算法

给出L集合、L矩阵、连接积和通路矩阵的概念及基于这些概念的一些哈密顿回路的存在性判定定理和通过构造通路矩阵序列Mk=Mk－1*M（k=2，...，n）直接求出简单图（无向和有向）的全部哈密顿回路的算法及实例．     

一些特殊图的无符号Laplacians多项式

用表示有n个顶点的简单图G的邻接矩阵,表示图G的度矩阵.图G的无符号矩阵为S=A+D.本文给出了一些特殊图的无符号矩阵和特征多项式.     

机构拓扑回路的自动生成

为了研究平面机构的计算机自动生成算法,采用了图论的理论与方法,根据平面机构的结构特点,提出了四点机构拓扑回路的分类问题,以及如何在每类回路上增加通路,进而成功地搜索出全部的机构拓扑回路。该文还提出了扩展点点邻接矩阵与扩展点边关联矩阵的概念,并利用这两个矩阵的扩展列与扩展行存储搜索过程中的信息,为进一步搜索提供了方向,从而提高了机构拓扑回路生成的效率。最后通过实例分析证明了这种计算机自动生成算法是快捷而可靠的。     

用分层关联方法求简单图中所有Hamilton回路的算法

研究简单图中所有的Ham ilton回路,不但可以判断简单图是否Ham ilton图,并且还可以得到简单图的所有的Ham ilton回路。首先在简单图中建立了初级通路的关联关系,并对初级通路的关联关系进行了分层,在此基础上,设计了求简单图中所有Ham ilton回路的算法。该算法利用简单图中长度为x的初级通路及长度为x的初级通路的分层关联关系逐步求长度为x 1的初级通路及长度为x 1的初级通路的分层关联关系的方法,求得简单图的所有Ham ilton回路。通过理论证明,该算法与已有的求简单图的所有Ham ilton回路的算法相比,原有的求简单图的所有Ham ilton回路算法中大量的重复计算被避免,从而提高了算法的效率。