运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2002年
4期
57-64
,共8页
线有向图%全有向图%幂敛指数%周期%邻接矩阵
線有嚮圖%全有嚮圖%冪斂指數%週期%鄰接矩陣
선유향도%전유향도%멱렴지수%주기%린접구진
Line digraph%Total digraph%Index of convergence%Period%Adjacencymatrix
设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为有向圈Cn时,k(T(D))=2n-1.2.对任意非平凡强连通图D,k(T(D))≥Diam(D)+1.我们还证明了以上界是不可改进的最好界.
設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為有嚮圈Cn時,k(T(D))=2n-1.2.對任意非平凡彊連通圖D,k(T(D))≥Diam(D)+1.我們還證明瞭以上界是不可改進的最好界.
설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위유향권Cn시,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) de-note the index of convergence and the period of D, respectively. Following resultsare obtained in this paper: 1. For a non-trivial digraph D, then p(T(D)) = 1, andk(T(D)) ≤ max{2p(D) - 1, 2k(D) + 1). Especially, we prove that k(T(D)) ≤ k(D) + 1 ifD is a primitive digraph; and k(T(D)) = 2k(D) - 1 if there are not directed cycles in D;and k(T(D)) = 2n - 1 if D is a directed cycle Cn. 2. For a strongly connected digraphD, then k(T(D)) ≥ Diam(D) + 1, where Diam(D) denotes the diameter of D. We alsoproved that these bounds are best.
