The embedding of rings and meshes into RP(k)networks

来源 :中国科学F辑 | 被引量 : 0次 | 上传用户:ibm__1235
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
This paper first investigates the topological properties of RP(k) networks.Then focusing on the embedding of rings and 2-D meshes into the RP(k) network, it is proved that the RP(k) network is a Hamiltonian graph and the ring with 10*k nodes can be embedded into the RP(k) network with load, expansion, dilation and congestion all equal to 1. If there exists a faulty node on each slice in the RP(k) network, throwing off the faulty nodes, the RP-1(k) network is obtained. It is also proved that there exists a Hamiltonain cycle in the RP-1(k) network. So the ring with 9*k nodes can be embedded into the RP1 (k) network. After that, we discuss the embedding of a 2-D mesh, M1(a, b), into the RP(k) network. By defining the sequence-column-order mapping, the snake-like-column-order mapping and the shortest path mapping, we obtain two ways of embedding a 2-D mesh into the RP(k) network. The performances of the embedding are as follows. In the snake-like-column-order mapping, the dilations are 1, 2, 3, 3 and 2 and the congestion are 1, 3, 4, 5 and 3 respectively when a is equal to 1, 2, 3, 4 and 5. In the sequencecolumn-order mapping, the dilation is equal to 3 and the congestion is equal to 6 when a is between 6 and 9. The dilation is equal to 「a/10」+2 and the congestion is equal to max{「a/10」+1, 6} when a >10. As a special case, the four parameters are also equal to 1 when a is equal to 10.
其他文献
For a general linear mixed model with two variance components, a set of simple conditions is obtained, under which, (i) the least squares estimate of the fixed
In this article we report a new and sensitive palaeoclimate proxy indicator-humification degrees of peat.Based on the comparison of humification degrees with ot
为探究吕家坨井田地质构造格局,根据钻孔勘探资料,采用分形理论和趋势面分析方法,研究了井田7
Organisms have variable genome sizes andcontain different numbers of genes. This difference demonstrates that new gene origination is a fundamental process in e
Alkali treatment can change the structures and properties of cellulosic fibers. The aim of this work was to study the mechanism of structure changes of Tencel f
This paper introduces a sliding-window mean removal high pass filter by which background clutter of infrared multispectral image is obtained. The method of sele
A huge coral reef occurring in the Triticites belt of the Maping Formation, in Bianping Village, about 4 km west of Houchang Town from Ziyun County, Southern Gu
Nanomanipulation of DNA molecules or other biomolecules to form artificial patterns or structures at nanometer scale has potential applications in the construct
Nanometer-scale thin film of Ni supported on glassy carbon (nm-Ni/GC) was prepared by electrochemical deposition through cyclic voltammetry (CV). The properties
基于螺旋度分波分析公式,我们探讨在J/ψ→fJφ(θ1,φ1)、fJ→ππ(θ2,φ2)、φ→K+K-(θ3,φ3)级联衰变过程中是否可以通过各种一维角分布投影鉴别出f0和f2共振态.结果表