无向双环网络G(N;±1,±s)紧优分布特性

研究了无向双环网络G(N;±1,±s)的紧优分布特性,提出了一种快速仿真算法,计算出了4≤N≤1 000中任意节点数N存在的紧优个数n,仿真出了4≤N≤1 000的n-N紧优分布率和n/(N-3)-N紧优分布率,给出了其中无紧优无向双环网络的N值.仿真结果表明,n-N分布呈现平稳的波动特性,n不随着N递增,而n/(N-3)-N随着N的增加呈波动性下降的趋势,且与N的奇偶性无关.     

关于非单位步长的紧优双环网络G（N；r，5）

双环网络是计算机互连网络或通讯系统的一类重要拓扑结构，其图论模型是指一个有向图G（N；r，S）；每个顶点记为0，1，2，…，N-1，并从每个顶点i发出两条有向边i→i＋r（mod N）和i→i＋s（mod N），其中r和S是自然数，且1≤r≠s〈N．若G（N；r，s）存在k紧优双环网络，G（N；1，s）存在k1紧优双环网络，且满足k1〉k，称G（N；r，s）为非单位步长双环网络．在L形瓦理论的基础上，给出一个求非单位步长双环网络的方法，求得两个关于模型G（N；r，s）的紧优双环网络无限族；结合中国余数定理和数论中的素数理论，给出一个求非单位步长双环网络无限族（k1-k≥1且k〉0）的方法；作为具体应用，求得两个非单位步长双环网络无限族（k1-k≥2且k〉0）．     

基于圈的紧优双环网络G(N;1,s)求解算法

提出基于圈的紧优双环网络G(N;1,s)求解算法,利用VB6．0作为编程语言、SQL Server 2000作为数据库来实现这一算法,对任意给定N,而2≤s≤N-1的这样一族双环网络中的所有紧优双环网络都可以计算出来,结果存入数据库．算出N≤200的所有紧优双环网络。     

有向双环网络G(N;r,s)双紧优分布特性研究

提出双紧优的概念来构造高效的有向双环网络G(N;r,s),给出了任意有向双环网络的直径(D(N))和宽直径(D2(N))的定义及相关证明,得出了它们之间的关系D2(N)≥D(N)+1.给出了任意有向双环网络G(N;r,s)的双紧优点的仿真分布图.结果表明,有向双环网络G(N;r,s)的紧优点不一定是双紧优点,且双紧优点的分布无规律.     

无向双环网络G(N;±r,±s)直径求解方法

提出新的无向双环网络G(N;±r,±s)的直径求解法———分步法;并得到一种新的直观图———螺旋环,研究了螺旋环的性质;给出了无向双环网络的直径d(N;±r,±s)的显式公式;给出了N,s都固定的直径算法;在N固定,且2≤r相似文献   

关于k紧优双环网络

给出了判断N个节点存在k(k≥0)紧优双环网络的一个算法,得到该算法的复杂性为O(N1/4).作为具体应用,给出一个7紧优双环网络的无限族.首次给出了一个7紧优双环网络G(81 190 689;16 035),其直径为15 612.     

若干新的紧优、几乎紧优有向双环网络无限族

本文给出了若干族新的紧优和几乎紧优的有向双环网络无限族.     

关于非单位步长的紧优双环网络G(N;r,s)

双环网络是计算机互连网络或通讯系统的一类重要拓扑结构,其图论模型是指一个有向图G(N;r,s):每个顶点记为0,1,2,…,N-1,并从每个顶点I发出两条有向边I→I r(mod N)和I→I s(mod N),其中r和s是自然数,且1≤r≠s＜N.若G(N;r,s)存在k紧优双环网络,G(N;1,s)存在k1紧优双环网络,且满足k1＞k,称G(N;r,s)为非单位步长双环网络.在L形瓦理论的基础上,给出一个求非单位步长双环网络的方法,求得两个关于模型G(N;r,s)的紧优双环网络无限族;结合中国余数定理和数论中的素数理论,给出一个求非单位步长双环网络无限族(k1-k≥1且k＞0)的方法;作为具体应用,求得两个非单位步长双环网络无限族(k1-k≥2且k＞0).     

4紧优和5紧优双环网络无限族

双环网络是计算机互连网络或通讯系统的一类重要拓扑结构。本文推广了文献[6]的主要结论，给出一个较一般的紧优双环网络无限族构造方法，从而得到若干类4紧优和5紧优双环网络无限族。     

3类6紧优双环网络无限族

在关于L形瓦理论的基础上 ,结合中国余数定理 ,给出了 3类 6紧优双环网络无限族 .     

一种新的紧优双环网络无限族构造方法

