Kautz网络中的路与宽距离.pdf

维普资讯 第37卷第3期 数 学 进 展 Vo1．37，No．3 2008~6月 ADVANCESIN MATHEMATICS June，2008 Kautz网络中的路和宽距离 邓志国 ，徐宝根， 刘二根 (华东交通大学数学系，南昌，江西，330013) 摘要：用K(d，他)表示Kautz网络，该网络由于具有优良的拓扑性质而频频出现在文献中被广 泛研究，本文针对该网络中的路和宽距离得到如下结论：设 和 Y是中两个不同的顶点，P是一 条最短 ，)一路，Q是一条最短 (Y，)一路，那么 (1)如果P和Q相交于不同于 和Y的内部结 点，那么lPl+lQl他；(2)PuQ最多由3个圈的并组成；(3)如果有d(x，Y) 他一d+3，那 么 (d一1)一宽距离dd一1(K(a，他)：，Y)=他十1．作为结论 (3)的一个应用，本文表明，如果d 3 和他 d一2，那么独立数az，d一1(K(d，他))=口z，d(K(d，他))=d+ _。，其中z=1，2，… ，他． 关键词：(z，)一独立数；Kautz网络；宽距离 MR(2000)主题分类：05C12，90B10／中图分类号： O157．5 O157．5 文献标识码；A 文章编号： 1000-0917(2008)03—0337-05 在并行与分布式系统中，互连网络的设计是一个很重要的问题，到目前为止，有许多互连网 络结构在文献中被提出并得到了广泛的研究 [1-6】．其中，Kautz网络是一种非常有效的拓扑结 构，被证明具有非常好的性质而频频出现在文献中 [8--101． 互连网络的拓扑结构通常用一个图来表示，在本文中，我们交互使用如下概念：网络和图， 处理器与顶点，链路与边．当用G来表示一个实时网络处理系统，(f，)一独立数Oq,w(G)是指这 样—个最大的顶点集的顶点个数：对于该顶点集的任意两个顶点，它们之间不能够在规定的时限 f内用 条内点不交的路通信．因此， (f，)一独立数是衡量互连网络性能的—个重要参数 [11】． 本文第 1部分介绍了一些相关定义和符号．第 2部分讨论了关于Kautz网络中的路和宽距 离，并且得到了Kautz网络的一些独立数．第 3部分是本文的结论． 1相关定义和符号 — 个Kautz网络K(d，n)是指按如下方式定义的—个有向图：顶点集定义为V={z1z2… z ：Xi∈{0，1，… ，d)， ≠Xi+1，i=1，2，… ，n一1)并且边集E是由所有以顶点z1z2…z 为 起点的d条以X2X3…zOt为终点的有向边组成，其中Ot∈{0，1，… ，d)并且 a≠z．K(d，n) 具有am十am_1个顶点，d计 +d”条边并且连通度为 d(见 [7】)． 本文用G=G(E)来表示一个简单图，其中V=v(a)和E：E(G)分别表示图G的顶 点集和边集． (z，Y)表示从顶点z到顶点Y的一条边．假设z=z1z2…z和Y=YIY2… 是K(d，n)的两个不同顶点，P(x，Y)表示从z到Y的一条有向路，IP(x，)I表示路P(x，Y)的 长度，d(x，Y)表示从z到 Y的最短路的长度． 1(x，Y)表示顶点z的尾部和顶点Y的首部重 收稿 日期：2006．1l一13；收到修改稿 日期： 2007-05-15． 基金项目；国家 自然科学基金 (No，江西省自然科学基金 (No．0611009) E-mail： dzgOustc．edu 维普资讯 338 数 学 进 展 37卷 迭元素的最大个数，设这些重迭元素为 Z2… ，那么Z(X，)就是最大的f使得 一… =玑= ，= 1，2，… ，1． G中内点不交的 (，)一路的集合称为一个 (，)一路系，一个路系c(c：，)