有向图的有向圈长分布

阶为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)的有向图的最小可能弧数的上界。     

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

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

三圈图的距离矩阵Inertia

令G是一个点集为V (G)={v_1,v_2,…,v_n}的连通简单图,让d_(ij)=d_G (v_i,v_j)]是图G中点vi和点vj之间的距离,图G的距离矩阵是D(G)=(d_(ij))_(n×n).用n_+(G),n_0(G),n_-(G)分别表示D(G)的所有特征值中正数、零、负数的个数。由此定义D(G)的Inertia为(n_+(G),n_0(G),n_-(G)),并且给出了围长为3的三圈图的距离矩阵的Inertia.     

两类冠图的Randi■能量

设G是顶点集为V(G)={v_1,v_2,…,v_n}的简单无向图,R(G)=(r_(ij))是图G的Randi■矩阵,其中当v_i与v_j相邻时r_(ij)=1/■;否则r_(ij)=0.图G的Randi■能量RE(G)指R(G)的特征值的绝对值之和.冠图G■_1G_2是由图G_1的每个顶点与图G_2的一个拷贝的所有顶点相连得到的.本文对冠图I_r(K_n)和K■_nK_m的Randi■能量进行了研究.     

圆有向图中的泛弧

设D=(V,A)是一个有向图,uv是D上的一条弧。如果对于任意顶点w∈V(D),都有弧uv和顶点w包含在某个公共圈中,则称弧uv是D的一条泛弧。证明了圆有向图R的每条弧都是泛弧当且仅当R是一个圈或者R是2-强连通的且R不属于一类特殊的圆有向图。并由此给出了判断圆有向图的每条弧是否都是泛弧的多项式算法。     

完全二部有向图的(C_(2k),α)-因子分解

K*m,n表示对称的完全二部有向图,C2k表示2k长有向圈。如果K*m,n的子有向图F满足(1)F的有向弧集可分解为若干个有向圈C2k,(2)K*m,n的每一个点都恰好出现在F的"个C2k中,则称F为K*m,n的(C2k,")-因子。如果K*m,n的有向弧集可以划分为K*m,n的(C2k,")-因子的和,则称K*m,n存在(C2k,")-因子分解。文章利用直接构造法,得到对称的完全二部有向图K*m,n存在(C2k,")-因子分解的充分必要条件:m=n#0(mod"k/d),其中d是"和k的最大公约数。     

Fuzzy有向图中有向路及有向圈存在的条件

对Fuzzy有向图定义了邻接矩阵，并通过对邻接矩阵幂的讨论，探讨了Fuzzy有向图中从有向途径中分离有向路的条件，有向圈及有向Hamilto n圈存在的条件。     

图的Seidel Laplacian-Estrada指标

设G为简单图,d_i表示顶点v_i的度,G的Seidel Laplacian矩阵S_L(G)是一个对角元为n-1-2d_i,非对角元为±1的实对称矩阵,当顶点v_i和v_j相邻时,(S_L(G))_(ij)=1,否则,(S_L(G))_(ij)=-1。引入并研究了Seidel Laplacian矩阵的Estrada指标,给出了该指标的上、下界,以及它与Seidel Laplacian能量之间的关系。     

关于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 定理条件。     

一类超欧拉有向图中的超欧拉bypass

设D是严格有向图(无环与重弧),λ(D)是有向图D的弧强连通度,α′(D)表示有向图D的匹配数.如果有向图D中含有一个生成欧拉子图反向一条弧的方向所得的子图,则称有向图D含有一个超欧拉bypass.证明了一个强连通有向图D满足λ(D)≥α′(D)≥5,则有向图D含有一个超欧拉bypass.     

一类特殊的双色有向图的本原性

文章研究了只有两个圈C1,C2的双色有向图,给出了这类双色有向图本原的充分必要条件.     

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

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

连续格的极小集刻画

仿照完全分配格中的做法,定义了完备格上的定向极小集和连续格上的定向极小映射,从而得到了连续格的定向极小集刻画,并研究了它们的一些性质。     

产生任意k阶余因式的原理和方法

提出了不定导纳矩阵任意k阶余因式的有向树拓扑表示式;给出了通过混合分割产生有向树多项式的分解定理.应用它们可以方便有效地求取任意k阶余因式的拓扑表示式.用其求全符号网络函数,可扩大计算机所能拓扑分析的网络规模.用其求部分符号网络函数,可使计算机所能分析的网络规模扩大到一般数值分析程序所能处理的阶数.     

对合Quantale范畴中的定向极限

讨论了对合Quantale范畴中函子作用在上有界集上的定向极限，并且给出了该定向极限的具体结构，同时得到了定向极限为单渗漏的一个充分条件．     

采用有向电气介数的脆弱线路选取

针对电力网络是有向加权网络的特性,在当前运行方式下考虑网络结构的脆弱性,利用线路功率组成,提出了将有向电气介数作为线路脆弱性指标.这样可以真实反映出"发电-负荷"节点对之间功率传输对各线路的占用情况,并且引入发电机出力来考虑不同电压等级线路阻抗的差异,能有效识别出系统的关键线路,同时将传统的只考虑发电机负荷间最短路径的全局效能指标替换为考虑发电机负荷间所有传输路径的有向全局导纳指标,这样物理背景更符合电力系统实际.采用IEEE-39节点系统进行仿真计算,结果验证了该算法的有效性和可行性.     

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

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

赋权多阶段有向图最短路的求法

多阶段有向图是常见的一种有向图,许多运输、工程、管理等实际问题能转化为有向图最短路问题进行求解,尤其赋权多阶段有向图对解决该类实际问题更具有重要意义.研究了赋权多阶段有向图的最短路问题,从图上逆序标号法、表上作业法和动态规划法不同的角度对文中实例给出了赋权多阶段有向图最短路求解方法。     

关于整正则有向图的补图与联图

把补图与联图这两种二元运算应用于正则有向图,发现无向正则图中的一些定理在有向图中亦成立,使定理的应用范围更加宽广,在此基础上进一步探讨了其成为整谱图的条件,从而得到了构造整谱有向图的新方法,可以用来构造新的整谱有向图.     

平面二部图的完美匹配集合上的有向根树结构及其生成

图的完善匹配或１－因子指覆盖子其所有顶点的独立边集。对含有完善匹配的平面二部图，其所有完美区通过某旋转变换形成层次组织结构。可用有向根树或半格表示。建立了平面二部图的完善匹配集合上新有向根树结构并可通过算法来生成。