關于煎餅網絡及層次環煎餅網絡的幾個猜想

師海忠，汪生龍

（西北師范大學數學與統計學院，甘肅 蘭州 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.