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

容错直径和宽直径是度量网络可靠性和有效性的重要参数。对任何k连通图，它的容错直径Dk不超过宽直径dk。论文证明d2≤max{(d1-1)(D2-1/2d1-1) 1,D2 1}；给出d1=2时d2=D2 1的一个充分必要条件：d2=3或d2=4且达到d2值的任何两顶点必相邻。     

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

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

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

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

关于笛卡尔乘积图边容错直径的研究

笛卡尔乘积是从若干特定的小网络构造大网络的有效方法,边容错直径是衡量一个网络可靠性和效用性的重要标准,研究了笛卡尔乘积网络的边容错直径,并且得到了一个相关的结果.对任何t1,t2≥1,若G1,G2分别是t1边连通的和t2边连通的,则它们的笛卡尔乘积图的边容错直径D’t1+t2(G1×G2)≤D’t1(G1)+D’t2(G2)+1.并且,该不等式中的上界是最好的.     

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

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

无向Kautz图的限制性连通度和限制性容错直径

证明直径为ｌ且最小和最大度分别为３和４的无向Ｋａｕｔｚ图具有限制性连通度４，且其限制性容错直径至多ｌ＋１４。     

有向双环网络的容错路由及容错直径

提出有向双环网络G(N;r,s)的容错路由及容错直径的概念,根据L-型瓦的叠加原理,研究了容错节点所对应的最优等价节点的分布规律.利用L-型瓦的4个参数a,b,p和q,给出有向双环网络G(N;r,s)的容错路由算法及其容错直径的计算公式.根据该算法进行容错路由,当有向双环网络G(N;r,s)中出现故障时,网络的可靠性和信息传输延迟将达到最佳状态.     

双向双环局域网络的限制性容错直径

给出了双向双环局域网络的一个最优路由算法。证明了当n≥4时，双向双环局域网的限制连通度为4，其限制性容错直径为n。     

关于Cayley图的直径

证明了有关Ｃａｙｌｅｙ图的直径的几个定理，并得到它们对有限群的问题的应用．     

关于旋转交换网络的直径

本文讨论了旋转交换网络REn 的一些代数性质并给出了此网络的一个路由算法. 并且证明了(n2-2n 1)/4相似文献   

互联网络数据传输延迟与图的容错直径之研究

对互联网络拓扑结构与容错直径进行研究,得出了互联网络数据传输延迟与图的容错直径的内在关系,并给出重要性质,为优化互连网络拓扑结构提供设计依据.     

关于（k—1）容错直径或k直径的最大图

本文确定了阶为ｎ，（ｋ－１）容错直径为ｄ或ｋ直径为ｄ的ｋ连通图Ｇ的边数的最大值，并给出了相应的最大图．     

冒泡排序图的超带性

图G的k-路集C(u,v)是连接G中顶点u和v的k条内点不交的路的集合.图G的k-路集C(u,v)是一个k*-路集如果连接顶点u和v的k条内点不交的路包含G中所有的顶点.一个二部图G是k*-带的若G中任意两个属于不同二划分集的顶点之间存在k*-路集.设κ(G)是图G的连通度.一个二部图是超带的若G是i*-带的,1≤i≤κ(G).n维冒泡排序图Bn是二部图,是n-1正则的,有n!个顶点.在本文中,首先证明了Bn是(n-1)*-带的,n≥5,然后得到n维冒泡排序图Bn(n≠3)是超带的.     

关于Cayley图的Hamilton性的一个猜想

介绍了Ｃａｙｌｅｙ 图的Ｈａｍｉｌｔｏｎ 性的一个有趣而尚未解决的问题;并给出了文献［１］中一个定理的简单证明。     

pqr阶Cayley图的边-Hamilton性的一个注记

设G为限群,|G|=pqr,p,q,r为相异素数,M是G的一个生成集,作者证明了若M中含有p阶正规元,则Calyley图X（G,M）是边-Hamilton图     

一个有效的容错路由算法

互连网络中路由容错是网络设计的重要问题之一。作者利用ｎ维超方体模型,研究了互连网络中容错路由问题,包括容许的故障点和故障块的数目和结构,给出了一个有效的点到点路由算法,并分析了该算法的正确性和有效性。     

修正泡型图的条件匹配排除

一个图G的条件匹配排除数是最少的边的数量,使得删去这些边后形成的图既没有孤立点也没有完美匹配和几乎完美匹配.任何一个这样的边集称为G的一个最优条件匹配排除集.条件匹配排除数是衡量网络在边故障情况下的鲁棒性的参数之一.主要给出了修正泡型图的条件匹配排除数是2n-2(n≥5).     

SEFP:一种新的固定度为4的Cayley互连网络

提出一种新的固定度为4的正则互连网络SEFPn，它是一种置换群Sn上的Cayley图。SEFPn是基于洗牌（shuffle），交换（exchange）及翻转（flip）运算的互连网络。它直径短，其直径大约是SEPn（洗牌交换置换网络）的一半。我们提出了基于此网络的路由算法，并由此得到了此网络的直径估计。这种网络被证明能有效模拟其它基于置换群Sn上的Cayley图。在要求具有限定数量的I／O端口的VLSI实现方面，此网络很具有吸引力。另外我们还讨论了此网络的一些代数性质。     

匹配组合网络的宽直径

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

3-正则Cayley图的l-边-连通度

介绍了l-边-连通度的定义及定义在抽象群上的Cayley图;利用构造最小l-序列边割的方法,结合Cayley图的性质,研究了3-正则Cayley图的l-边-连通度;给出并证明了l为2、3、4时的l-边-连通度λl(G);同时,给出了对n-正则Cayley图的l-边-连通度的推论.