双环网络直径点和宽直径点的分布特性

针对单个有向单位步长双环网络G(N;1,h),根据其直径和宽直径的定义,并借助其等价L形瓦进行直径和宽直径路由的构造,证明了任意双环网络的直径点和宽直径点均小于或等于2个;证明了直径点一定分布在L形瓦的第一象限内,宽直径点一定分布在L形瓦的两个坐标轴上.对于一族有向单位步长双环网络G(N;1,2≤h≤N-1),随着步长h的递增,该族双环网络路由的节点顺序具有由小到大变为由大到小的特点,借助VB6.0编程仿真了该族双环网络直径点和宽直径点的分布图,发现其直径点和宽直径点具有波动下降的特征;直径点往往大于宽直径点;步长h在中间处两者的值最大;对于某个双环网络,如果直径点有两个,则其宽直径点必有两个.

广义容错直径和广义宽直径

容错直径和宽直径是度量网络可靠性和有效性的重要参数.本文推广了容错直径和宽直径的概念,并相应地推广了两个著名结果.

有向双环网络的宽直径公式

给出了有向双环网络G(n;s1,s2)的宽直径公式,它由G(n;s1,s2)所确定的L-形瓦的4个参数a,b,p,q表示.令u=a-p,v=b-q,用D(G)与D2(G)分别表示G(n;s1,s2)的直径与宽直径,则(1)当u=1,v=1时,D2(G)=n-1.(2)当u>1,v>1时,D2(G)=D(G)+1=max{a+b-p-1,a+b-q-1}.(3)当u=1,v>1时,D2(G)=「b-1/v」+a+v-2.(4)当u>1,v=1时,D2(G)=「a-1/u」+b+u-2.

关于图的容错直径和宽直径

容错直径和宽直径是度量网络可靠性和有效性的重要参数 .对任何k连通图 ,它的容错直径Dk 不超过宽直径dk.论文证明d2 ≤max (d1- 1 ) (D2 - 12 d1- 1 ) +1 ,D2 +1 ;给出d1=2时d2 =D2 +1的一个充分必要条件 :d2 =3或d2 =4且达到d2

关于3连通图的容错直径和宽直径

容错直径和宽直径是度量网络可靠性和有效性的重要参数。对任意k连通图,它的容错直径D_k不超过宽直径d_k。本文证明:当D_2=2时,d_3≤max{D_3+1,2D_3-2};当D_2≥3时,d_3≤(D_2-1)[2(D_2-1)(D_3-1)-D_2-2]+1。

关于图的连通度、宽直径、顶点数函数的讨论

FrankHsuD博士 (1994年 )中提出了w_距离 (w_distance)和w_直径 (w_diameter)的概念 ,介绍了“函数h(k ,d ,n)” ,其中的参变数包含连通度k ,最大直径d和顶点个数n .该文对这个函数进行了讨论 ,给出了部分结果 .

双环网络并行最优寻径策略及宽直径的研究

将双环网络拓扑结构映射到平面直角坐标系,基于直角坐标系研究双环网络的并行最优寻径方法。首先研究坐标轴上节点及其等价节点的分布规律,建立等价节点分布模型,得出基于等价节点的并行最优寻径策略及双环网络宽直径求解方法。在双环网络最小路径图(MDD)的基础上拓展,提出并行路径图(PDD)的设计思路并予以仿真实现,基于PDD图,设计两点间2条内点不交的并行最短路径的快速求解方法。仿真实验表明,宽直径分布随步长的变化呈现一定波动性,相对于传统的寻径方式,并行最优寻径明显提高了网络传输效率。

关于4连通图的容错直径和宽直径

容错直径和宽直径是度量网络可靠性和有效性的重要参数.对任意k连通图,它的容错直径Dk,不超过宽直径dk.本文证明:当G是4连通图时,若D3=2,d4≤{D4+1,8D4?17};若D3≥3,d4≤max{3D2(3D4?D2?13)+1,2D2D3(D4?2)+D2?D2+1,3D2(D3?1)(D4?2)?D2?D2+1}12332并2222且证明对n(n≥3)连通图,当Dn=2时,2≤dn≤3.

两类图的W-宽直径

图的直径与宽直径是并行与分布式网络通信延迟的度量,据此研究了两类图的W-宽直径,在n点圈Cn中添加t条边得到图C(n,t),讨论了图C(n,t)的2-宽直径的最小值问题,并得到其上下界,进而提出了h(n,t)精确取值的猜想;在分析联图连通度的基础上,导出了联图的W-宽直径上界估计式。

