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

SPANNING TREES AND BROADCASTING IN EXTENDED DE BRUIJN DIGRAPH

扩展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.