關(guān)于煎餅網(wǎng)絡(luò)及層次環(huán)煎餅網(wǎng)絡(luò)的幾個(gè)猜想

師海忠，汪生龍

（西北師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅 蘭州 730070）

0 引言

互連網(wǎng)絡(luò)是超級(jí)計(jì)算機(jī)的重要組成部分，互連網(wǎng)絡(luò)在很大程度上決定并行計(jì)算機(jī)的性能，計(jì)算機(jī)或服務(wù)器或通訊互連網(wǎng)絡(luò)常常模型化為一個(gè)無向圖，頂點(diǎn)對(duì)應(yīng)計(jì)算機(jī)或服務(wù)器或通訊站點(diǎn)，邊對(duì)應(yīng)通信信道[2-5]。煎餅圖網(wǎng)絡(luò) Pn是由Cayley圖模型設(shè)計(jì)出來的的互連網(wǎng)絡(luò)[5-9]。煎餅網(wǎng)絡(luò)有一個(gè)弱點(diǎn)即結(jié)點(diǎn)度隨著網(wǎng)絡(luò)規(guī)模的增大而增大。為改進(jìn)這一弱點(diǎn)，師海忠提出了互連網(wǎng)絡(luò)的層次環(huán)群論模型，據(jù)此模型設(shè)計(jì)出了層次環(huán)煎餅網(wǎng)絡(luò) Pn×Zk1×Zk2×...× Zkq上述層次環(huán)煎餅網(wǎng)絡(luò)具有 n !k1k2…kq個(gè)頂點(diǎn)且是n - 1+ 2 q正則的。它具有許多優(yōu)良的性質(zhì)[10-37]，但關(guān)于它的結(jié)構(gòu)尚未完全清楚。師海忠提出了關(guān)于他的一個(gè)猜想(具體見第5節(jié))。

本文其余結(jié)構(gòu)如下：第2節(jié)，基本概念；第3節(jié)，關(guān)于煎餅網(wǎng)絡(luò)的一簇猜想和 P5的圈分解；第4節(jié)，煎餅網(wǎng)絡(luò) Pn(n ≥ 3 )的兩類圈；第5節(jié)，關(guān)于圖G × Zk1× Zk2×…× Zkq(ki≥3,i = 1,2 … q)的 一 個(gè) 猜想；第6節(jié)，關(guān)于Pn×Z2的一個(gè)猜想；第7節(jié)，結(jié)束語。

1 基本概念

1.1 Cayley圖的定義

1.2 煎餅圖的定義

定義2：煎餅圖中：頂點(diǎn)集為符號(hào)1,2,…n上的對(duì)稱群 Sn，生成元集為：

由此生成的凱萊圖稱為煎餅網(wǎng)絡(luò)，記為 Pn.煎餅網(wǎng)絡(luò) P4圖1所示：

圖1 煎餅網(wǎng)絡(luò)P4Fig.1 Pancake network P4

1.3 煎餅圖的另一等價(jià)定義

定義 3: 在煎餅圖 Pn=（sy mn,PR）中 s ymn為對(duì)稱群上的集合；PR為 s ymn中生成元組成的集合，即：

1.4 笛卡爾乘積圖定義

定義 4：笛卡爾乘積圖：設(shè) G1= （ V1, E1）和G2= （ V2, E2）為兩個(gè)圖，則其笛卡爾乘積圖 G1× G2的定義如下：

頂點(diǎn)集為：

邊集為：

此定義可推廣到n個(gè)圖的笛卡爾乘積圖 G1×G2×…×Gn。在文獻(xiàn)[10]中師海忠提出互連網(wǎng)絡(luò)的層次環(huán)群論模型-Cayley層次環(huán)網(wǎng)絡(luò)：

G×Zk1×Zk2×…×Zkq(其 中G為 度 為d的Cayley 圖)。

當(dāng)G為煎餅網(wǎng)絡(luò) Pn時(shí)稱為煎餅層次環(huán)網(wǎng)絡(luò)Pn×Zk1×Zk2×…×Zkq進(jìn) 而 當(dāng)q = 1 ,k1= 3 時(shí) 有 網(wǎng) 絡(luò)Pn×Z3具體構(gòu)造如下：

頂點(diǎn)集 V （Gn）:

