有向循环图与有向圈的乘积的研究  

Research on the Product of Cirulant Digraph and Directed Cycle

作　　者：周永生[1] 

机构地区：[1]广东职业技术师范学院计算机科学系,广东广州510665

出　　处：《广东职业技术师范学院学报》2000年第4期1-5,共5页Journal of Guangdong Polytechnical Normal University

基　　金：国家自然科学基金资助项目!(1990 10 12 )

摘　　要：本文讨论了有向循环图与有向圈的乘积 ,得到了以下结果 :( 1)有向循环图D(n ;s1,s2 ,… ,si- 1,nl ,si+1,… ,sr)是连通的充要条件。( 2 )设有向循环图D(n ;s1,s2 ,… ,si- 1,s,si+1,… ,sr)连通 ,且n =ls,gcd(n ,s1,s2 ,si- 1,si+1,… ,sr) =l(l>2 ) ,则D(n ;s1,s2 ,si- 1,s,si+1,… ,sr) D(s ;s1l,s2l ,… ,si- 1l ,si+1l ,… ,srl)× μl。( 3)设D(n0 ;s1,s2 ,… ,sr)是连通 ,则D(n0 ;s1,s2 ,… ,sr)×μn1× μn2 ×… μns为有向循环图 gcd(ni,nt) =1(i,t =0 ,1,2 ,… ,s ;i≠t)。gcd(n ,s1,s2 ,… ,sr)表示n ,s1,s2 ,… ,sr 的最大公约数 ,μlIn this paper the product of the circulant digraphs and directed cycle is discussed.We use gcd(n,s 1,s 2,s r) to denote the greatest common divisor of n,s 1,s 2,…,s r,and μ l the dicycle with l vertices.The following results are obtained. 1)Necessary and sufficient condition of circulant digraph D(n;s 1,s 2,…,s i-l ,nl,s i+1 ,…,s r)is connected. 2)Suppose that gcd(n,s 1,s 2,…,s i-1 ,s i+1 ,…,s r)=l(l>2),n=ls,and D(n;s 1,s 2,…,s i-1 ,s,s i+1 ,…,s r)is connected.Then D(n;s 1,s 2,…,s i-1 ,s,s i+1 ,…,s r)D(s;s 1l,s 2l,…,s i-1 l,s i+1 l,…,s rl)×μ l。 3)Suppose that D(n 0,s 1,s 2,…,s r) is connected.Then D(n 0,s 1,s 2,…,s r)×μ n 1 ×μ n 2 ×…×μ n s (s i≠nl;1≤i≤r) is a circulant digraphgcd(n i,n t)=1(i,t=0,1,2,…,s;i≠t)。

关 键 词：有向循环图 有向圈 乘积 连通 有向分支 同构 自反模 简单有向图 

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