臺灣博碩士論文加值系統

在平行和分散式的網際網路中，有一種名為一般化蜂窩環輪面(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).

1 Introduction...............................................................2
2 Preliminary................................................................4
3 EveryDHT(h,l,r) is a generalized honeycomb torus...........................6
4 Conclusion................................................................17
A Examples For Lemma 2......................................................19
B Example For Lemma 4.......................................................23

1.1 The graphs (a)HT(1) (b)HT(2) (c)HT(3)....................................3
2.1 The graph GHT(8, 6,2)....................................................5
3.1 DHT(2, 3,6) for Lemma 4.................................................11
3.2 The isomorphic graphs (a)DHT(2, 3, 6) and (b)GHT(3, 24,17)..............12
3.3 A example for case 1 of Theorem 1.......................................14
3.4 A example for case 2 of Theorem 1.......................................14
A.1 The path patterns Pt1(i, j), P2(i, j) and P3(i, j) for DHT(2, 3,6)......19
A.2 The path pattern Q(i, j) for DHT(2, 3,6)................................20
A.3 The path pattern R(i, j) for DHT(2, 3,6)................................20
A.4 The path pattern S(i, j) for DHT(2, 3,6)................................21
A.5 The path pattern T(i, j) for DHT(2, 3, 6) when l = g0...................21
A.6 The path pattern T(i, j) for DHT(2, 4, 10) when l = g0.................22

[1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, North-
Holland, New York, (1980).
[2] J. Carle, J-F. Myoupo, and D. Seme, “All-to-All Broadcasting Algorithms
on Honeycomb Networks and Applications”, Parallel Processing Letters,
vol. 9, pp. 539–550, 1999.
[3] H. Cho, and L. Hsu, “Generalized Honeycomb Torus”, Information
Processing Letters, vol. 86, pp. 185–190, 2003.
[4] G.M. Megson, X. Yang, and X. Liu, “Honeycomb Tori are Hamiltonian”,
Information Processing Letters, vol. 72, pp. 99–103, 1999.
[5] G.M. Megson, X. Liu, and X. Yang, “Fault-Tolerant Ring Embedding in a
Honeycomb Torus with Nodes Failures”, Parallel Processing Letters, vol.9,
pp. 551–561, 1999.
[6] B. Parhami, “A Introduction to Parallel Processing: Algorithms and
Architectures”, Plenum Press, New York, 1999.
[7] B. Parhami and D.M. Kwai, “A Unified Formulation of Honeycomb and Diamond
Networks”, IEEE Trans. Parallel and Distributed Systems, vol. 12,
pp. 74–80, 2001.
[8] I. Stojmenovic, “Honeycomb Networks: Topological Properties and
Communication Algorithms”, IEEE Trans. Parallel and Distributed Systems,
vol. 8, pp. 1036–1042, 1997.
[9] X. Yang, D. J. Evans, H. Lai, and G. M. Megson, “Generalized honeycomb
torus is hamiltonian”, Information Processing Letters, vol. 92,
pp. 31–37, 2004.