提出一种新的紧优双环网络无限族的构造方法.该方法从一个具体的不含k(0≤k≤m)紧优双环网络的N0出发,通过求一个同余方程方程组的所有解,构造不含k(0≤k≤m)紧优双环网络的无限族.从一个具体的可实现L形瓦出发,利用其h和y互素条件,构造可实现L形瓦的无限族.作为应用,给出若干7紧优和8紧优双环网络无限族;解决了几个关于紧优双环网络无限族的公开问题.     

奇异k紧优双环网络无限族的构造

提出构造任意奇异k紧优双环网络无限族的一种方法.对于整数k>1/2m+(3+(2i-1)2)/24,m≥(i-i2-1)/3,设N(t)=3t2+(2i-1)t+B,其中B=k2+k-m,1≤i≤3且N(t)∈Ii(t),证明了对于若干组i和m,可以构造奇异k紧优双环网络无限族.     

双环网络G(N;1,s)等价生成树

提出研究双环网络G(N;1,s)的抽象模型--等价生成树,并对其性质进行了研究,给出了双环网络G(N;1,s)等价生成树的构造方法.提出基于等价生成树G(N;1,s)的直径d(N;1,s)的求解算法,并给出了其显式公式,利用C语言编程对等价生成树的结构模型进行了仿真.结果表明:算法不仅可在有限时间内求出G(N;1,s)的所有直径,而且可方便地得到源结点到所有其他结点的最短路径.算法的复杂度为O(N).     

一类9紧优双环网无限族

在L形瓦理论的基础上,结合数论中的素数理论,通过计算机搜索,首次得到9紧优双环网N（2 500 139）,其中N（t）=3t2＋4t-2 222 698。用理论证明N（2 500 139）是9紧优双环网,并且给出一个含有参数的9紧优双环网无限族;同时指出了参考文献中的若干错误。     

一类无向双环网络的最优路由算法

设n=qh r,这里1≤r≤h-1,w=「(h-1)/(q r) .对于一类较为普遍的满足条件h≥wr的无向双环网络G(n,1,h),本文给出了一种时间为常数步的最优路由算法.     

无向双环网络直径的估计

设h,n是满足条件2≤h＜n/2的两个正整数.无向双环网络G(n,1,h)是一个无向图(V,E),这里顶点集V=Zn={0,1,2….,n-1},边集E={i→i 1(modn),i→i-1(modn),i→i h(modn),i→i-h(modn)|i=0,1,2,…,n-1}.双环网络在并行处理的互连网络与局域通信网络的设计中有着重要的应用.利用G(n,1,h)的直径与平行四边形中格点间距离的关系,我们给出了无向双环网络G(n,1,h)新的直径上界估计.设n=qh r这里0≤r＜h.当q＜r时,我们所给出的上界估计比D.Z.Du等人所给的上界估计精确.     

基于树的无向双环网络G(N;±r,±s)寻径策略

提出了新的无向双环网络G(N;±r,±s)的直径求解方法,将其图论模型中的节点进行了重新排列,得到了一种基于树的路由模型,研究了该树型结构中与路由相关的一些性质;给出了计算无向双环嘲络G(N;±r,±s)直径d(N;±r,±s)的显式公式;证明了无向双环网络G(N;±r,±s)的直径等于树高;验证了Boe-sch和Wang等提出的无向双环网络G(N;±r,±s)直径的下界.     

基于二叉树的有向双环网络最优路由算法

提出了有向双环网络G(N;r,s)路由模型--二叉树模型,给出了一种新的寻径策略--基于二叉树层的寻径策略,以及计算有向双环网络G(N;r,s)直径d(N;r,s)的显式公式,证明了有向双环网络G(N;r,s)的直径等于二叉树模型的树高,研究了二叉树模型中与路由相关的一些性质.与传统的方法相比,本算法提高了系统的寻径效率.     

关于有向双环网络G(N;r,s)平均直径的研究

针对有向双环网络的最小路径图,给出了一个快速计算有向双环网络平均直径的高效算法.根据该算法,只要知道有向双环网络G(N;r,s)的3个参数N,r和s,就能计算出L-型瓦的4个参数a,b,p和q,从而计算出平均直径.对直径与平均直径之间的关系进行了仿真研究,结果表明:在一个无限族中,直径与平均直径的分布呈轴对称图形;同一网络的平均直径约等于直径的一半;在任意无限族中,当直径达到下界值时,平均直径不一定达到下界值,但当平均直径达到下界值时,直径一定达到下界值.最终表明平均直径比直径能更好地衡量网络传输效率.     

最优双环网络的构造算法

在刘焕平等人工作的基础上,给出一个k(k≥0)紧优双环网络的构造算法及其若干具体应用.给出N最小的5紧优双环网络G(417 289;47 721),其直径为1 122;N最小的6紧优双环网络G(7 243 747;65 576),其直径为4 666.