跳到主要內容

臺灣博碩士論文加值系統

(52.203.18.65) 您好!臺灣時間:2022/01/19 15:01
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:林政寬
研究生(外文):Cheng-Kuan Lin
論文名稱:n階置換Cayley圖之研究
指導教授:黃華民黃華民引用關係
指導教授(外文):Hua-Min Huang
學位類別:碩士
校院名稱:國立中央大學
系所名稱:數學研究所
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:87
中文關鍵詞:Cayley
相關次數:
  • 被引用被引用:0
  • 點閱點閱:147
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
一個有漢米頓圈的圖,代表圖中任意兩點都有一對內點互斥且通過所有頂點的路徑。
根據Menger′s 定理,在n連通圖中,任意的兩點p, q之間存在著n條內點互斥的路徑。若此n條內點互斥的路徑包含著圖中所有的頂點,則稱p, q是n覆蓋連通。
本論文將以n規則Cayley圖為例來討論覆蓋連通性及其相關特性。
表次 ..................... 2
圖次 ................... 3
摘要 .............................. 4
前言 ........................... 5
第一章基本定義 ..... 6
1.1基本定義
1.2Cayley圖
1.3立方圖
1.4Transposition Tree圖
1.5Pancake圖
第二章 有遞迴結構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.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top