连通立方网络图的构建和性质分析

ðÞð Þð Þð ð ÞÞð Þ ð ÞðÞðÞðÞð Þð Þð Þ¼ðÞð Þ ð Þ工程科学与技术，国际期刊20（2017）934完整文章连通三次网络图Burhan Selçuka，Mr. J.，Ali Karciba土耳其Karabük，Karabük大学计算机工程系b土耳其马拉蒂亚伊诺努大学计算机工程系阿提奇莱因福奥文章历史记录：2017年3月9日收到2017年4月19日修订2017年4月19日接受2017年5月25日在线发布保留字：Hamilton路径超立方体格雷码互连网络连通立方网络图A B S T R A C T超立方体是一种流行的互连网络。由于超立方体的流行，越来越多的研究者致力于发展超立方体的各种变体本文提出了超立方体的一种变形--连通立方网络图，并研究了首先，我们定义了CCGG，并对CCGG进行了特性分析然后，我们证明了CCNG具有Hamilton图的性质最后，给出了比较结果，并给出了一个CCGG的路由算法和双调排序算法。在稀疏性和代价方面，CCGG优于Hypercube。©2017 Karabuk University. Elsevier B.V.的出版服务。这是CCBY-NC-ND许可证（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍在实践中使用的最常见的网络拓扑结构是树，循环，网格，环面，网格和超立方体。在本文中，为了提出一个新的视角的网络拓扑结构，我们使用超立方体拓扑结构的超立方体变体称为连接立方网络图（CCNG）的建设。定义并构造了x维n个节点、y维m个节点、z维k个节点的CCNG网络k;m;nCCNG k;m;n是一个递归图，可以用两种方法构造.第一种方法，有限个H n 在3D空间中相互连接，H n表征了这个空间中的立方体，第二种方式是将第一种方式中得到的有限个网格结构连接起来。在这里，首先，我们将连接有限数量的立方体H3使得每个立方体与随后的立方体具有共同的表面。进一步，我们将连接有限个超立方体H4.（H4是4D空间中的超立方体）以每个超立方体具有公共立方体的方式。此外，我们将连接有限数量的这种网格结构，通过连接立方体来创建一个共同的表面。因此，通过连接3维或4维的超立方体得到Hamilton图。本文在得到CCNG的k;m;n阶后， 图，我们有研究了CCNG的类哈密顿性质。*通讯作者。电子邮件地址：bselcuk@karabuk.edu.tr（B.Selçuk），ali.karci@ inonu.edu.tr（A.Karci）。由Karabuk大学负责进行同行审查本文的其余部分组织如下。第三节给出了三维空间中CCNG k;m;n第4节显示的建设和特性分析的CCNG k;m;n. 第五节给出了用于标记网格结构节点的递归算法。在第6节中，我们给出了比较结果。在第七节中，我们给出了一个CCGG的路由算法。在第8节中，双调排序算法被映射到CCNG k;m;n。最后，我们给出了一个结论。2. 背景和相关工作互连网络通常由图G V;E表示，这是一对集合，其中V表示节点集合，E表示边集合。超立方体图Hn在互连网络中有着广泛的应用。超立方体图Hn是一个递归可定义图。Hn具有正则图、简单的节点标记、良好的连通性、对称性和代价等性质，n维Hn连接2n个节点，每个节点可以唯一地用n位地址标记，使用两个节点之间的直接连接，当且仅当它们的n位地址恰好相差一位位置.H n的流行的原因可以归因于它的拓扑特性，能够使用简单的路由算法和能够允许嵌入commonly-rewired互连模式。近年来，n维超立方体的许多性质得到了广泛的研究（参见[1]）。[2019- 12 - 16] [2019 - 09 - 16][2019- 09 - 16][2019 - 09 - 16]此外，超立方体的变种已经得到，以确保超立方体的性能提高一些http://dx.doi.org/10.1016/j.jestch.2017.04.0052215-0986/©2017 Karabuk University.出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表工程科学与技术国际期刊杂志主页：www.elsevier.com/locate/jestchB. Selçuk，A.Karci/Engineering Science and Technology，an International Journal 20（2017）934935ðÞðÞð Þ ð Þð ð ÞÞ ðÞJ - j8 jj jjÞ 2P8ðþÞ ðþ Þ ðþ Þ1/4Pð Þ ðÞðÞ1/4ðþÞ¼ ¼¼结构，CCNG k m1N11/4P最流行的超立方体变体是折叠超立方体[3，5]、交叉立方体（扭曲立方 体 ） [8 ， 11 ， 19] 和 分 层 立 方 体 网 络 （ 参 见 图 1 ） 。 [1][2][3][4][5][6][7] 这些方法的目的最近，Karci和Selcuk[16]使用分形结构定义了一个新的超立方体变体，称为他们研究了一种新的超立方体变体的汉密尔顿性质此外，一些作者提出了新的互连网络。有兴趣的读者可以参考参考文献[2，20，21]了解详细信息。在本文中，||“表示两个字符串. Hammingg距离用Pn-1αibiη计算，现在，我们可以利用[13]中的定义1给出详细的定义。为了构造CCNG k;m;n网络，有三种情况需要提供定义1（a）：案例1：x<$2y和y<$4z案例2：y<$2x和x<$4z案例3：z<$2x和x <$4y在情况1中，x维度上的节点数量将加倍，而y和z维度上的节点数量将保持不变。同样的过程可以应用于其他尺寸（y和z）。CCNGk;m;n的构造可以是其中求和等于ai的求和1/4bi（按位异或定义2：操作）。H3在3D空间中被称为立方体，H4在4D空间中被称为超立方体。让我们记住图中所示的三维坐标平面。1 .一、3. 连通三次网络图（CCNG（k，m，n））的构造在这一节中，我们给出了CCNG k;m;n的定义。为了方便读者定义1. CCNG k;m;n：CCNG k;m;n可以分三步定义。定义2.设CCNG图k;m;n是连通三次网络图. 可以将两个CCNGk;m;n组合以构建大小为CCNGk;m;nl;G v;E;kP1;mP 1;nP 1的大小的两倍的新网络。将有三种情况：(a) 如果加倍维数为x，则0jjCCNGk;m;n和1jjCCNGk;m;n中的节点和边也包括在CCNGk1;m;nGVx;Ex。If8v i2V;p¼3;.. . ;kmn-1，2p-86Labe lv i62p-5，jk-mj61;jk-nj61和mn61，则0v i;1v iEx。(b) 如果双倍维数是y，则(a) CCNGk;m1;n是一个立方网络图，0 jjCCNGk;m;n 和1 jjCCNGk;m;n 也纳入CCNGk;m1;nGV y;Ey。If8v i2V;Labelv iiseven，通过以连续的方式连接m2个i1/4立方体在xz平面中具有公共表面。例如，图3中给出的网格结构是CCNG_1; 2; 1_。(b) CCNGk;m1;n1是一个立方网络图，设lvi<2kmn-1，jk-mj61;jk-nj61和jm-nj61;则n0jjv i;1jjvi2Ey.(c) 如果双倍维数是z，则0 jjCCNGk;m;n和1 jjCCNGk;m;n是还包括通过连接P n 的数量得到 2i网格ð þ þ Þ在CCN Gk;m;n11GV z;Ez中。If8v i2V;Labe lv i2K M n2K M n2结构，CCNG k;m1;n1，具有较低的和上表面沿着z轴是共同的。为了考试-图4中的网格结构为CCNG-1; 2; 2 π。（c）CCNG<$k <$1;m<$1;n<$1 <$$>是一个三次网络图，它是通过连接k2i的数量得到的网格<$k;<$k;<$n，它们具有较低的和f4 iji ¼ 0; 1; 2;.. . ; 2-g[f4 i 1 ji 0; 1; 2;.. . ; 2-氨基-甘氨酸，jk-mj61;jk-nj61和jm-nj61;则8<$0jjv i;1jjv i<$2Ez.图2示出了加倍过程策略和标记技术。定义2使用H3 作为一个基本的建筑结构-上表面与x轴相同。为了考试-图5中的网格结构为CCNG_（2; 2; 2）。这些定义的类似物可以用不同的方式处理比如说，CCNGk;m1;n<$CCNGk 1;m;n<$CCNGk;m;n1或CCNGk1;m 1;nCCNGk 1;m;n11/4CCNG/g;m/g1;n/g：此外，这些定义的类似物被H3取代，H400。Fig. 1. 三维坐标空间。用于构造剩余CCNG块k; m; n。这个定义可以修改为使用H4R作为基本构建块。4. CCNG（k，m，n）的分析性质在这一节中，我们展示了CCNG的特征分析。在第4.1节中，我们主要研究了CCNG_k; m_k ~ 1; n_k的Hamilton性质。这些过程的相似性被CCNG k;m所取代1;n 和{CCNG k1;m;n 或CCNG k;m;n1 }。在第4.2节中，我们主要研究了CCNG_k;m_k ~1;n_k ~1的Hamilton性质。这些过程的相似性用CCNGk; m 1; n 1和{CCNGk 1; m 1; n或CCNGk 1; m; n 1}代替。4.1. CCNG（k，m+1，n）的Hamilton性质在这一小节中，我们得到了CCNG的解析性质：k;m<$1;n<$。首先给出了CCNG k;m的网格结构图1;n 其中k1;m1和n图3中的定义2。此外，很容易证明CCNG1; 1; 1等同于H3。CCNG1; 1 ;1; 1是利用3比特格雷码得到的一个Hamilton图。定理1. 让这样，我们就得到了遍历所有节点所产生的Hamilton图936B. Selçuk，A.Karci/Engineering Science and Technology，an International Journal 20（2017）934图二. 分别将x、y和zB. Selçuk，A.Karci/Engineering Science and Technology，an International Journal 20（2017）9349371/4P-1; P-2; P-3 ;P-1; P-2; P-3 ;XPPðÞðÞðþÞðþÞ¼×ð Þ ð Þ ð Þ采用k <$m <$n <$1比特格雷码对网格结构CCNG<$k; m <$1; n<$1进行编码。CCNG中的边的 总数k; m <$1; n<$是3×2kmn<$1-2km<$1-2mn<$1-2kn，总节点数为2kmn<$1。证据首先，我们发现总节点数使用数学归纳法计算H图3.第三章。通过使用4位格雷码来标记该CCNG_1;2;1的节点第一步：对于CCNG1;2;11，P12i1/43四个节点（一个面）是共同的，是相连的。 设初始立方体有8个节点，其他2-立方体有4个节点。因此，该图中的节点总数为8×2×4×16×2×4×2×1×3：假设步骤：对于CCNG k m1n，M 2个i1/4有四个节点（一个面）是共同的，是连通的。假设，得到具有2 kmn 1个节点的 图 。最后一步：对于CCNG k m2n，m×12i1/4四个节点（一个面）是共同的，是相连的。因此，得到具有2kmn 2个根据定义2，我们得到kmn-1kmn-2Xi¼0i¼02升2i2kmn-1：图四、通过使用5位格雷码来标记该CCNG_1;2;2 π的节点图五、通过使用6位格雷码来标记该CCNG_2;2;2n的节点m2i-1/4mon是连通的，有2kmn 1个节点，假设CCNGk;m1;n，因此该图中的总节点数为2kmn12kmn-1×4< $2× 2kmn1<$2kmn 2：因此，m= 12i1/4公共的，是连通的，一个图有2kmn2个节点。当CCNGk;m2;n具有2kmn2个节点时，CCNGk;m1;n具有2kmn1个节点，因为对于CCNGk;m1;n是维度y中节点数的一半对于CCNGk; m 2; n。其次，我们证明了CCNG k;m1;使用数学归纳法，n第一步：图3中CCNG1; 2; 1（定义1和2）的Hamilton路径的证据是显而易见的，并且已知CCNG1; 2; 1与H4相同。H4是一个Hamilton图.然后，CCNG1; 2; 1是一个Hamilton图，它是用4位格雷码。假设步骤：假设CCNGk;m1;n具有Hamilton路径，则CCNGk;m1;n是通过使用kmn1比特格雷码获得的Hamilton图，因为CCNGk;m1;n有2kmn 1个节点。最终步骤：对于CCNG k;m2;n有2 k<$m<$n<$22 k<$m<$n<$1个节点。我们获得CCNGk;m2;n 1;n1;n1因 为 CCNG<$k; m <$1; n<$1 有 2k<$m<$n<$1 个 节 点 ， 且 它 是Hamilton图。CCNGk;m2;n可以由两个CCNG k;m1;n构造。假设vi而vj是两个节点，CCNGk;m1;n，且vi和vj之间的汉明距离相等到1.一、的边缘200jjLabelvi;1jjLabelvi和0jjLabe lvj;1jjLabe lvj在CCN Gk;m2;n中，并且它们在CCNG 中 的 Hamilton 回 路 [k; m ∈ 2; n∈ 1]. 也 就 是 说 ，CCNGk;m2;n是通过使用kmn2比特格雷码获得的Hamilton图，因为CCNGk;m2;n具有2kmn2个节点。由于这些原因，CCNGk;m1;n是Hamilton图其通过使用kmn1比特格雷码获得，因为CCNGk;m1;n有2kmn 1个节点。938B. Selçuk，A.Karci/Engineering Science and Technology，an International Journal 20（2017）934ðþÞ×---ðþ þ Þð 作为基本构件）是常见的nodes（i1/40acube- H 4.¼¼ ¼ð þÞð þÞð þÞ ¼ ¼¼P3.Σ441/41/4ðþ þ Þð44最后，很容易证明，CCNG k;m1; n为32 kmn 12 km12 mn12 kn这是 构造Hamilton图所必需的。有x维中的n =2k-1n=2mnn =1边，2knn =2mn =1- 1 n = 2 m n =1边，222×2kmn- 1211^2kmn 2：其次，我们可以很容易地表明，CCNG k;m1;n1有一个汉密尔顿路径，使用类似于Theo的数学归纳法2，证明了。H-1<$2k<$m<$1条边，z维。该定理rem 1.然后，CCNG<$k; m <$1; n <$1 <$是利用k<$m<$n<$2比特格雷码得到的Hamilton图以来CCNG k;m 1;n 1有2 k<$m<$n<$2个节点。与定理1的证明类似，很容易证明：推论1. 让我们 连接 Pm 2 i-超立方体 这 有八这样，我们就得到了用k<$m<$n<$1比特格雷码遍历网格结构的所有节点所产生的Hamilton图。总边数为13×2kmn-1-2kmn-1-2knkmn总数的边缘在CCNG<$k;m<$1;n<$1 <$1 是 3 × 2k<$m<$n<$2- 2 m<$n <$2- 2 k <$n <$1- 2 k <$m<$1，它要求构造一个Hamilton 图 . 在 维 度 x 中 有 <$2k-1<$2m<$n<$2 边 ， 在 维 度 y 中 有2k<$n<$1<$2m<$1-1<$n边，并且z维中的n=1-1<$2k<$m<$1条边。节点总数为2关于Hamiltongraph建筑所需的由这种网格结构得到了Hamilton图。以类似的方式，该证明被替换为水平和垂直平面。最后，总成本（总节点数+总边数）证据CCNG2; 1;1;CCNG1; 2; 1或CCNG1; 1; 2具有与H 4相同的节点数。然而，如果CCNG102; 1;104;CCNG101; 2; 104或CCNG101; 1; 2 04的构造基于H103作为基本构造块，则CCNG102; 1; 104; CCNG101; 2; 104或CCNG101; 1; 2 04具有4边缘少比H400。如果建设的CCNG2; 1; 1; CCNG1; 2; 1或CCNG1; 1; 2基于H4，则CCNG2; 1; 1;CCNG1;2; 1 或 CCNG1; 1; 2 与 H4 相 同 。 用 H_ （ 14 ） 构 造 CCNG_ （ k;m_（11;n））_（11）表示，网状结构，4× 2kmn 2- 2mn2- 2kn 1- 2km 1：因此，我们证明了定理2。 H4.3. CCNG（k + 1，m + 1，n +1）例1.CCNG2 2 2：让对于CCNG的每个反射过程，使用ð ð;;H3作为基本构建块。证明了CCNG的边的总数为：3× 2kmn 1- 2kmn 1- 2mnn 1- 2kmn 2kmnn-1<$13× 2kmn-1- 2kmn-1- 2mnn-1- 2kn：Q4.2. CCNG（k，m + 1，n +1）网格结构如图所示。 3、有面、分底，要有共性。(In定理3，对于km n ①的人。总数该网状结构的节点是64个。（ 图中） 5）。即31313164262222：该网格结构是Hamilton图，并且使用6位格雷码获得。构造Hamilton图所需的边的总数是144。在这一小节中，我们首先给出了网格结构的图形，CCNGk; m 1; n 1; km n 1。定理3. 让我们连接Pk 2iCCNG k m1;;þ在定理2中，有一个曲面，定理2.让四个节点）是共同的。，CCNG k m1n，发生在底部，是共同的。这种网状结构，CCNG是一个Hamilton图，由下式得到：这种结构;;使用kmn3位格雷码。 总边数为由相连的正方形导出的两个水平表面。我们来连线3×2kmn 3-2kmn 2-2knn 2-2mnn 2及总成本ni¼02、这个 结构， 底层， 到 被 一 水平 表面是4×2kmn 3— 2km2— 2kn2— 2个月的需对于con-共同因此，这种网格结构CCNG<$k;m<$1;n<$1<$k是哈密尔顿图，并且是通过使用k<$m<$n< $2比特格雷码获得的。边的总数是3×2kmn 2-2mn 2-2kn 1-2kmn1，构造Hamilton图所需的节点数为2 kmn 2。证据 假设m;n>1。首先，Pmn2i<$2mn-1，Hamilton图结构证据... 证明类似于定理2的证明。 H5. 递归算法文[17]给出了构造n位格雷码的方法现在我想，是y维的m条边，n维的m条边此图的节点数为1/4尺寸中的边z. 总数让我们将这种反射和前缀方法应用于一个超M-411 1/41M1][1/20M-31]立方体在我们的问题与一些修改。表1与超立方体的比较结果。网络#节点#边#边#节点直径成本超立方体H<$3n<$23n3n×23n3n3n9n2CCNG_k;m;n_k（H（3）为基本构件）CCNG_k;m;n_k（H（4）为基本构件）2kmn 1如果k<$m<$n，23n12k<$m<$n1如果kn，3×2kmn 1-2kmn 1-2mn 1-2kn如果kn，3× 23n× 1- 5× 22n13×2kmn-1-2kmn1-2kn如果kn，32k2m12n如果kn，3-5× 2-n-113-2-k-2-m-1-2-n如果kn，格姆恩如果kn，3n格姆恩如果kn，3-2-k- 2-m-1- 2-n如果kn，3n×3-5×2-n-113-2-k- 2-m-1- 2-n×kmn如果kn，23n113×23n1-5×22n13-5×2-n-13n3n×13-5×2-n-1个nB. Selçuk，A.Karci/Engineering Science and Technology，an International Journal 20（2017）934939355ðÞðÞ4ð Þ ð Þ ð ÞðÞðÞ¼1吉吉2013年12¼23353333我的我的4.M ←½0M][½1M-];吉吉K22þ ¼备注1. 设M11/4/20001111 0]和M-1/4/21011010]。推论3. 由于上述算法修改了M1和M1相反2 241 12014年1月4日我们得到M3¼f000001011010110111101100g ¼½0M2][M1和M1分别，递归 算法 是 用于-1-13ij 3½1M2]，和m3粤ICP备16011110号-1½1M1][½0M-1]：从定义2，我们很容易得到CCNG1;1; 11M1。对推论2中的网格结构的节点进行标记。推论4.如果我们添加一个for循环（fork← 0 tor do）并修改同样地， 我们得到 M1/4/20M1][1/21M-1]，和 M1½0M1][M1而不是M1在上面的算法中，我们有4 335 4ijk32013年1月3日1/21M-41]1/4f01/20M1][1/21M-31]]g[f11/21M1][1/20M-31]] g。在定理2中，对于情况kn1（图5），我们得到：CCNGk; m 1; n 1 1 M1. 所以，我们得到M1/4/200M1] [1/201M-1] [1/211M1] [1/210M-1]在定理3中，给出了一种新的递归算法，用于对网格结构CCNG_k_递 归 算 法 的 时 间 复 杂 度 是 O<$N <$N ， 其 中 N<$N <$k<$1<$x<$m<$1<$x <$n<$1 <$。1/4 f00f 000001011010110111101 100gg[f01f100101111110010011001 000gg[f11f000001011010110111101 100gg[f10f100和101111110010011001 000ggM1¼f 0000000001 00011 00010 00110 00111 00101 00100g[f01100 01101 01111 01110 01010 01011 01001 01000g[1010010101 10111 10110 10010 10011 10001 10000g：此外，图4中的通过遍历网格结构的所有节点CCNG 1; 2; 2产生的该图是通过使用5位格雷码获得的。定理4. 在定理2中，使用以下递归算法来标记网格结构的节点CCNGk;m1;n1。的6. 压缩结果CCNG<$k;m;n<$的直径等于k <$m<$n，因为CCNG k;m;n在x维中有k条边，在y维中有m条边，在z维中有n条边。假设CCNG网络的节点连通度为n，且3 × mink; m; n<$6 n 6 k <$m<$n. 因此，CCNG的一些性质可以如表1所示。CCNG中的节点数等于超立方体H中的节点数。CCNG中的边数小于超立方体H中的边数，因此，CCNG-[k;m;n]-[a]-[b]-[a]-[b更比Hkmn更容易画。CCNG的直径等于超立方体H的直径。CCNG的成本低于Hk mn的成本。 可以看出，CCNG<$k; m; n<$k比超立方体H<$k<$m <$n<$k稀疏。表1说明了关于CCNGk;m;nn和超立方体的一些信息。可以看出，CCNGk;m;n比超立方体更稀疏，并且CCNGk;m;n是几乎常数度图，因为CCNGk;m;n的平均节点度为时间复杂性的的递归算法是在哪里13-2-k- 2-m-1- 2-n或3- 2-k- 2-m-1- 2-n。 因此其中M-k1是M1相对于镜子（xy-平面、xz-平面或yz-平面）的反射。算法-1。标签输入：m;n输出：标记为G<$CCNGk;m1;n1//Remark 1定义：M1¼½00011110]，M-1½10110100]开始1. fori←1tom2.对于j←1到n，3.如果我j2然后1 1 13 2 21所得到的结构可以递归地构造，另一方面，它是一个近似常数度的结构。CCNG k;m;n比H n稀疏，因此在连接性和成本方面优于H n（这种情况可以在表1中看到）。7. CCNG（k，m，n）上的路由以下算法是[18]中超立方体路由算法的修订版本。可以递归地构造CCNG k;m;n，因此可以以相同的方式处理路由过程这意味着可以从两个CCNGk-1; m; n或CCNGk; m-1; n或CCNG k; m; n-1构造CCNGk ; m ; n。CCNG网络k-1;m;n-1、CCNG网络k;m- 1;n-1和CCNG网络k;m;n-1中的任何一个都可以看作是CCNG网络k;m;n的次立方网络。路由过程至少需要一个源节点和一个目标节点。假设源节点S1/4 sr s r-1. s0和目标节点T1/4 tr t r-1.. . t0.5.G←M3;6.returnG;7.其他8.M1j 2←½0M1j 1][1/21M-i11];9.M-i12←½1M1j 1][½0M-i11];将有两种情况：情况1：如果sr tr1，则源节点和目标节点在不同的次立方网络中。给你的信息必须是转移超过的边缘S-R-R-1 s0;t r t r-1. t0to吉吉10.M12013年1月3日我的天←1/20百万美元吉吉][½1M-i12];包含目标节点的子立方体网络。运算符表示异或运算符。此时11.G← M1;消息将位于标签s r s r-1的节点上. s0。 如果12.returnG;13.端14.结束15. 结束结束s r s r-1... s0¼t r t r-1. t0，然后路由将终止。否则，如果sr-1tr-1¼1，则消息将被传输到节点的标签s r s r-1... s0。如果s r s r-1... s0t r t r-1. t0，然后路由将终止。 该过程以这种方式继续，直到消息到达目标节点。940B. Selçuk，A.Karci/Engineering Science and Technology，an International Journal 20（2017）934ðÞ¼ðÞSL;¼¼;......的人。==情况2：如果srtr¼0，则路由过程将被处理，SH<$/和SL<$/标签的下一位（sr-1）。算法2。 路由路由（S、T、K、MSG）//假设CCNG=k; m; n= V; E=其中V是节点集，E是边集。jVj <$2 r1，初始k<$r，S代表s k s k-1。. 0和T代表t k t k-1... t0.1. 如果kP0，I) 如果s k s k-1... s0¼t k t k-1. t0然后终止II) elseifs k s k-1. s0-t k t k-1... t0和sktk¼1发送消息到节点s k s k-1. s0路由（s k-1. s0，t k-1. t0，k-1，MSG）i←1 2r 2如果S½i]>S½r=2i]，则SH[fS½i]gSL¼SL[fS½r=2i]g其他SL¼SL[fS½i]gSH¼SH[fS½r=2π πi]g在构造SL和SH序列之后，P处理器将较小值序列SL_SL_发送到处理器Q_qv-1qv-2. . q0¼pv-1pv-2.. . 均p0. 这个过程会继续到下一个处理器，序列，直到发送过程终止（ts是启动时间用于传输，Tw是通过链路传输一个的时间）。III）否则路由（s k-1. s0，t k-1. t0，k-1，MSG）算法3。排序BitonicSortCCNGP; S8.CCNG（k，m，n）上的排序在这一节中，双调排序算法被映射到CCNG k;m;n的动机的工作[4]。双调排序算法是一种基于并行结构的排序算法。双调排序算法是目前已知的最快的并行排序算法之一。双调排序由双调序列的合并步骤组成。如果一个序列由一个非减单调序列和一个非增单调序列组成，则称该序列为双调序列。循环移位过程不会使双调序列变成非双调序列，即双调序列在循环移位过程之后仍然保持双调。CCNG k;m;n上的双调排序可以描述如下：假设序列在标号处理器上ppv-1pv-2... p0，序列是大小为r的S。P处理器对序列S的元素进行如下比较，并构造两个新的序列：SH由较大的元素组成;SL由较小的元素组成。//分区步骤1. i ← v-1; v-2;.. . ; 02.SH<$/和SL<$/3.i← 1; 2;. ;jSj=24.如果S½i]>S½ jSj=2i]，则5.SH¼SH[fS½i]g6.SL¼SL[fS½jSj=2i]g7.其他8.SL¼SL[fS½i]g9.SH¼SH[fS½jSj=2i]g10. 如果Q¼pv-1pv-2.. . p i pi-1... p01/4qv-1qv-2. qiqi-1.. . q0存在于11.发送SL到Q12.S¼SH//合并步骤13. 排序S中的元素在P14.0; 1;... ;v-2;v-115.接收来自Qpv-1pv-2.. . p i pi-1... p0qv-1qv-2... qiqi-1.. . q016.S=合并（S，SL）见图6。 双调排序算法的划分阶段。B. Selçuk，A.Karci/Engineering Science and Technology，an International Journal 20（2017）934941ðÞ2v2v22SW2222vS2vSW1111S2v2vST比较<$22···2v<$r1 -2v2222v2v见图7。 双调排序的合并阶段。备注2. CCNG k;m;n上双调排序的时间复杂度可以描述。有两种消息发送技术，如存储和转发和虫洞。所有消息都T分选1/4O。Rlgr-rv在一个链路上传输，因此，T之间将没有差异6vt rt.1þ1þ ···þ1Σ存储和转发和虫洞的最大数量1/4vtt. 1-1小时后，排序时间、累计排序子序列时间、合并时间。第一步：ts twrT合并我是说...1-1个半小时2第二步：t st wr..ð1Þ在合并步骤中将消耗相同的时间。因此，算法3的时间复杂度可以通过以下公式计算：步骤：tstrw2vTv;r传输CBT比较CSTT排序CO2累积PTT合并.- 是的Σ不联系我们你好，我很好。 rlg r-rv vt rt奥勒什河变速箱6vtsrtw22米.. .102v¼vt sþrt w 1 -2v1/4O。vtrt r2关于我们s w2v2v传输步骤中的比较次数为罗 罗河 1Σ实施例2. CCNG上的双调排序算法 可以用一个例子来解释。假设这个序列S12f23; 1; 5;- 5;-7;0;60; 45;- 23; 34;- 43;11;10; 111;- 45;-70; 15;- 89;- 16;100; 101;-20; 120; 56;- 28; 2;6; 9;- 78;30; 32; 66g积累传输步骤为n。该消耗可以分为五个部分：传输时间，构造SL的比较时间，WWW联系我们942B. Selçuk，A.Karci/Engineering Science and Technology，an International Journal 20（2017）934¼f-- -一种----Gf-g¼ðÞð Þ1/4fgð Þ公司简介ðÞðÞðÞ可以在CCNG1; 2; 1上排序，如图3所示，源节点为0100。 节点0100将S分成SH 23; 1; 5; 100; 101; 0; 120;56;二十三、三十四、六、十一、十、一一一、三十二、六十六2019-05-1500：00：00 00：00 00：00 00：00七十八、三十、四十五、七十。 节点0100保持子序列SH并将子序列SL发送到节点1100。在第二步骤中，节点0100和1100是源节点。两个节点都将其当前序列划分为子序列。节点向节点0000发送SL23; 1; 5; 11; 10; 0;32;56，并且保持序列SH23; 34; 6; 100; 101; 111; 120; 66。源节点1100保持序列SH/f15;2;-16;9;-7;30;60;45g，并且发送序列SL1/4f-28;-89;-43;-5;-7;-78;-20;-45;-70g 到节点1000.在第三步中，有四个源节点，例如0100、0000、1100和1000。所有源处理器将它们的序列分成两个子序列，并保持SH子序列和发送子序列。双调排序的划分阶段如图所示。 六、最后一步未在此图中显示 图图7描绘了双调排序的合并阶段，并且可以看出节点1100包含子序列f-89;- 78;- 70;- 45;- 43;- 28;- 20;-16;-9;-7;-5; 2; 15; 30; 45; 60g节点0100包含子序列f-23; 0; 1; 5; 6; 10; 11; 23; 32; 34; 56; 66; 100; 101; 111; 120g：双音步的最后一步是合并过程，f-89;- 78;- 70;- 45;- 43;- 28;- 20;-16;-9;- 7;- 5; 2; 15; 30; 45; 60g和f-23; 0; 1; 5; 6; 10; 11; 23; 32; 34; 56; 66; 100; 101; 111; 120g：合并两个序列后，9. 结论本文导出了Hn的一个新的变形我们得到了一个具有递归构造过程的连通三次网络H n。然后分析了所得网络在节点总数、边总数网络的代价、网络的哈密尔顿性。提出了CCNG网络k;m;n的路由算法CCNG k;m;n是超立方体的一个变体，是可递归构造的.此外，它最重要 的 性 质 是 它 是 几 乎 常 数 度 网 络 ， 其 中 节 点 度 近 似 接 近 4 。CCNGk;m;n在稀疏性和代价方面优于H3n确认作者非常感谢Basel Maurzah教授（约旦大学，约旦）和ErginYılmaz博士（土耳其Bülent Ecevit大学）提出的宝贵建议，这些建议有助于大大改进论文。引用[1] M. Abd-El-Barr，T.F. Somani，分层互连网络的拓扑性质的回顾和比较，J. Electr.Comput。工程师：2011年1月，2011年。[2] M. Abdullah，E. Abuelrub，文学士Maurzah，链式立方树互连网络，阿拉伯国际信息技术杂志，Zarka私立大学，约旦8（3）（2011）334-343。[3] A.E. Amawy，S.李晓菲，折叠超立方体的性质和性能，IEEETrans. 平行分布 系统2（1）（1991）31-42.[4] S.W. Al-Haj Baddar ， 文 学 士 Maurzah ， Bitonic sort on a chained-cubictreeinterconnection network ， J. Parallel Distrib. Comput. 74 （ 2014 ） 1744-1761。f-89;-78;-70;-45;-43;-28;-23;-20;-16;-9;-7;-5; 0; 1; 2; 5; 6; 10; 11; 15; 23; 30; 32; 34; 45; 56; 60; 66; 100; 101; 111; 120g：B. Selçuk，A.Karci/Engineering Science and Technology，an International Journal 20（2017）934943[5] H.- Y.昌河，巴西-地J. Chen，增量可扩展折叠超立方体图，J。信息科学Eng.16（2）（2000）29