适用于动态有向图路径检索的一种数据结构

给出一种表达加权有向图的数结构，它使得对此有向图进行“插入”操作后，只需进行Ｏ（ｎ＾２）时间的维护工作，就可使得每对结点间的最短路径迅速地得修整。     

一类含有奇数个顶点的三色有向图本原指数上界

一个三色有向图D是本原的,当且仅当存在非负整数h、k和v,且h+k+v0,使得D中的每一对顶点(i,j)都存在从i到j的(h,k,v)-途径,h+k+v的最小值定义为三色有向图D的本原指数.研究了一类三色有向图,它的未着色图中包含2佗-4个顶点,一个n-圈、一个(n-2)-圈和一个2-圈,给出了本原指数上界.     

有向图的边割(X,Y)中｜X｜和｜Y｜的下界与有向图的极大性和超级性

在已有的极大边连通、超级边连通、极大局部边连通有向图概念的基础上,提出超级局部边连通有向图的概念,对一般的、二部的、基础图的团数至多为p的有向图、定向图分别给出｜(X,Y)｜＜δ(D)的边割(X,Y)、非平凡的最小边割(X,Y)中｜X｜和｜Y｜的下界,据此分别得到极大边连通、超级边连通有向图的最小度条件.类似地分别得到...     

有向图及其道路同调的△集刻画

近几年来,A.Grigor'yan,Y.Lin,Y.Muranov,V.Vershinin和S.T.Yau等人研究了有向图上的道路,定义了有向图的道路同调并将其作为重要的代数工具来研究有向图的拓扑结构.将有向图上的道路集合描述为△集的分次子集,通过推广超图的嵌入同调定义△集的分次子集的嵌入同调并证明有向图的道路同调可以描述为△集的分次子集的嵌入同调.     

求最短路问题的改进算法

本文对图论中含有负权的最短路问题的算法进行了讨论 ,给出了一个具有“可节省存储空间、提高运算速度、易编程实现”等优点的改进算法 (算法三 ) ,并通过例题进一步验证了该改进算法的优越性 ,具有一定的现实意义 .     

细胞有向图自动机及算法

本文提出了细胞（ｄ１，ｄ２）－有向图自动机的定义，研究了怎样用它求得（ｄ１，ｄ２）－有向图的广度优先混合方向支撑树，单向树及强连通分量等问题并给出了相应的并行算法和时间复杂度分析。     

本原极小强连通有向图1—指数的下界

本文给出了n阶本原极小强连通有向图1-指数的下图:expD(1)4.且这个下界是可以达到的.     

有限循环群上的Cayley有向图的哈密顿分解

本文给出了有限循环群上的Cayley有向图Cay(M,G)可哈密顿分解的一个充分条件,并证明了当|M|=2时此条件还是必要的.     

极小k边连通有向图中出度为k的点

设k是正整数，D是极小k边连通简单有向图．Mader猜测(见Combinatorics，Paul Erd6s is Eighty (V01．2)，Budapest，1996)D中至少有k 1个出度为k的点．在k=1时，Mader已证明成立．考虑志≥2，运用Edmonds等人在研究组合优化问题中引入的对无交叉组的树表示，证明了在志≥2时，D中至少有3个出度为k的点．