关于2-连通图的容错直径与宽直径的注记

在实时系统中,容错直径和宽直径是两个度量网络信息传输延迟和性能的重要参数。对于一般的图G,确定它的容错直径Dk困难很大,而确定它的宽直径dk却是个NPC问题,因此讨论它们之间的关系显得很重要。该文讨论了2连通图的容错直径与宽直径之间的一些性质,给出:若G是直径为2的2连通图,则d2=D2+1的充要条件为:存在两顶点u、v∈V(G),其中uv∈E(G),使得L(G)=L(G;u,v)=4或5。

带弦圈的最小2宽直径(英文)

设k为正整数,G是简单k连通图.图G的k宽直径,d_k(G),是指最小的整数l使得对任意两不同顶点x,y∈v(G),都存在k条长至多为l的内部不交的连接x和y的路.用C(n,t)表示在圈C_n上增加t条边所得的图.定义h(n,t)=min{d_2(C(n,t))}.本文给出了h(n,2)=[n/2].而且,给出了当t较大时h(n,t)的界.

匹配组合网络的宽直径

图的宽直径是度量并行与分布式网络通讯延迟的重要指标.研究匹配组合网络G(G)0,G1;M的宽直径,并根据该网络的结构性质,用点不交的最短路径方法得到G(G)0,G1;M的宽直径的上界估计式.

C(n,t)图的2-宽直径

图G是简单k-连通图,图G的k-宽直径记作dk(G),图C(n,t)表示在圈Cn上加t边后得到的图,h(n,t)=min{d2(C(n,t))},得到了h(n,3)的下界,以及当t≥n2-n4时,h(n,t)=2.

4度循环图的宽直径

研究了涉及图中两点间k条内部不交路的图的宽距离和宽直径。根据循环图的传递性和对称性,得到了n阶4度连通循环图的宽直径的上下限。所得结果可用来度量以循环图作为模型的一类具有高度对称性的网络的通信传输的延迟性能和容错性能。

关于3连通图的容错直径和宽直径的一个新结果

容错直径Dk可以度量容错网络中数据传输延迟,宽直径dk能度量网络的容错度和传输效率,因此容错直径和宽直径是设计和评估网络性能的重要参数.对于任意k连通图,它的容错直径Dk不超过宽直径dk,讨论dk和Dk之间的进一步关系是很有意义的.本文证明了当D2≥3时,d3≤2(D2-1)[(D2-1)(D3-1)-D2]+1,改进了已有的结果.

正则图的宽直径(英文)

宽度为m的图G的直径是最小整数d,使得G中任何两顶点之间至少存在m条其长度都不超过d的内点不交的路.对于任何满足[(2w+5)/3]≤m≤w的整数m,给出了n阶w正则w连通图的m宽直径的上界为[((n-2)(w-2))/((w-m+1)(3m-w-4))]+1.它能导出和改进某些已知结果.

4度循环图的不交路及k-宽直径（英文）

研究了4度循环图,构造出其任意两点之间的四条内部点不交路,并且给出其宽直径的一个较好的上界.

变种超方体网络的容错直径与宽直径

研究变种超方体的网络容错直径和宽直径,证明了n维变种超立方体的n-1容错直径和n宽直径为[2n/3]+1或[2n/3]+2.

关于4连通图的容错直径和宽直径的一个新结果

容错直径Dk可以度量容错网络中数据传输延迟,宽直径dk能度量网络的容错度和传输效率,因此容错直径和宽直径是设计和评估网络性能的重要参数.对于任意k连通图,它的容错直径Dk不超过宽直径Dk.证明了当D2≥3时,d4≤3(D2-1)(D3-1)[2(D3-1)(D4-1)-5]-3/2D22+3/2D2+1.

强乘积图的宽直径上界

由于图本身可以表示网络的拓扑结构,所以研究网络的各类指标时,常常使用图的参数和性质来度量网络性能的优异.通常是使用乘积图用小因子图构造复杂大图,其中使用强乘积来构造图是一种重要的构造图的方法,而宽直径则是度量网络性能的重要参数.宽直径较小的网络往往拥有较小的传输延迟.本文给出了任意两个因子图进行强乘积之后的乘积图,并根据子图的两种属性得出了宽直径上界,最后举例说明了使用强乘积图构造网络和使用笛卡尔乘积图构造网络的优点与不足.