关于煎饼网络及层次环煎饼网络的几个猜想

师海忠，汪生龙

（西北师范大学数学与统计学院，甘肃 兰州 730070）

0 引言

互连网络是超级计算机的重要组成部分，互连网络在很大程度上决定并行计算机的性能，计算机或服务器或通讯互连网络常常模型化为一个无向图，顶点对应计算机或服务器或通讯站点，边对应通信信道[2-5]。煎饼图网络 Pn是由Cayley图模型设计出来的的互连网络[5-9]。煎饼网络有一个弱点即结点度随着网络规模的增大而增大。为改进这一弱点，师海忠提出了互连网络的层次环群论模型，据此模型设计出了层次环煎饼网络 Pn×Zk1×Zk2×...× Zkq上述层次环煎饼网络具有 n !k1k2…kq个顶点且是n - 1+ 2 q正则的。它具有许多优良的性质[10-37]，但关于它的结构尚未完全清楚。师海忠提出了关于他的一个猜想(具体见第5节)。

本文其余结构如下：第2节，基本概念；第3节，关于煎饼网络的一簇猜想和 P5的圈分解；第4节，煎饼网络 Pn(n ≥ 3 )的两类圈；第5节，关于图G × Zk1× Zk2×…× Zkq(ki≥3,i = 1,2 … q)的 一 个 猜想；第6节，关于Pn×Z2的一个猜想；第7节，结束语。

1 基本概念

1.1 Cayley图的定义

1.2 煎饼图的定义

定义2：煎饼图中：顶点集为符号1,2,…n上的对称群 Sn，生成元集为：

由此生成的凯莱图称为煎饼网络，记为 Pn.煎饼网络 P4图1所示：

图1 煎饼网络P4Fig.1 Pancake network P4

1.3 煎饼图的另一等价定义

定义 3: 在煎饼图 Pn=（sy mn,PR）中 s ymn为对称群上的集合；PR为 s ymn中生成元组成的集合，即：

1.4 笛卡尔乘积图定义

定义 4：笛卡尔乘积图：设 G1= （ V1, E1）和G2= （ V2, E2）为两个图，则其笛卡尔乘积图 G1× G2的定义如下：

顶点集为：

边集为：

此定义可推广到n个图的笛卡尔乘积图 G1×G2×…×Gn。在文献[10]中师海忠提出互连网络的层次环群论模型-Cayley层次环网络：

G×Zk1×Zk2×…×Zkq(其 中G为 度 为d的Cayley 图)。

当G为煎饼网络 Pn时称为煎饼层次环网络Pn×Zk1×Zk2×…×Zkq进 而 当q = 1 ,k1= 3 时 有 网 络Pn×Z3具体构造如下：

顶点集 V （Gn）:

边集 E （Gn）:

2 关于煎饼网络的一簇猜想和P5的圈分解

2.1 关于煎饼网络的一簇猜想

在文献[1]中师海忠提出关于煎饼网络的一簇猜想：

猜想1：对于任意一个煎饼图 Pn：对任意自然数 n ≥ 2 ，如果n是奇数，则煎饼网络 P是个n边不交的哈密尔顿圈的并；如果n是偶数，则煎饼网络是个边不交的哈密尔顿圈以及一个完美对集的并。

并且证明了当 n = 2 ,3,4时该猜想成立[1]。当n≥ 5 时，猜想1仍然是一个开问题。在这里汪生龙给出了煎饼图 P5的两种特殊分解。

2.2 煎饼网络P5的两种圈分解

2.2.1 P5的第一种圈分解

定理1：P5可分解一个哈密尔顿圈 C120和一个长为78的小圈 C78以及一个长为12的小圈 C12和三个长为10的小圈 C10.

定理 2： P5可分解另外的一个哈密尔顿圈 C120和一个长为78的小圈 C78以及一个长为12的小圈C12和三个长为10的小圈 C10.

3 煎饼网络Pn(n≥3)的两类圈

3.1 煎饼网络Pn(n≥3)的长为6的小圈

长为6的小圈 C6是煎饼图 Pn（n≥ 3 ）中的一类特殊的小圈[9]，一个煎饼图 Pn（n≥ 3 ）中长为6的小圈 C6可以是相互独立的并且它的形式也是唯一的即 C6=r3r2r3r2r3r2，由它的形式可知如果形成长度为6的小圈则固定后面的（n- 3 ）位保持不变前3位按上述形式变换即可。于是得出了煎饼图 Pn（n≥ 3 ）中相互独立的6圈的总数 N （C6）。即：

3.3 煎饼网络 Pn(n≥3)中长为 l！(3≤l≤n)的圈

我们又可以得出一个主要的结论即任意一个煎饼网络 Pn（n≥ 3 ）中长为的相互独立的小圈 Cl!的数目 N （Cl!）是确定的即：

证明：我们已经知道任意一个煎饼网络Pn（n≥ 3 ）中存在长为6,7,8...n!的圈，因此可以断言在煎饼图 Pn（n≥ 3 ）中存在长为 l（3≤ l≤n）的小圈。相互独立的小圈是指对于任意两个小圈：

