全有向图的幂敛指数(英文)  

The Index of Convergence of the Total Digraph

作　　者：晏卫根[1] 张福基[2] 

机构地区：[1]集美大学师范学院数学系,厦门361021 [2]厦门大学数学系,厦门361005

出　　处：《运筹学学报》2002年第4期57-64,共8页Operations Research Transactions

基　　金：ThisworkissupportedbyNSFC(19971071)andFJECF(JA97138).

摘　　要：设D为有向图,T(D)为D的全有向图(Total-digraph),k(D)与p(D)分别为D的幂敛指数(Index of convergence)与周期(Period).本文证明了,1.对任意非平凡有向图D,p(T(D))=1,k(T(D))≤max{2p(D)-1,2k(D)+1},特别地,当D为本原有向图时,k(T(D))≤k(D)+1;当D不含有向圈时,k(T(D))=2k(D)-1;当D为有向圈C_n时,k(T(D))=2n-1.2.对任意非平凡强连通图D,k(T(D))≥Diam(D)+1.我们还证明了以上界是不可改进的最好界.Let D be a digraph, T(D) denote the total digraph of D, k(D) and p(D) denote the index of convergence and the period of D, respectively. Following results are obtained in this paper: 1. For a non-trivial digraph D, then p(T(D)) = 1, and k(T(D)) ≤ max{2p(D) -1,2k(D) + 1}. Especially, we prove that k(T(D)) ≤ k(D) + 1 if D is a primitive digraph; and k(T(D)) = 2k(D) - 1 if there are not directed cycles in D; and k(T(D)) = 2_n - 1 if D is a directed cycle C_n. 2. For a strongly connected digraph D, then k(T(D)) ≥ Diam(D) + 1, where Diam(D) denotes the diameter of D. We also proved that these bounds are best.

关 键 词：线有向图 全有向图 幂敛指数 周期 邻接矩阵 

分 类 号：O157.5[理学—数学]