有向图的有向圈长分布

阶为v的有向图D的有向圈长分布是序列(c_1,c_2,…,c_v),其中C_i是D中长为i的有向圈的数目。设0≤x_i≤v-i-1,证明了存在v个顶点的有向图D,使D的有向圈长分布为(0,0,x_1,x_2,…,x_(v-3),1),并且给出了具有有向圈长分布为(0,0,x_1,x_2,…,x_(v-3),1)的有向图的最大可能的弧数以及具有有向圈长分布为(0,0,k,k,…,k,k-1,…,3,2,1)(其中1≤k≤v-2)的有向图的最小可能弧数的上界。     

Adm猜想初探

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

有向线图存在Hamilton圈和Hamilton路的一个充要条件

有向图D的有向线图是以A（D）为顶点集，弧集为{（xy，yz），xy∈A（D），yz∈A（D）}的有向图，用L（D）表示D的有向线图。文章证明了连通有向线图存在Hamilton圈当且仅当它有圈因子；连通有向线图存在Hamilton路当且仅当它有1-路圈因子。     

有向H图中的有向圈数

有向Ｈ图中的有向圈数施宇丹（计算机科学与工程系）人们时常要把一组对象按优劣排成次序．将所有对象看作一个有向图的顶点，如果对象ａ比对象ｂ好，就在相应的两个顶点之间画一条有向边（ａ指向ｂ）．于是当出现ａ比ｂ好．ｂ比ｃ好，ｃ又比ａ好时，就在排序中出现了一个...     

有向Hamilton图的一个充分条件

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

有向拟阵的一些结构性质(Ⅱ)

本文给出了有向拟阵的圈公理。     

有向路的重构

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

有向超图的可平面性算法

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

几类有向支撑树的计数公式

本文对有向图中常见的几类有向支撑树的计数问题进行了讨论，提出了有关有向支撑树数目的计算方法，并将Ｔｕｌｔｔｅ定理推广到了更一般的情况。     

有向H-图的新判定准则

应用布尔代数上的行列式det2(A),引入det2(A)的特征行列式,讨论了det2(A)的特征行列式的性质与有向图的圈的关系,并用这些结论给出有向H-图的新特性和新判定准则.     

几类有向图的优美性

探讨三类由m个有向圈■4构成的有向图的优美性.给出他们的优美标号,证明这三类图都是优美图.     

有向图2Cn的优美性

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

有向哈密顿回路问题的一个充分条件及其多项式验证算法

利用自动机理论研究有向哈密顿回路问题，提出一个多项式复杂度的算法验证有向哈密顿回路问题的一个充分条件.更具体地说，将有向图建模为一个自动机，并在自动机的基础上形式化了哈密顿图的相关概念，然后提出了一个多项式复杂度的算法，检验一个自动机标记的语言的子集是否满足真子集的一个充分条件.在该算法的基础上，提出了一个多项式复杂度的算法检验哈密顿图的一个充分条件并找出相应的哈密顿回路.特别地，给出了一个判断有向图是否是哈密顿图的充分条件和一个判断有向图中的一条回路是否是哈密顿回路的充分条件.     

循环群上有向Cayley图的Hamilton圈

C是一个有限群，M是G的一个极小生成集．用Cay(M：G)表示生成集为M的G上的一个Cayley图，Zn表示模n的剩余类加群．研究Zn上的有向Cayley图的Hamilton圈的存在性，给出了有向Cayley图Cay(M：Zn)存在Hamilton圈的若干充分条件．     

计算有圈有向网络根通信可靠度的因子分解算法

对有圈有向网络的拓扑结构进行了研究,提出了一个保持网络可靠度不变的缩减规则和因子分解的一个选边规则.由此建立了一个计算有圈有向网络根可靠度的有效算法.算法的时间复杂度是O(N.(|V|+|E|)),其中N是算法所产生二叉树的叶点数,|V|和|E|分别表示网络的节点数和边数.对一些网络进行了计算,结果显示利用该算法计算根通信可靠度所产生的N比其他算法的要小得多,因此,所提算法更有效.     

有向二部图中的独立有向6-圈

证明了若有向二部图D=(V1,V2:A)的最小度至少为5k,则D有k个顶点不交的独立有向6-圈.其中 |V1|=|V2|=3k, k为整数.     

有向架模型建模方法及其应用

为克服传统的基于有向图模型的危险和可操作性分析专家系统在知识表达方面的局限性，通过将二维的有向图模型在三维空间的解耦，采用图论的方法，提出了一个可以用于危险和可操作性分析自动化的有向架模型．利用该模型，可以灵活地表达危险和可操作性分析中的各种过程变量偏离之间的相互作用关系．它拓展了传统的有向图模型，从而使危险和可操作性分析的结果更全面、更系统，提高了专家系统全面挖掘化工过程中潜在的安全危险问题的能力．     

有向图最小圈长不大于4的一个充分条件

运用组合计数的方法, 给出了与Caccetta Haggkvist猜想有关的一个近似结果, 即给出最小出度至少为αn的n阶有向图含有长度不超过4的有向圈的充分条件： α≥0.288 66.     

若干广义圈的Hoffman多项式和谱

设J和I分别为全1矩阵和单位矩阵.对任一给定正整数k,称邻接矩阵A满足Ak=J(Ak=J-I)的有向图为UPP-k(UPFL-k)有向图.对UPP-k有向图Γ及任意正整数p,确定了Γ是广义圈CpГ的Hoffman多项式和谱;也对UPFL-k有向图给出了广义圈CpГ的Hoffman多项式及CkГ的谱的明确表达式.     

Hamiltonian图的弧行列式条件

利用弧行列式得到有向图有有向2-因子的充分必要条件,同时得到n阶有向图为Hamiltonian图的充分必要条件.