一类本原图的Scrambling指数

文章主要研究了一类特殊的含有6个圈3个不同圈长的本原有向图的Scrambling指数,通过分析每一点经过t长途径可到达的点的集合,给出了此类图的Scrambling指数.     

极大局部边连通和超级局部边连通二部有向图的邻域条件

本文主要证明了对于n阶二部有向图D，当最小度δ≥3,对任意同部顶点x，y,有min{|N⁺(x)∪N⁺(y)|，|N^-(x)∪N^-(y)|}≥(n+3)/4]时,D为极大局部边连通的；当最小度δ≥4,对任意同部顶点x，y,有min{|N⁺(x)∪N⁺(y)|,|N^-(x)∪N^-(y)|}>(n/4)+1时,D为超级局部边连通的。我们证明了条件的最好可能性及结果与原有结果的独立性。     

一类有向图的星边弧染色

提出了有向图的星边弧染色的概念,并定义了有向图D的星边弧色数,记为(→x)s′(D).运用Lovász局部引理证明了若有向图D=(V,A)的最大出度△+与最大入度A-满足线性关系△+=k△-(△(D)≥7,k＞0),则(→x)s′(D)≤16[(√1+k2)/1+k△3/2]*,这里[*]*表示上取整.     

2—有向循环图的同构

本文得到了2-有向循环图 G(a,b,N)与 G(a＇,b＇,N)同构的充要条件为:(a,b,N)=(a＇,b＇,N)=K且 a＇b≡ab＇(mod KN);或 a＇a≡b＇b(mod KN),这里(x,y,z)表示整数 x,y,z 的最大公约数。     

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

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

不可约非负矩阵的周期与指标集的分类算法

文［１］和［２］讨论了不可约非负矩阵指标集的分类理论，在此基础上，本文给出了不可约非负矩阵的周期与指标集的分类算法。这一算法能同时求出周期与同余类，当矩阵的阶不大时，该算法容易在图上实现。     

决策影响图在设备可靠性系统分析中的应用

决策影响图是决策分析的一种新的图形表征求解方法，它用无回路的有向图表征决策变量、随机变量和目标函数之间的相关关系，并进行推理分析、信息分析和灵敏度分析等．本文运用影响图分析法研究设备可靠性分析问题．     

具有唯一定长路的有向图的一个注记

Ｌａｍ和ｖａｎ Ｌｉｎｔ构造了一类具有唯一定长路的有向图Ｄ（ｃ，ｋ），其阶为ｎ＝ｃ＾ｋ＋１，并证明Ｄ（ｃ，ｋ）的自同群包含一个２（ｃ＋１）阶二面体群，其中ｃ为大于１的整数，ｋ为大于１的奇数。本文利用（０，１）矩阵方程的性质证明，对任意的整数ｃ＞１和奇数ｋ＞１，存在ψ（ｋ）（ψ为Ｅｕｌｅｒ函数）个ｎ＝Ｃ＾ｋ＋１阶具有唯一定长路的有路的有向图；它们互不同构且其中每一个图的全自同构群都是２（Ｃ＋１）阶二     

关于猜想γ（A）≤（m－1）~2＋1

设Ａ是一个非负矩阵，若存在正整数ｋ，使得Ａ~ｋ＞０，则称Ａ为本原矩阵，而上述ｋ的最小者称为Ａ的本原指数，记作γ（Ａ）．设ｍ为Ａ的最小多项式的次数，ｇ为Ａ的伴随有向图的围长，当ｇ≤ｍ－１时，猜想γ（Ａ）≤（ｍ－１）~２＋１成立。     

一类具有唯一定长路的有向图的自同构群

Ｌａｍ和Ｖａｎ Ｌｉｎｔ 在推广友谊定理时构造了一类具有唯一定长路的有向图（这里 用Ｄ（ｃ，ｋ）表示），并证明了Ｄ（ｃ，ｋ）的自同构群包含一个２（ｃ＋１）阶二面体群。 木文利用Ｄ（ｃ．ｋ）的邻接矩阵的性质证明这个二面体群就是Ｄ（ｃ，ｋ）的全自同构群， 从而解决了 Ｌａｍ和 Ｖａｎ Ｌｉｎｔ作中遗留的问题。