互连网络的向量图模型

n-超立方体、环网、k元n超立方体、Star网络、煎饼(pancake)网络、冒泡排序(bubble sort)网络、对换树的Cayley图、De Brujin图、Kautz图、Consecutive-d有向图、循环图以及有向环图等已被广泛地应用做处理机或通信互连网络.这些网络的性能通常通过它们的度、直径、连通度、Hamiltonian性、容错度以及路由选择算法等来度量.首先提出了有向向量图和向量图的概念;其次,开发了有向向量图模型和向量图模型来更好地设计、分析、改良互连网络.进一步证明了上述各类著名互连网络都可表示为有向向量图模型或向量图模型.更重要的是该模型能够设计出新的互连网络-双星网络和三角形网络.

关于修正冒泡排序网络的一簇猜想

修正冒泡排序网络是互连网络设计中的一个重要的Cayley图模型,关于修正冒泡排序网络的一簇猜想如下:对于任意的自然数n≥3,修正冒泡排序网络Yn是i个边不交的哈密尔顿圈以及n-2i个完美对集的并,其中1≤i≤︱n/2︱。证明了当i=1,2时,这个猜想是正确的。

关于互连网络的几个猜想

n-立方体是著名的互连网络,星图、煎饼图和冒泡排序图是由凯莱图模型设计出来的重要的互连网络。对换树(transposition tree)的凯莱图是一类特殊的凯莱图,星图和冒泡排序图分别是对换树为星和路的凯莱图。给出了关于n-立方体、星图、煎饼图、冒泡排序图和对换树的凯莱图的各一个猜想;提出了对换图的凯莱图的概念,进而由这一概念设计出了两个互连网络——圈图和轮图,并证明冒泡排序图和星图分别可嵌入圈图和轮图。

2r-正则图连通圈网络的Hamilton分解

互连网络是超级计算机的重要组成部分。互连网络通常模型化为一个图,图的顶点代表处理机,图的边代表通信链路。2010年师海忠提出互连网络的正则图连通圈网络模型,设计出了多种互连网络,也提出了一系列猜想。文中证明了2r-正则图连通圈网络可分解为边不交的一个Hamilton圈和一个完美对集的并,从而证明了当原图为2r-正则连通图时,这一系列猜想成立。

完全对换网络的一簇猜想

完全对换网络是互连网络设计中的一个重要的Cayley图模型,关于完全对换网络的一簇猜想如下:对任意整数n≥3,当n=0(mod 4)或1(mod 4)时,完全对换网络CTn是k(1≤k≤n(n-1)4)个边不交的哈密尔顿圈和(n(n-1)2-2k)个完美对集的并;当n=2(mod 4)或3(mod 4)时,完全对换网络CTn是k(1≤k≤n(n-1)-24)个边不交的哈密尔顿圈和(n(n-1)2-2k)个完美对集的并。证明了当n=3,4和n=5(1≤k≤4),n=6(1≤k≤6)时,这簇猜想是正确的。

修正冒泡排序网络的容错直径的一个上界

找出了修正冒泡排序网络中任意两个顶点之间的n条内点不交的路,给出了这些内点不交的路的长度的上界,进而证明了n(n1)2+1是修正冒泡排序网络容错直径的一个上界.

几类新的笛卡尔乘积互连网络

Star网络、Pancake网络、Bubble sort网络、修正Bubble sort网络(又称圈图)、轮图等都既是Cayley图又是重要的互连网络。利用图的笛卡尔乘积方法构建了几类新的笛卡尔乘积互连网络:环网、循环移数网络、ILLIAC网络、超立方体分别与Star网络、Pancake网络、Bubble sort网络、修正Bubble sort网络、轮图的笛卡尔乘积网络;这些网络的某些性能指标(例如,直径等)比Star网络或超立方体更好。

互连网络的新模型:多部群论模型

互连网络是超级计算机的重要组成部分。互连网络在很大程度上决定着超级计算机的性能。在1989年,S.B.Akers等提出了互连网络的群论模型,据此模型设计出了星网络、冒泡排序网络等一大批网络。尤其是星网络具有很多很好的性能,被认为是超立方体的替代品。但它们都有一个弱点:网络规模(结点数)为n!。即随着n的增大,n!增速太快,使得据此网络结构设计出的超级计算机升级较为困难,即扩展性较差。在群论模型的基础上提出了互连网络的多部群论模型,进而,据此模型设计出(n,k)-多部星网络、(n,k)-多部冒泡排序网络等多种网络。并证明星网络是(n,1)-多部星网络,而且(n,k)-多部星网络做到了规模(结点数)增大且增幅固定、直径增大缓慢、结点度不变,即有很好的可扩展性,其它(n,k)-多部网络也有类似的性能。

完全二叉树到冒泡排序网络的嵌入

