臺灣博碩士論文加值系統

多環網路Dn(h1,h2,...,hm)是一個具有n個點0,1,...,n-1，以及mn個邊的有向圖，其邊的連接形式為由點i連向點i+hj對n的同餘，滿足i=0,1,...,n-1且j = 1,2,...,m。在過去的幾年裡，多環網路常被當成區域網路結構來廣泛地研究。很多相互連通網路的性質都被探討，而其中漢米爾頓圈的存在性是所考慮的重要性質之一。關於雙環網路Dn(h1,h2)的漢米爾頓圈的存在性，黃老師和李老師獲得其充分且必要條件。在此篇論文中，我們討論當m≧3時的多環網路的漢米爾頓性質。

A multi-loop network Dn(h1,h2,...,hm) is a digraph with n vertices 0,1,...,n-1 and mn arcs of the form i to i+hj (mod n) for i=0,1,...,n-1 and j=1,2,...,m. The multi-loop networks have been widely studied as architectures for local area networks in the last few years. Many properties of the interconnection networks are studied. The existence of a hamilton cycle for an interconnection network is one of the most important property. For m=2, Dn(h1,h2) is called a double-loop network. Hwang and Li obtained a necessary and sufficient condition for the hamiltonicity of Dn(h1,h2). In this thesis, we study the hamiltonicity of the digraph Dn(h1,h2,...,hm) for m≧3.

Contents
摘要……………………………………………………………………… i
Abstract ……………………………………………………………… ii
誌謝…………………………………………………………………… iii
1 Introduction ……………………………………………………… 1
2 Definitions ………………………………………………………… 2
3 Previous Results of the Hamiltonicity for Multi-loop Networks …… 4
4 Our Main Results ………………………………………………… 7
5 Conclusions ……………………………………………………… 15
6 References ……………………………………………………… 16

J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, Macmillan, London; Elsevier, New York, (1976).
F. T. Boesch and R. Tindell, Circulants and their connectivities, J. Graph Theory 8 (1984) 487-499.
G. J. Chang, F. K. Hwang and L. D. Tong, The hamiltonian property of the consecutive-3 digraph, Math. Comp. Mod. 25 (1997) 83-88.
G. J. Chang, F. K. Hwang and L. D. Tong, The consecutive-4 digraphs are hamiltonian, J. Graph Theory 31 (1999) 1-6.
G. Chartrand and O. R. Oellerman, Applied and Algorithmic Graph Theory, {McGraw-Hill, New York, (1993).
Y. Cheng, F. K. Hwang, I. F. Akyidliz and D. F. Hsu, Routing algorithms for double loop networks, Int. J. Found. Comput. Sci. 3 (1992) 323-331.
E. A. van Doorn, Connectivity of circulant digraphs, J. Graph Theory 10 (1986) 9-14.
M. A. Filo, M. Valerno, J. L. A. Yebra, I. Alegre and T. Lang, Optimization of double-loop structures for local networks, Proc. XIX Int. Symp. MIMI 82, Paris (1982) 37-41.
R. Gould, Graph Theory, Benjamin/Cummings, California, (1988).
F. K. Hwang, A survey on double loop networks, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 5 (1991) 141-151.
F. K. Hwang, The hamiltonian property of linear functions, Oper. Res. Lett 6 (1987) no.3, 125-127.
F. K. Hwang and W.-C. W. Li, Hamiltonian circuits for 2-regular interconnection networks optimization, Ed: D.Z. Du and P. Pardalos, World Scientific, River Edge, NJ.
H. Meyniel, Une condition suffisante dexistence dun circuit hamiltonien dans un graphe orientoverset J. Combin. Theory. Ser. B 14 (1973) 137-147.
D. H. Pradhan, Fault-tolerant multiprocessor and VLSI based systems communication architecture, Fault Tolerant Computing, Theory and Technigues}, Vol II, (D. H. Pradhan ed.), Prentice-Hall, Englewood Cliffs, New Jersey (1986).
C. S. Raghavendra and J. A. Sylverster, A survey of multi-connected loop topologies for local computer networks, Comput. Netw. ISDN Syst. 11 (1986) 29-42.
T.-Y. Sung, C.-Y. Lin, Y.-C. Chuang and L.-H. Hsu, Fault tolerant token ring embedding in double-loop networks, Inform. Lett. 66 (1998) 201-207.
C. K. Wong and D. Coppersmith, A combinatorial problem related to multimodule memory organizations, J. ACM 21 (1974) 392-402.