邊集 E （Gn）:

2 關(guān)于煎餅網(wǎng)絡(luò)的一簇猜想和P5的圈分解

2.1 關(guān)于煎餅網(wǎng)絡(luò)的一簇猜想

在文獻(xiàn)[1]中師海忠提出關(guān)于煎餅網(wǎng)絡(luò)的一簇猜想：

猜想1：對(duì)于任意一個(gè)煎餅圖 Pn：對(duì)任意自然數(shù) n ≥ 2 ，如果n是奇數(shù)，則煎餅網(wǎng)絡(luò) P是個(gè)n邊不交的哈密爾頓圈的并；如果n是偶數(shù)，則煎餅網(wǎng)絡(luò)是個(gè)邊不交的哈密爾頓圈以及一個(gè)完美對(duì)集的并。

并且證明了當(dāng) n = 2 ,3,4時(shí)該猜想成立[1]。當(dāng)n≥ 5 時(shí)，猜想1仍然是一個(gè)開問題。在這里汪生龍給出了煎餅圖 P5的兩種特殊分解。

2.2 煎餅網(wǎng)絡(luò)P5的兩種圈分解

2.2.1 P5的第一種圈分解

定理1：P5可分解一個(gè)哈密爾頓圈 C120和一個(gè)長為78的小圈 C78以及一個(gè)長為12的小圈 C12和三個(gè)長為10的小圈 C10.

定理 2： P5可分解另外的一個(gè)哈密爾頓圈 C120和一個(gè)長為78的小圈 C78以及一個(gè)長為12的小圈C12和三個(gè)長為10的小圈 C10.

3 煎餅網(wǎng)絡(luò)Pn(n≥3)的兩類圈

3.1 煎餅網(wǎng)絡(luò)Pn(n≥3)的長為6的小圈

長為6的小圈 C6是煎餅圖 Pn（n≥ 3 ）中的一類特殊的小圈[9]，一個(gè)煎餅圖 Pn（n≥ 3 ）中長為6的小圈 C6可以是相互獨(dú)立的并且它的形式也是唯一的即 C6=r3r2r3r2r3r2，由它的形式可知如果形成長度為6的小圈則固定后面的（n- 3 ）位保持不變前3位按上述形式變換即可。于是得出了煎餅圖 Pn（n≥ 3 ）中相互獨(dú)立的6圈的總數(shù) N （C6）。即：

3.3 煎餅網(wǎng)絡(luò) Pn(n≥3)中長為 l！(3≤l≤n)的圈

我們又可以得出一個(gè)主要的結(jié)論即任意一個(gè)煎餅網(wǎng)絡(luò) Pn（n≥ 3 ）中長為的相互獨(dú)立的小圈 Cl!的數(shù)目 N （Cl!）是確定的即：

證明：我們已經(jīng)知道任意一個(gè)煎餅網(wǎng)絡(luò)Pn（n≥ 3 ）中存在長為6,7,8...n!的圈，因此可以斷言在煎餅圖 Pn（n≥ 3 ）中存在長為 l（3≤ l≤n）的小圈。相互獨(dú)立的小圈是指對(duì)于任意兩個(gè)小圈：

當(dāng) vi≠vj且ei≠ej（i = 1,2,3...m, j = 1 ,2,3...n）時(shí)，我們稱小圈 C1與 C2是相互獨(dú)立的，即邊和頂點(diǎn)都不相同的小圈稱為相互獨(dú)立的圈。

煎餅圖 Pn中的頂點(diǎn)數(shù)為 n !，而長為 l!的圈的頂點(diǎn)數(shù)也為 l!因此在一個(gè)煎餅圖 Pn（n≥ 3 ）中長為l! （3≤ l ≤ n ）的相互獨(dú)立的圈的總數(shù) N （l!）是確定的即：

4 關(guān)于圖G×Zk1×Zk2×…Zkq(ki≥3, i=1,2…q)的一個(gè)猜想

在文獻(xiàn)[10]中對(duì)于圖 G ×Zk1×Zk2×…×Zkq(ki≥3,i = 1 ,2 … q )(G是頂點(diǎn)度為d的 C ayley圖)師海忠提出了一個(gè)猜想，具體猜想如下：