当 vi≠vj且ei≠ej（i = 1,2,3...m, j = 1 ,2,3...n）时，我们称小圈 C1与 C2是相互独立的，即边和顶点都不相同的小圈称为相互独立的圈。

煎饼图 Pn中的顶点数为 n !，而长为 l!的圈的顶点数也为 l!因此在一个煎饼图 Pn（n≥ 3 ）中长为l! （3≤ l ≤ n ）的相互独立的圈的总数 N （l!）是确定的即：

4 关于图G×Zk1×Zk2×…Zkq(ki≥3, i=1,2…q)的一个猜想

在文献[10]中对于图 G ×Zk1×Zk2×…×Zkq(ki≥3,i = 1 ,2 … q )(G是顶点度为d的 C ayley图)师海忠提出了一个猜想，具体猜想如下：

猜想1：当 d + 2 q为偶数时，图 G ×Zk1× Zk2×...× Zkq可分解为个边不交的哈密尔顿圈的并；当 d + 2q为奇数时，图 G ×Z ×Z ×…×Z可分解为

k1k2kq个边不交的哈密尔顿圈和一个完美对集的并。

当 G = Pn时，则上述猜想变为：

猜想2′：当 n - 1+ 2 q为偶数时，图 Pn×Zk1××…×Z （n ≥ 2）可分解为个边不交的kq哈密尔顿圈的并；当 n - 1+ 2 q为奇数时，图 Pn×Zk1×× . ..× Z （n ≥ 2 ）可分解为个边不交的 kq哈密尔顿圈和一个完美对集的并。

下面证明当 n =2,3,4且q = 1 ,kq= 3 时上述猜想是正确的。为清楚表达，称Pn×Z3为（n, 3）-煎饼网络。

当 n =2时，（2,3）-煎饼网络是一个哈密尔顿圈C6和一个完美对集的并。

当 n =2， q =1， kq= 3时，猜想2′成立。

当 n =3时，（3,3）-煎饼网络是两个边不交的哈密尔顿圈 C18的并。

当 n =3， q =1， kq= 3时，猜想2′成立。

当 n =4时，（4,3）-煎饼网络是两个边不交的哈密尔顿圈 C72和一个完美对集M的并。当 n =4， q =1， kq= 3 时，猜想2′成立.当 n ≥ 5 时，猜想2′仍然是个开问题。

5 关于Pn×Z2的一个猜想。

当 G =Pn且 q = 1 ,kq= 2 时师海忠提出如下猜想。

n2 边不交的哈密尔顿圈的并。

n 2 交的哈密尔顿圈和一个完美对集的并。

下面证明当 n = 2 ,3时，上述猜想是正确的。

为清楚表达，Pn×Z2称为 （n，2） - 煎饼网络。

当 n =2时，（2,2）-煎饼网络是一个哈密尔顿圈 C4。

故当 n = 2 时猜想3成立。

当 n =3时，（3,2）-煎饼网络是一个哈密尔顿圈C12和一个完美对集M的并。

故当 n = 3 时猜想3成立。

当 n =4时，（4, 2）-煎饼网络是一个哈密尔顿圈C48和6个长为8的小圈 C8的并。

（4,2）-煎饼网络图2所示。

图2 (4,2)-煎饼网络P4×Z2Fig.2 (4,2)- Pancake network P4×Z2

6 结束语

煎饼图 Pn网络是著名的一种互连网络，通过对煎饼图网络的分析可知，每相邻两个煎饼图网络 Pn与 Pn-1之间存在着密切的关系，即 Pn-1中的哈密尔顿圈是 Pn中的边不交的小圈，并且通过对 P5的一类特殊分解对任意煎饼图 Pn（n≥ 5 ）有了一个整体的认识，而 Gn= Pn× Z3网络具有更加优越的性质，具有很好的扩展性。对（n, 3, m）-煎饼图层次环网络>P ×Z ×Z ×…×Z =P ×Zm的性质有待进一步的n333n3研究。在第5节中我们提出了一类重要的猜想，这些猜想揭示了Cayley图层次网络的整体结构，猜想2′当 n = 2 ,3,4时正确的，当n较大时是否正确尚未可知，更倾向于它们是正确的。但对煎饼图网络 Pn和 （n,k1, k2…kq）-煎饼图层次环网络Pn×Zk1×Zk2×…的研究仅仅是一个开始，对它们的进一步研究有待进一步探索。

[1] 师海忠, 路建波. 关于互连网络的几个猜想[J]. 计算机工程与应用, 2008, 44(31): 112-115.

[2] 徐俊明. 组合网络理论[M]. 北京: 科学出版社, 2007.

[3] 师海忠. 互连网络的代数环模型[D]. 博士论文, 北京: 中国科学院, 应用数学研究所, 1998.

[4] Xu Junming. A First Course in Graph Theory[M]. 北京: 科学出版社, 2015.

[5] 王鼎兴, 陈国良. 互连网络结构分析[M]. 北京: 科学出版社, 1990.

