迪卡尔乘积图到Cayley图中的嵌入  

Embedding Cartesian Product Graphs into Cayley Graphs

作　　者：赵猛[1] 方滨兴[1] 王义和[1] 胡铭曾[1] 

机构地区：[1]哈尔滨工业大学计算机科学与工程系,哈尔滨150001

出　　处：《计算机学报》2000年第6期646-648,共3页Chinese Journal of Computers

摘　　要：给出了一类图 (迪卡尔乘积图 )到另一类图 (Cayley图 )的嵌入的一般方法 .这些嵌入是这样实现的 :首先把迪卡尔乘积图的每个“因子”图嵌入到主图中 ,然后取这些“因子”嵌入的积 .进一步给出了一个定理 ,用来通过“因子”嵌入的性质来计算乘积嵌入的膨胀度 .Finding a good topology for multiprocessor interconnected network is a problem that is widely discussed recently, and many topologies have been recommended, such as hypercube, generalized hypercube and the recently proposed class of graphs——Cayley Graphs, among which is star graph, which is looked on as an attractive alternative to hypercube. One problem in dealing with the newly proposed topology is the lack of algorithms tailored for them, which impede the application of these network topologies. In order to solve this problem, embeddings of graphs are considered. With the embedding of one graph into another, the host can employ algorithms proposed for the guest. However, in the previous efforts, only the embeddings of some particular graphs were discussed. In this paper, the general method of embedding a kind of graphs, Cartesian product graphs, into another kind of graphs, Cayley graphs, is presented. These embeddings are carried out by first embed the factor graphs of the Cartesian product graphs into the hosts, then take the products, which is a concept introduced in this paper, of these factor embeddings. A theorem is given which presents a method to compute the dilation of the product embedding from the properties of the “factor embeddings”.

关 键 词：CAYLEY 迪卡尔乘积图 互联网 体系结构 

分 类 号：O157.5[理学—数学] TP393[理学—基础数学]