猜想1：當(dāng) d + 2 q為偶數(shù)時(shí)，圖 G ×Zk1× Zk2×...× Zkq可分解為個(gè)邊不交的哈密爾頓圈的并；當(dāng) d + 2q為奇數(shù)時(shí)，圖 G ×Z ×Z ×…×Z可分解為

k1k2kq個(gè)邊不交的哈密爾頓圈和一個(gè)完美對(duì)集的并。

當(dāng) G = Pn時(shí)，則上述猜想變?yōu)椋?/p>

猜想2′：當(dāng) n - 1+ 2 q為偶數(shù)時(shí)，圖 Pn×Zk1××…×Z （n ≥ 2）可分解為個(gè)邊不交的kq哈密爾頓圈的并；當(dāng) n - 1+ 2 q為奇數(shù)時(shí)，圖 Pn×Zk1×× . ..× Z （n ≥ 2 ）可分解為個(gè)邊不交的 kq哈密爾頓圈和一個(gè)完美對(duì)集的并。

下面證明當(dāng) n =2,3,4且q = 1 ,kq= 3 時(shí)上述猜想是正確的。為清楚表達(dá)，稱Pn×Z3為（n, 3）-煎餅網(wǎng)絡(luò)。

當(dāng) n =2時(shí)，（2,3）-煎餅網(wǎng)絡(luò)是一個(gè)哈密爾頓圈C6和一個(gè)完美對(duì)集的并。

當(dāng) n =2， q =1， kq= 3時(shí)，猜想2′成立。

當(dāng) n =3時(shí)，（3,3）-煎餅網(wǎng)絡(luò)是兩個(gè)邊不交的哈密爾頓圈 C18的并。

當(dāng) n =3， q =1， kq= 3時(shí)，猜想2′成立。

當(dāng) n =4時(shí)，（4,3）-煎餅網(wǎng)絡(luò)是兩個(gè)邊不交的哈密爾頓圈 C72和一個(gè)完美對(duì)集M的并。當(dāng) n =4， q =1， kq= 3 時(shí)，猜想2′成立.當(dāng) n ≥ 5 時(shí)，猜想2′仍然是個(gè)開問題。

5 關(guān)于Pn×Z2的一個(gè)猜想。

當(dāng) G =Pn且 q = 1 ,kq= 2 時(shí)師海忠提出如下猜想。

n2 邊不交的哈密爾頓圈的并。

n 2 交的哈密爾頓圈和一個(gè)完美對(duì)集的并。

下面證明當(dāng) n = 2 ,3時(shí)，上述猜想是正確的。

為清楚表達(dá)，Pn×Z2稱為 （n，2） - 煎餅網(wǎng)絡(luò)。

當(dāng) n =2時(shí)，（2,2）-煎餅網(wǎng)絡(luò)是一個(gè)哈密爾頓圈 C4。

故當(dāng) n = 2 時(shí)猜想3成立。

當(dāng) n =3時(shí)，（3,2）-煎餅網(wǎng)絡(luò)是一個(gè)哈密爾頓圈C12和一個(gè)完美對(duì)集M的并。

故當(dāng) n = 3 時(shí)猜想3成立。

當(dāng) n =4時(shí)，（4, 2）-煎餅網(wǎng)絡(luò)是一個(gè)哈密爾頓圈C48和6個(gè)長為8的小圈 C8的并。

（4,2）-煎餅網(wǎng)絡(luò)圖2所示。

圖2 (4,2)-煎餅網(wǎng)絡(luò)P4×Z2Fig.2 (4,2)- Pancake network P4×Z2

6 結(jié)束語

