【作者】 钟玮；

【导师】 陈宝兴；

【作者基本信息】 漳州师范学院 ， 计算机应用技术， 2010， 硕士

【摘要】 Cayley图是由有限群导出的一类重要的高对称正则图,被认为是非常合适的互连网络拓扑结构.很多优秀的互连网络如双环网,超立方体,星图都是Cayley图.大家知道对Cayley图的研究起步早并且取得非常丰富的结果,而对Bi-Cayley图的研究目前相对来说还比较少.设G是一个有限群,S是群的一组生成元(可以含G的单位元),并且能完全生成G,Bi-Cayley图是一个二部图,它的顶点集和边集分别定义为,V=G×{0,1},E=.{([g,0],[sg,1])|g∈G,s∈S}.Bi-Cayley图是Cayley图的自然推广,特别地,循环群上4度Bi-Cayley网络BC(n；±s1,±s2)是无向双环网络DLG(n；±s1,±s2)的一个自然推广.本文的研究主要有以下三个方面1.循环群上4度Bi-Cayley网络BC(n；±s1,±s2)连通的充分必要条件.2.通过求得最小非负解和最小交叉解来计算循环群上4度Bi-Cayley网络BC(n；±s1,±s2)的直径.3.循环群上4度Bi-Cayley网络BC(n；±s1,±s2)的最优路由算法.更多还原

【Abstract】 Cay ley graphs, which represent a category of symmetric and regular graphs derivable from finite groups, have been shown to be very suitable to serve as in-terconnection network topologies.Many outstanding networks,such as double-loop network,hybercube,star graph are Cayley graphs.We all know that the Cayley graph has been studied for a long history,and we have abundance results about it.But we have few results about Bi-Cayley still now.For a finite group G and a set of gener-ating elements S(possibly,it contains the identity element)of G,which can generate G completely, the Bi-Cayley graph BC(G,S) of G with respect to S is defined as the bipartite graph with vertex set V=G×{0,1} and edge set E={([g,0], [sg, 1])|g∈G, s∈S}.Bi-Cayley graphs are generalization of Cayley graphs.Specifically,4-degree Bi-Cayley graphs of Cyclic Groups are generalization of undirected double-loop net-works.In this paper we maily study the following three questions.1. The necessary and sufficient condition of the connectivity of Bi-Cayley graphs are investigated.2. To get the smallest non-negative solution and the smallest cross solution,and use them to calculate the diameter of 4-degree Bi-Cayley graphs of Cyclic Groups BC(n;±s1,±s2).3.To design the arithmetic to get the shortest path of two point of connected 4-degree Bi-Cayley graphs of Cyclic Groups BC(n;±s1,±s2).更多还原