互连网络的m层二进制图模型

超立方体、交叉立方体、Mbius立方体以及折叠立方体等都是著名的互连网络。它们有一个共同的弱点:其结点度随着网络规模(结点数)的增大而增大。这意味着依此互连网络设计出的超级计算机的扩展性很差。能否构建出既能保持它们已有特性又能使结点度固定的互连网络呢？现提出互连网络的m层二进制图模型,并依此模型设计了分别由超立方体、交叉立方体、Mbius立方体以及折叠立方体等生成的m层超立方体、m层交叉立方体、m层Mbius立方体以及m层折叠立方体。特别地,m层超立方体有一个特点:结点度可以不随网络规模的增大而增大,而且具有超立方体的特性。另外,还提出了由已知图生成m层图的概念。     

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

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

Star网络S6的Hamilton圈分解

Star网络Sn作为超立方体(一种著名互连网络)的替代品而被许多作者研究.与超立方体相比较,该网络有较小的直径和顶点度.在本文中,我们证明了关于Star网络Sn的一个猜想当n=6时是正确的,即S6是两个边不交的Hamilton圈及一个完美对集的并.     

关于互连网络群论模型的一簇猜想

连通图生成的Cayley图是作为互连网络的群论模型提出来的概念。猜想:设G=(V,E)是具有顶点集{1,2,…,n}(n>2)和m条边的连通图。如果m=2r,则由G生成的Cayley图是边不交的k(0≤k≤r)个Hamilton图和m－2k个完美对集的并;如果m=2r+1,则由G生成的Cayley图是边不交的k(0≤k≤r)个Hamilton图和m－2k个完美对集的并。特别地,对于k=r和星网络,这个猜想的特殊情形是1998年由师海忠提出来的。     

BSCC(4,k)的Hamilton圈分解

冒泡排序连通圈网络BSCC(n)是一类重要的互连网络。2010年师海忠提出了如下猜想:冒泡排序连通圈网络BSCC(n)(n≥4)可分解为边不交的Hamilton圈和完美对集的并。记BSCC(n)为BSCC(n,0),对BSCC(n,0)的每个顶点用一个三角形代替,得到新网络BSCC(n,1),对BSCC(n,1)的每个顶点用三角形代替得到BSCC(n,2),类似迭代k次得新网络BSCC(n,k)。师海忠进一步提出猜想2:BSCC(n,k)可分解为边不交的一个Hamilton圈和一个完美对集的并。证明了BSCC(4,k)可分解成边不交的一个Hamilton圈和一个完美对集的并。     

关于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网络的这几类控制数给出了更好的界.     

有向图语言

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

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

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