扩展de Bruijn图的生成树和广播  

SPANNING TREES AND BROADCASTING IN EXTENDED DE BRUIJN DIGRAPH

作　　者：高随祥[1] 杨德庄[1] 

机构地区：[1]中国科学院研究生院数学系

出　　处：《系统科学与数学》2003年第1期109-116,共8页Journal of Systems Science and Mathematical Sciences

基　　金：国家自然科学基金(10171095;10001031)资助课题;中国科学院研究生院院长基金(yzjj200105)资助项目

摘　　要：扩展de Bruijn图EB(d,m;h1,h2,…,hk)是de Bruijn图的一种推广,它是一种再要的网络互连结构.本文主要研究扩展de Bruijn图中的有根生成树,证明了对任何顶点u和任意整数r:2≤r≤d,扩展de Bruijn图都有以u为根且深度为[log(?),d]·max{hi:1≤i≤k}的rk-叉生成树,并由此获得了扩展de Bruijn图的广播时间的上界.Extended de Bruijn digraph EB(d, m; h1,h,2, ,hk) is an extension of de Bruijn digraph, which is an important interconnection architecture for multiple processor network systems. This paper studies the spanning trees with root of extended de Bruijn digraph. It is derived that for any extended de Bruijn digraph EB(d, m; h1,h,2, ,hk) and any integer r: 2 < r < d, there exists on rk- ary spanning tree rooted at an arbitrarily given vertex, whose depth is D [logr d] . This presents an upper bound of minimum broadcasting time of the extended de Bruijn digraph.

关 键 词：扩展deBruijn图 生成树 广播 多处理器系统 

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