高校应用数学学报A辑.pdf

《高校应用数学学报A辑.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、高校应用数学学报A辑Appl.Math.J.ChineseUniv.Ser.A2000,15(2):147～1512紧优双环网络无限族徐俊明(中国科学技术大学数学系,合肥230026)摘　要找到两个2紧优双环网络的无限族.这肯定地回答了李乔等人于1993年提出的一个问题.关键词　双环网络;循环有向图;直径;最优;紧优分类号　(中图)O15719,TP302;(1991MR)05C40,68M10.文献标识码A　　文章编号100024424(2000)0220147205双环网络是计算机互连网络或通讯系统的一类重要拓扑结构,其

2、图论模型是指这样一个有向图G(N;s):它的每个顶点记为0,1,2,⋯,N-1,并从每个顶点i发出两条有向边i→i+1(modN)和i→i+s(modN),其中s是自然数,而且1

3、Z,G(N;s)称为k紧优的,若d(N;s)=d(N)=lb(N)+k.0紧优和1紧优通常称为紧优和几乎紧优.设N(t)是一个定义在Z上的正整数值函数.{N(t):t∈Z,t≥t0}称为含k紧优双环网络的无限族,如果对任何t≥t0,都存在s(t)使得G(N(t);s(t))为k紧优的.{N(t):t∈Z,t≥t0}称为不含k紧优双环网络的无限族,如果对任何t≥t0和s(t)都有d(N(t);s(t))>lb(N(t))+k.在文献[7]中,李乔等人提出一个系统的构造方法,找出一系列含紧优和几乎紧优双环网络的无限族.同时提出研

4、究下列问题:对于给定的k>1,找出k紧优双环网络无限族.最[9]近作者找到两个不含紧优和几乎紧优双环网络的无限族.在此结果的基础上,本文找到两个2紧优双环网络的无限族.§1　记号和引理[10]因为G(N;s)是点可迁的强连通有向图,所以要研究其直径只需考察从顶点0到其收稿:1999202225.国家自然科学基金(19971086),博士点基金和中国科学院基金资助.©1995-2004TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.148高校应用数学学报A辑第15卷第2

5、期它顶点的距离.为此,在笛卡尔平面直角坐标系中,令X轴的单位为1(或s),Y轴的单位为s(或1).把第一象限中的所有格点(x,y)按下列顺序排成序列:(0,0),(1,0),(0,1),(2,0),(1,1),(0,2),⋯,(j,0),(j-1,1),⋯,(j-i,i),⋯,(1,j-1),(0,j),⋯.并且依次在每一格点(x,y)的右上角的单位方格内安置一个数n∈{0,1,2,⋯,N-1},其中n≡x+ys(modN).如果在此之前数n已出现过,则空出此方格,考察下一个格点,直到所有的数0,1,[1,6]2,⋯,N-1

6、都出现时为止.已经证明:由G(N;s)所确定的N个方格组成的构图呈图1所示的面积为N个单位的L形域,记为L(N;s).如图1所示,由l,h,x,y确定的面积为N的L形区域称为L形瓦,记为L(N;l,h,x,y),其中l,h,x,y都是整数,并且规定l,h≥2,0≤x

7、,x,y)称为k紧瓦,如果D(L)=lb(N)+k.根据上述记号和定义可知,对任何G(N;s),均有d(N;s)=D(N;s),并且d(N)≥D(N).若G(N;s)为k紧优的,则它所对应的L形瓦一定是k紧瓦.反之不真.L形瓦L(N;l,h,x,y)称为可实现的,如果存图1在一个G(N;s)使得L(N;s)=L(N;l,h,x,y).[7]引理1L形瓦L(N;l,h,x,y)可实现的充分必要条件是g.c.d.(y,h′)=1,且此条件成立时,L(N;l,h,x,y)可被惟一的G(N;s)实现,其中s≡Al-Bl′(modN)

8、,A和B是满足Ay+Bh′=1的某两个整数.[7]引理2　对任何正整数N,必存在t∈Z使得N=N(t)∈I1(t)∪I2(t)∪I3(t),其中:222222I1(t)=[3t+1,3t+2t],I2(t)=[3t+2t+1,3t+4t+1],I3(t)=[3t+4t+2,3(t+1)]是