有向超图的可平面性算法

随着有向超图理论在实际问题中的深入应用，其平面性研究也更加具有意义．本文回顾有向超图的一般理论，给出了有向超图结构图的概念，并在此基础上给出有向超图的可平面性算法．由于有向超图的结构图是简单有向图，故有向超图的可平面性算法建立在对一般图的可平面性判断上，该算法是多项式时间算法，是有效算法．     

生成有向图中全部简单回路的一种新算法

提出了生成有向图中全部简单回路的一种新算法.算法的主要思想是对图中顶点进行缩减,在缩减过程中巧妙地利用字符串标记保存图中原有信息,不断减少图中顶点的数量,最终将图缩为一点,逐步得到全部简单回路.这种缩减过程隐藏在矩阵运算中,在运算中不断简化矩阵,从而降低了运算复杂度,提高运算效率.此算法生成的回路中不包含重复的回路,算法结构清晰,易转化为计算机程序.文中给出了算法的详细证明和实例应用.     

基于边被收缩图的有向有环图有向割集求解算法

为了提高有向有环图有向割集生成算法的效率,通过收缩有向有环图环路中的边将有向有环图转换成带收缩顶点的有向无环图,并使得生成有向无环图有向割集的算法可以生成有向有环图的有向割集.在理论上分析了本文提出的算法的时间复杂度和空间复杂度,并进行了实验测试.理论分析和实验测试的结果表明本文提出的算法是很高效的.     

用矩阵判断哈密顿图的一个充要条件

给出了一个从图的邻接矩阵来判断有限无向连通图是否是哈密顿图的充分必要条件     

竞赛图中的有向哈密顿路

对于竞赛图中必有有向哈密顿路这一命题,在分析已有证明的基础上,给出了一种新的证明。     

对Posa定理的讨论

文章通过对Posa定理进行讨论,给出了判断非哈密顿图的一些办法,并且给出了二部图是哈密顿图的一个充分条件.     

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

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

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

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

有向Hamilton图的一个充分条件

研究了有向Ｈａｍｉｌｔｏｎ图的一个特殊结构形式，从而给出了有向Ｈａｍｉｌｔｏｎ图的一个充分条件。     

一类优美有向图的充要条件

研究了由恰有一个公共顶点的有向回路→／Ｃｍ和→／Ｃｎ（ｍ，ｎ≥３）组成的有向图→／Ｗｍ，ｎ的优美性，给出了→／Ｗｍ，ｎ是优美有向图的充要条件。     

关于Ghouila—Houri定理的注记

Ghouila—Houri 得到强连通有向图 D 是有向 H 图的充分条件.强连通有向图 D 中,若对任一点 V.d((?))≥p,则 D 是有向 H 图。任一有向图都可以看作某个相应马尔可夫链的转移概率图。我们应用马尔可夫链理论得到:强连通有向图 D 中,如果 min{δ~+(D),δ~-(D)}≥p/d,则 D 是有向 H图。这里 d 是马尔可夫链周期,因此 d≥2。当 d=2时,即是 Ghouil—Houri 定理条件。     

λ阶短哈密顿回路的匹配法

无向权图G(n,m)的任始结点哈密顿回路可分成两条匹配半路径,根据给定λ值,用最小权路径延长法,对所有相关半路径进行匹配,便可完全确定从最短到λ阶短哈密顿回路的匹配法和相应的匹配算法.λ阶短哈密顿回路的匹配法可用于判别权图G(n,m)是否为哈密顿图.     

用矩阵判断哈密顿图的一个充要分析

给出了一个从图的邻接矩阵来判断有限无向连通图是否是哈密图的充分必要条件。     

用有向图法解决网页爬行中循环链接问题

提出网页构成的有向回路问题, 描述了由网页构成有向图的形式定义, 并给出了用有向图法发现网页构成的有向回路算法. 所给定的算法能使网页爬行器避免掉入由已爬行过的网页构成的有向回路陷阱.     

有向路的重构

在Harary和Palmer的有关有向图的重构的基础上得到:若有向路的顶点数大于4,则可以利用它的一组有向子树重构该有向路.结合Harary和Palmer给出的有向图的重构定理,推出结论:设T是有ν(ν≥4)个顶点的有向树,则T可由其子图{T-vi}完全确定(其中i=1,2,…,ν).     

有向图2Cn的优美性

图论是数学的一个分支,特别是离散数学的一个重要分支,它在物理、化学、天文、地理、生物学,尤其是在计算机科学中有着非常广泛的应用。图的标号问题是图论中极有趣的一个研究课题,有着较好的研究价值和广阔的应用背景。图的一个顶点标号是顶点集合到非负整数集合的映射,而边标号是边集合到非负整数集合的映射,根据对映射的不同要求,产生了各种各样的图的标号问题,有向图的优美标号是其中的一类。用Cn表示有n个顶点的有向圈,mCn表示m个无公共顶点的有向圈Cn之并,本文研究了有向图mCn的优美性,利用搜索图的标号的算法与数学证明相结合的方法,证实了有向图2Cn为优美图,其中n为任意正整数。     

基于核的有向强连通图计算机随机生成算法

针对图论算法研究和算法测试对随机生成有向强连通图的需求,在深入研究有向强连通图和极小有向强连通图的结构组成的基础上,提出了有向强连通图核的概念。参考有向连通图的随机生成算法,给出了一种有向强连通图的随机生成算法,并对该算法进行了测试。对具有上千个节点及上万条弧的强连通图的随机生成,采用该算法时间都在1 s以内,生成的结果能很好地应用于图论研究,以作为图论算法的随机测试用例。     

一个求图的最大圈的启发式算法

本文给出了无向图、有向图存在哈密顿圈或存在包含顶点数为N_1的最大圈的充分条件,在此基础上给出了求最大圈的找通路一扩大回路算法,这个算法是启发式的,但是有效的。利用此算法可以求出任意图的最大圈,也可以用来搜索图的最佳哈密顿圈。     

一种数字电路反馈线的快速切割算法

本文提出了一种数字电路反馈线的快速切割算法。该算法先在一个表示数字电路的有向图上构成一棵内向树,然后确定与内向树树枝形成回路的余树枝为反馈线。文中还证明了,切断这些反馈线后的电路不存在回路。     

Adm猜想初探

有向图的Adam猜想是图论中的一个尚未解决的问题。本文根据有向图中含一已知弧的有向圈数目同这弧的从头到尾的有向路数目的相等关系得到Adam猜想的一个等价命题:若D是包含有向圈的有向图,则存在某弧,把它反向之后将减少D中有向圈的数目当且仅当在D中存在一条弧(v_i,v_j),满足r_(?)≤r_(ij),其中r_(ij)表示D中从点v_i到点v_j的有向路的数目。据此我们可以证明Adam猜想对满足一定条件的许多有向图是成立的。