[6] 张禾瑞. 近世代数基础[M]. 北京: 高等教育出版社, 1978.

[7] 张禾瑞. 近世代数基础[M]. 北京: 高等教育出版社, 2008.

[8] S.B.Akers, B.Krishnamurthy. A group-theoretic model for symmetric interconnection network[J]. IEEE Transaction on Computers, 1989, 38(4): 555-565.

[9] E.K. Small cycles in the pancake graph. ARS MATHEMATICA CONTEMPORANEA 7 (2014) 237-246.

[10] SHI Haizhong, SHI Yue. A Hierarchical Ring Group-Theoretic Model for Interconnection Networks. http://vdisk.weibo.com/s/dlizJyfeBX-2J [电子文献].

[11] J A Bondy, Murty U S R. Praph theory with applications [M].New York: AmericanElserer, 1976.

[12] 师海忠. 几类新的笛卡尔乘积互连网络[J]. 计算机科学,2013, 40(6A): 265-270.

[13] 高随祥. 图论与网络流理论[M]. 北京: 高等教育出版社,2008.

[14] 师海忠. 互连网络的新模型: 多部群论模型[J]. 计算机科学, 2013, 40(9): 21-24.

[15] K, Kaneko.: Hamiltonian cycles and hamiltonian paths in faulty burnt pancake graphs. IEICE Trans.Inf.and Systems 2007, E90-D(4): 716-721.

[16] S.Asai, Y.Kounoike, Y.Shinano and K.Kaneko, Computing the diameter of 17-pancake graph using a PC cluster, 2006,LNCS4128: 1114-1124.

[17] W. H. Gates and C. H. Papadimitriou, Bounds for sorting by prefix-reversal, Discrete Mathmatics. 27, (1979), 47-57.

[18] H. Dweighter, E 2569 in: Elementary problems and solutions,America. Math. Monthly 82(1975)1010.

[19] Ping-Ying Tsai, Jung-Sheng Fu, Gen-Huey Chen, Edgefault-tolerant Hamiltonicity of pancake graphs under the conditional fault model, Theoretical Computer Science,409(2008): 450-460.

[20] Cheng-Kuan Lin, Hua-Min Huang, Lin-Hsing Hsu, The super connectivity of the pancake graphs and the super laceability of the star graphs, Theoretical Computer Science, Volume 339, Lssues2-3, 12 June 2005, 257-271.

[21] Cheng-Kuan Lin, Yuan-Kang Shih, Jimmy J. M. Tan,Lih-Hsing Hsu, Mutually independent Hamiltonian cycles in some graphs, Ars Combinatoria, 2009.

[22] Chao-Ming Sun, Cheng-Kuan Lin, Hua-Min Huang,Lish-Hsing Hsu. Mutually independent Hamiltonian paths and cycles in hypercubes, Journal of Interconnection Networks, Vol.7(2), 2006, 235-255.

[23] M.H. Hyedari and I. H. Sudborough, On the diameter of the pancake network, Journal of Algorithms 25 (1997), 67-94.

[24] I. J. Dejter, O. Serra, Efficient dominating sets in Cayley graphs, Discrete Appl. Mathmatics. 129 (2003), 319-328.

[25] A. Kanevsky and C. Feng, On the embedding of cycles in pancake graphs, Parallel Conputing 21 (1995), 923-936.

[26] E. V. Konstantinova, A. N. Medvedev, Cycles of length seven in the pancake graph, Diskretn. Anal. Issled. Oper. 17(2010), 46-55 (in Russian).

[27] J. J. Shen, J. J. M. Tan, K. T. Chu, Cycle embedding in pancake interconnection networks, Proc. 23rd workshop on Combinatorial Mathmatics and Computation Theory, Taiwan(2006): 85-92.

[28] J. Cibulka, On average and highest number of flips in pancake sorting, Theoretical Computer Science 412 (2011), 822-834.

[29] 张欣, 师海忠. 交叉立方体连通圈网络的Hamilton分解[J].软件, 2015, 36 (8) : 92-98.

[30] 王海峰, 师海忠. Möbius超立方体网络的Hamilton分解[J].软件, 2015, 36(10): 85-88.

[31] 常立婷, 师海忠. 基于超立方体和圈的细胞分裂生长网络及其性质[J]. 软件,2017, 38(9): 141-149.

[32] 胡艳红 师海忠. 关于冒泡排序连通圈网络猜想的一个注记[J]. 软件, 2016, 37(01): 91-100.

[33] 史小玲. 集团网网络可靠性的探讨及实例研究[J]. 软件,2016, 37(01): 117-119.

[34] 韩江雪, 李昕. 基于NS2 的多层卫星网络路由协议开发方案[J]. 软件, 2016, 37(02): 63-65.

[35] 刘静. 基于独立生成树的网络多路径传输方法研究[J]. 软件, 2016, 37(4): 25-28.

[36] 果真, 艾文宝. 双向中继网络中安全波束成形向量设计[J].软件, 2016, 37(02): 170-173.

[37] 史小玲. 集团网网络可靠性的探讨及实例研究[J]. 软件,2016, 37(01): 117-119.