煎餅圖 Pn網(wǎng)絡(luò)是著名的一種互連網(wǎng)絡(luò)，通過對(duì)煎餅圖網(wǎng)絡(luò)的分析可知，每相鄰兩個(gè)煎餅圖網(wǎng)絡(luò) Pn與 Pn-1之間存在著密切的關(guān)系，即 Pn-1中的哈密爾頓圈是 Pn中的邊不交的小圈，并且通過對(duì) P5的一類特殊分解對(duì)任意煎餅圖 Pn（n≥ 5 ）有了一個(gè)整體的認(rèn)識(shí)，而 Gn= Pn× Z3網(wǎng)絡(luò)具有更加優(yōu)越的性質(zhì)，具有很好的擴(kuò)展性。對(duì)（n, 3, m）-煎餅圖層次環(huán)網(wǎng)絡(luò)>P ×Z ×Z ×…×Z =P ×Zm的性質(zhì)有待進(jìn)一步的n333n3研究。在第5節(jié)中我們提出了一類重要的猜想，這些猜想揭示了Cayley圖層次網(wǎng)絡(luò)的整體結(jié)構(gòu)，猜想2′當(dāng) n = 2 ,3,4時(shí)正確的，當(dāng)n較大時(shí)是否正確尚未可知，更傾向于它們是正確的。但對(duì)煎餅圖網(wǎng)絡(luò) Pn和 （n,k1, k2…kq）-煎餅圖層次環(huán)網(wǎng)絡(luò)Pn×Zk1×Zk2×…的研究僅僅是一個(gè)開始，對(duì)它們的進(jìn)一步研究有待進(jìn)一步探索。

[1] 師海忠, 路建波. 關(guān)于互連網(wǎng)絡(luò)的幾個(gè)猜想[J]. 計(jì)算機(jī)工程與應(yīng)用, 2008, 44(31): 112-115.

[2] 徐俊明. 組合網(wǎng)絡(luò)理論[M]. 北京: 科學(xué)出版社, 2007.

[3] 師海忠. 互連網(wǎng)絡(luò)的代數(shù)環(huán)模型[D]. 博士論文, 北京: 中國科學(xué)院, 應(yīng)用數(shù)學(xué)研究所, 1998.

[4] Xu Junming. A First Course in Graph Theory[M]. 北京: 科學(xué)出版社, 2015.

[5] 王鼎興, 陳國良. 互連網(wǎng)絡(luò)結(jié)構(gòu)分析[M]. 北京: 科學(xué)出版社, 1990.

[6] 張禾瑞. 近世代數(shù)基礎(chǔ)[M]. 北京: 高等教育出版社, 1978.

[7] 張禾瑞. 近世代數(shù)基礎(chǔ)[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 [電子文獻(xiàn)].

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

[12] 師海忠. 幾類新的笛卡爾乘積互連網(wǎng)絡(luò)[J]. 計(jì)算機(jī)科學(xué),2013, 40(6A): 265-270.

[13] 高隨祥. 圖論與網(wǎng)絡(luò)流理論[M]. 北京: 高等教育出版社,2008.

[14] 師海忠. 互連網(wǎng)絡(luò)的新模型: 多部群論模型[J]. 計(jì)算機(jī)科學(xué), 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] 張欣, 師海忠. 交叉立方體連通圈網(wǎng)絡(luò)的Hamilton分解[J].軟件, 2015, 36 (8) : 92-98.

[30] 王海峰, 師海忠. M?bius超立方體網(wǎng)絡(luò)的Hamilton分解[J].軟件, 2015, 36(10): 85-88.

[31] 常立婷, 師海忠. 基于超立方體和圈的細(xì)胞分裂生長網(wǎng)絡(luò)及其性質(zhì)[J]. 軟件,2017, 38(9): 141-149.

[32] 胡艷紅 師海忠. 關(guān)于冒泡排序連通圈網(wǎng)絡(luò)猜想的一個(gè)注記[J]. 軟件, 2016, 37(01): 91-100.

[33] 史小玲. 集團(tuán)網(wǎng)網(wǎng)絡(luò)可靠性的探討及實(shí)例研究[J]. 軟件,2016, 37(01): 117-119.

[34] 韓江雪, 李昕. 基于NS2 的多層衛(wèi)星網(wǎng)絡(luò)路由協(xié)議開發(fā)方案[J]. 軟件, 2016, 37(02): 63-65.

[35] 劉靜. 基于獨(dú)立生成樹的網(wǎng)絡(luò)多路徑傳輸方法研究[J]. 軟件, 2016, 37(4): 25-28.

[36] 果真, 艾文寶. 雙向中繼網(wǎng)絡(luò)中安全波束成形向量設(shè)計(jì)[J].軟件, 2016, 37(02): 170-173.

[37] 史小玲. 集團(tuán)網(wǎng)網(wǎng)絡(luò)可靠性的探討及實(shí)例研究[J]. 軟件,2016, 37(01): 117-119.