變形的蜂窩環輪面

Deformed Honeycomb Tori

石圜鋼(Yuan-Kang Shih)

指導教授 ： 高欣欣

中原大學/理學院/應用數學研究所/碩士(2006年)

https://doi.org/10.6840/cycu200600175

摘要

在平行和分散式的網際網路中，有一種名為一般化蜂窩環輪面(Generalized Honeycomb Tori GHT(m,n,s))的圖形被廣泛應用。在一般化蜂窩環輪面家族中，有一種被稱為六角形蜂窩環輪面(Honeycomb Hexagonal Torus HT(n))的圖形，其結構是非常對稱的，因而吸引眾多學者去深入研究及探討。而六角形蜂窩環輪面圖形是由一個參數n所決定，故其圖形在擴張時是非常規則的同時向外延伸。在這篇文章中，我們提出一個新的圖形概念，這個新圖形是由六角形蜂窩環輪面所衍生出來的，我們將其命名為變形的蜂窩環輪面(Deformed Honeycomb Tori DHT(h,l,r))，此圖形是由三個參數所決定出來的，而這三個參數彼此都是互相獨立的。最後我們將會給一個明確的對應方式，藉以說明我們所提出之變形的蜂窩環輪面是一般化蜂窩環輪面的一個子集。

關鍵字

網際網路 ； 網路連結 ； 蜂窩環輪面

並列摘要

Assume that m, n and s are integers with m >= 2, n >= 4, 0 <= s < n and s is of the same parity of m. The generalized honeycomb tori GHT(m, n,s) have been recognized as an attractive architecture to existing torus interconnection networks in parallel and distributed applications. Among the various families of graphs of GHT(m, n, s), numerous studies are devoted to honeycomb hexagonal torus HT(n) due to its nice symmetrical structure. Although each vertex of HT(n) is described by a three-dimensional coordinate (x, y, z), the graph grows uniformly in the three directions. In this article, we propose a new class of graphs extended from HT(n), namely, deformed honeycomb torus DHT(h, l, r). DHT(h, l, r) is defined to allow the graph to grow in the three independent dimensions. We prove that this more general class of graphs still remains a subset of the generalized honeycomb torus. Furthermore, for any given DHT(h, l, r), we have a concrete correspondence between its vertex set and the associated GHT(m, n, s).

並列關鍵字

interconnection ； Honeycomb torus ； network

參考文獻

[1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, North-

Holland, New York, (1980).

[3] H. Cho, and L. Hsu, “Generalized Honeycomb Torus”, Information

[4] G.M. Megson, X. Yang, and X. Liu, “Honeycomb Tori are Hamiltonian”,

Information Processing Letters, vol. 72, pp. 99–103, 1999.