冒泡排序网络是由凯莱图模型设计出来的重要的互连网络.这个网络由于它的简单,点对称性和可缩结构而受到极大关注.二叉树是并行通信模式中应用十分普遍的结构.设G和H是两个给定的网络,它们可分别由两简单无向图表示,从G到H的嵌入是存在G到H的同态映射使得对G中的任何一条边,它的象是H中一条路.把二叉树嵌入到另一网络中,这样可以应用已知的二叉树的性质去研究另一网络,反过来可以用另一网络模拟二叉树.在本文中我们主要考虑完全二叉树,同根完全二叉树和双根完全二叉树能以膨胀数1嵌入到冒泡排序网络中,同时给出了这三种完全二叉树嵌入冒泡排序网络的具体构造方法.

(V,R)-语言

V是一个字母表。FV是V上的一个自由半群,R是FV的一个子集。首先,提出了(V,R)-半群的概念,证明了图半群和有向图半群都是(V,R)-半群。其次,提出了超图半群的概念,证明了超图半群是(V,R)-半群,超图半群把超图理论和自由半群理论联系起来。以此为基础,提出了(V,R)-语言和超图语言两个概念。超图语言把超图理论和形式语言理论联系起来。进而,证明了超图语言、无向图语言和有向图语言都是特殊的(V,R)-语言。第三,证明了无向图语言和有向图语言都是正则语言。这就回答了文献"无向图语言"和"有向图语言"中提出的开问题。(V,R)-半群和(V,R)-语言是研究自由半群和形式语言的新理论和新方法。

图半群的度向量

定义了图半群的度向量,讨论了它与图半群的关系。

无向图语言

无向图是图论中的基本概念,图半群是1991年提出的一个概念,形式语言与自动机理论是计算机科学与技术科学的重要基础理论。借助无向图和图半群,提出了无向图语言的概念,并研究了无向图语言的一个子类———平面图语言,给出了如下结论:一个无向图语言是平面图语言当且仅当它不包含K5语言或K3,3语言的剖分图语言。另外提出了几个开问题,其中之一是无向图语言与正则语言、上下文无关语言、上下文有关语言以及短语结构语言有何关系?

冒泡排序网络的控制数

给出了冒泡排序网络中任一点到恒定点的距离与置换逆序数的关系,利用置换逆序数得到了冒泡排序网络顶点分布、几类点控制数的值以及一些控制数的界.

有向图语言

经典形式语言有两条主线,就是自动机线索与形式文法线索。利用有向图理论和有向图半群理论建立了另一条线索——有向图语言,讨论了两类特殊的有向图语言——de Bruijn有向图语言和Kautz有向图语言,引入了连通语言及语言的直径等概念,计算出了deBruijn有向图语言和Kautz有向图语言的直径。

完全图半群与连通图半群

引进了拟完全国半群、完全图半群、连通图半群以及连通元的概念，证明了有限字母在上的自由半群和相应的完全图半群同构；是可换图。另外，给出了ｎ阶连通简单图半群有Ｓ阶完全子图半群的一个充分条件。

二部图半群和完全二部图半群

讨论了二部图半群和完全二部图半群的一些性质,探讨了二部图半群与二部图、完全二部图半群与完全二部图的关系,给出了二部图半群的圈特征。

一类新的互连网络:三角塔网络

本文提出并分析了一种新的互连网络—三角塔网络.当n>4或n=4时,它是极大连通的,紧超连通的,即三角塔网络的连通度κ(TTn)是2n-3.星网络是三角塔网络的子网络,故而三角塔网络除了继承星网络的很多优良性质(例如:点对称性、连通性、点可迁性等),还说明Sn能以膨胀数1嵌入TTn.当三角塔网络和超立方体与冒泡排序网络有近乎相同的顶点数时,三角塔网络的直径和连通度与超立方体与冒泡排序网络的直径和连通度相比直径更小、连通度更大.本文给出了三角塔网络的直径和平均距离,并提出了关于三角塔网络Hamilton性的一簇猜想,并且证明这个猜想对于n=3,4以及n=5,6,k=1,2时是正确的.

关于Bubblesort-star网络的距离控制数

对于任意的正整数l,连通图G的顶点子集D被称为距离l-控制集,是指对于任意顶点vD,D中至少含有一个顶点u,使得u和v在G中的距离不超过l。图G的距离l-控制数是指G中所有距离l-控制集的最小基数,1-控制数常常称为控制数。给出了Bubblesort-star网络的控制数、距离2-控制数和距离3-控制数的界,而且针对某些低维Bubblesort-star网络的这几类控制数给出了更好的界。

x3（G）—X3（G^—）的可达下界

引入了最佳配点、最佳配邻点集的概念，讨论了３－色数的界，给出了ｘ＿３（Ｇ）＋ｘ＿３的可达下界．

冒泡排序图的条件容错哈密尔顿性

冒泡排序图是由凯莱图模型设计出来的重要的互连网络.容错性的研究对考察网络的可靠性是十分重要的.n维冒泡排序图Bn是正则对称图,若它有n!个顶点和(n-1)n!/2条边.设F是冒泡排序图Bn的失灵边集,且|F|≤2n-7,若冒泡排序图Bn的每个顶点都至少关联2条非失灵边,那么Bn-F中存在哈密尔顿圈.