n 階置換Cayley 圖之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：19

、訪客IP：3.17.150.163

姓名

林政寬(Cheng-Kuan Lin) 查詢紙本館藏

畢業系所

數學系

論文名稱

n 階置換Cayley 圖之研究

相關論文

★ 低維度Cayley圖之研究	★ 超立方體與其變形的覆蓋容器
★ 路徑與圈嵌入有缺損的超立方體	★ 樹圖最大特徵值的討論
★ On the Spectrum of Trees

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

一個有漢米頓圈的圖，代表圖中任意兩點都有一對內點互斥且通過所有頂點的路徑。
根據Menger′s 定理，在n連通圖中，任意的兩點p, q之間存在著n條內點互斥的路徑。若此n條內點互斥的路徑包含著圖中所有的頂點，則稱p, q是n覆蓋連通。
本論文將以n規則Cayley圖為例來討論覆蓋連通性及其相關特性。

關鍵字(中)

★ Cayley

關鍵字(英)

論文目次

表次 ..................... 2
圖次 ................... 3
摘要 .............................. 4
前言 ........................... 5
第一章基本定義 ..... 6
1.1 基本定義
1.2 Cayley圖
1.3 立方圖
1.4 Transposition Tree圖
1.5 Pancake圖
第二章有遞迴結構Cayley圖上的漢米頓相關性質 .................. 16
2.1 漢米頓連接
2.2漢米頓圈
第三章 k-覆蓋連通性質 .............. 24
3.1 Pancake圖的k-覆蓋連通性質
3.2 立方圖的k-偶覆蓋連通性質
3.3 星圖的k-偶覆蓋連通性質
3.4 泡沫圖的k-偶覆蓋連通性質
附錄........................ 60
參考文獻................ 69

參考文獻

[1] S.B. Akers and B. Krishnamurthy, A Group Treoretic Model dor Symmectric Interconnection Networks, IEEE Transaction on Computer, Vol. c-38, No. 4, April 1989, pp. 555-566.
[2] Friedhelm Meyer auf der Heide and Berthold VÖcking , Short paths routing in arbitrary networks, (1998), 12-13.
[3] Ore, Hamiltonian connected graphs, J. Math. Pures. Appl. 55, (1961), 315-321.
[4] Marissa P. Justan, Computer Verification of the Diameter of the n-dimensional Pancake Network.
[5] Douglas B. West, Introduction to Graph Theory, Prentice Hall, 1996.
[6] K. Menger, Zur allgemeinen Kurventheroie, Fund. Math., 10, 1927, 95-115.
[7] Michael Albert, R. E. L. Aldred and Derek Holton, On 3*-connected graphs, Australasian Journal of Combinatorics, 24(2001), 193-207.
[8] 雷偉明, Cayley 圖的直徑與寬直徑的研究, 中央大學數學研究所碩士論文, 1996.
[9] 徐嘉陽, 特殊Cayley 圖的寬距, 中央大學數學研究所碩士論文, 1994.
[10] Chun-Nan Hung, Hong-Chun Hsu, Kao-Yung Liang, and Lih-Hing Hsu, Rong Embedding in Faulty Pancake Graph.
[11] Chang-Hsing Tsai, Jimmy J.M. Tan, Tyne Liang, and Lih-Hsing Hsu, Fault – Tolerant Hamiltonian Laceablility of Hypercubes.
[12] Tseng-Kuei Li, Jimmy J. M. Tan, and Lih-Hsing Hsu, Hamiltonian lacebiblity on edge fault star graph.
[13] Mohammad H. Heydari, and I. Hal Sudborough, On the Diameter of the Pancake Network, Journal of Algorithms, 25 (1997), 67-94.
[14] D. S. Cohen, and M. Blum, Improved bounds for sroting pancakes under a conjucture, Manuscript, Computer Secience Division, University of California, Berkeley, 1992.
[15] M. R. Carey, D. S. Johnson, and S. Lin, Amer. Math. Monthly 84 (1977), 296.
[16] W. H. Gates, and C. H. Papadimitriou, Bounds for sorting by prefix reversal, Discrete Math. 27 (1979), 47-57.
[17] F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan Kaufmann, San Mateo, CA, 1992.
[18] H. Dweighter, Amer. Math. Monthly 89 (1975), 1010.
[19] S. Lakshmivarahan, J. Jwo, and S. K. Dhall, Symmetry in interconnection networks based on Cayley graphs of permutation groups: a survey, Parallel Comput., 19:361-407, 1993.
[20] Thomas W. Hungerfore, Abstract Algebra, Saunders College Publishing, 1997.
[21] F. Harary and M. Lewinter, Hypercubes and other recursively defined hamilton laceable graphs, Congressus Numerantium 60, 1987, pp. 81-84.
[22] S. Y. Hsieh, G. H. Chen and C. W. Ho, Hamiltonian-laceability of star graphs, NETWORKS, vol. 36,2000, pp. 225-232.
[23] Dirac G. A., Some theorems on abstract graphs, Proc. Lobs. Math. Soc. 2, 1952, 69-81.
[24] H. Bass, J. F. C. Kingman, F. Smithies, J.A. Todd,and C. T. C. Wall, Algebraic Graph Theory, Norman Biggs, (1974).
[25] G. Simmons, Alomost all n-dimensional rectangular lattices are Hamiltonian laceable, Congressus Numerantiun 21, 1978, pp. 103-108.

指導教授

黃華民(Hua-Min Huang)

審核日期

2002-7-18

推文