有向Kautz图上的随机游动.pdf

第 43 卷 　第 6 期 ( ) Vol. 43 　No. 6 厦门大学学报 自然科学版 　2004 年 11 月 Journal of Xiamen University (Natural Science) Nov. 2004 　 ( ) 文章编号 2004 有向 Kautz 图上的随机游动 陈 海 燕 (厦门大学数学科学学院 ,福建 厦门 361005) 摘要 : 首先给出了有向 Kautz 图上简单随机游动任意两点之间平均击中时间的表达式及其最大和最小值 ,并证明了 快速收敛性. 最后给出了有向 Kautz 图上简单随机游动从任一单点分布到稳定分布的一个最优停时规则 ,从而得到 了最优均值. 关键词 : 有向 Kautz 图;随机游动;平均击中时间 ;停时规则 中图分类号: O 157. 5 文献标识码 :A 　　　　　　　　　　　　　　　 　　有向 Kautz 图 ,有向 de Bruijn 图以及超立方体 并且 K ( d , k) 是强连通的 d 正则有向图. 由于都具有一些非常好的拓扑性质,例如高容错 ,易 定义2 　设 G = ( V , E) 是一个有向连通图, 图 [1 ] ( ) 扩充等 被认为是现在和将来并行计算机互连网络 G 上的一个随机游动就是 V = V G 上的一个马尔 最具有竟争力的 3 大拓扑结构而受到广泛关注. 其 可夫链 X 0 X 1 …, 它的转移概率矩阵记为 P = 中超立方体是目前人们研究最深入的网络结构 ,现 ( p ij) i , j ∈V , 其中 p ij 是从 i 到j 的一步转移概率. 特别 在人们不仅了解它的各种拓扑性质 ,而且对它上面 + 1 Γ ( ) [2～4 ] 地, 若 j ∈ i , 有 p ij = + ( ) ; 否则 p ij = 0 ; 则 的随机游动也早已进行了深入的研究 . 关于有 d i + 向 Kautz 图 ,有向 de Bruijn 图 ,虽然他们的拓扑性质 此随机游动称为图 G 上的简单随机游动, 这里 Γ [1 ,5～7 ]