跳到主要內容

臺灣博碩士論文加值系統

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

詳目顯示

我願授權國圖
: 
twitterline
研究生:林容新
研究生(外文):Rong-Shin Lin
論文名稱:低維度Cayley圖之研究
論文名稱(外文):On Cayley graphs of degree 3
指導教授:黃華民黃華民引用關係
學位類別:碩士
校院名稱:國立中央大學
系所名稱:數學研究所
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:23
中文關鍵詞:漢米頓圈Cayley 圖
外文關鍵詞:Cayley graphHamiltonian cycle
相關次數:
  • 被引用被引用:0
  • 點閱點閱:127
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0

在[3]中,Dirac在1952年證明,只要簡單圖G中,頂點個數至少3個,頂點的維度都大於或等於頂點個數的一半,就有漢米頓圈。Chvátal-Erdös在1972年證明,簡單圖G中,頂點個數至少3個且κ(G)大於或等於 α(G),則有漢米頓圈。此兩類的圖,邊的個數都要相當多,而在邊數比較少的圖中是否有漢米頓圈則是一個難解的問題。例如:Odd graph O(n),頂點集合V為2n-1個元素集合的n-1元子集合,任二頂點A與B相鄰若且唯若A交集 B為空集合 。這種圖有 個頂點,但每點的邊數只有n條。這種圖是否是漢米頓圖就是很難的問題,n=3是Petersen圖,沒有漢米頓圈,但n大於或等於 4時是有名的Kneser 猜想:假設n>3,則O(n) 是漢米頓圖。這個問題大部分的情況到現在仍未解決。
考慮最極端的例子,我們想要檢查一些3-正則圖是否有漢米頓圈。根據Cayley圖是漢米頓圖的猜想,我們有興趣去知道3-正則Cayley圖是否有漢米頓圈。然而要去分析所有的3-正則Cayley圖是一件難事,特別是缺乏邊對稱的圖[8]。本論文將探討下列特殊的3-正則類:1.圈化圖(Cycle connected graph)。2.SEP(n)。


We wnat to check some 3-regular graphs has Hamiltonian cycle.According to the conjucture:Cayley graphs are Hamiltonian cycle,we want to know 3-regular Cayley graphs has Hamiltonian cycle.But it is hard to anlysis all 3-regular Cayley graphs.In this paper,we discuss some specal 3-regular graphs: Cycle connected graph and SEP(n).


目錄 ……………………一
圖形的目錄 ……………二
前言 ………………………………………………… 1
第一章 基本定義 …………………………………… 2
第二章 Cayley 圖 及 圈 化 圖 …………… 4
第三章 漢 米 頓 圈 的 問 題 …………………… 13
第四章 K-覆 蓋 連 通 …………………………… 19
第五章 討 論 ……………………………………… 22
參考文獻 …………………………………………… 23


[1] Bette Bultena and Frank Ruskey,“Transition Restricted Gray Codes”, the Electronic Journal of Combinatorics:Volume 3,Paper R11.March 14,1996[2] Chang-Hsing Tsai, Jimmy J. M. Tan, Tyne Liang, and Lih-Hsing Hsu,” Fault — Tolerant Hamiltonian Laceablility of Hypercubes,”preprint.[3] Douglas B. West, “Introduction to Graph Theory” Second edition: Prentice Hall 2001[4] Friedhelm Meyer auf der Heide and Berthold VÖcking ,” Short paths routing in arbitrary networks”, Journal of Algorithms, Vol. 31, No. 1, pp. 105-131, 1999.[5] G. A. Miller, Blichfeldt and Dickson ,” Theory and Applications of Finite Groups “, John Wiley and sons,Inc.,1916,reprinted Dover 1961[6] G.Simmons,”Almost all n-dimensional rectangular lattices are Hamiltonian laceable”,Congressus Numerantium 21,1978,pp.103-108.[7] Harry Dweighter,” Problem E2569”,American Mathematical Monthly,82 (1975) 1010.[8] H.S.M. Coxeter, “Zero-Symmetric Graphs Trivalent Graphical Regular Representations of Groups.” Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London (1981)[9] K. Menger, “Zur allgemeinen Kurventheroie”, Fund. Math., 10, 1927, 95-115[10] Leighton,F.T., “Introduction to Parallel Algorithms and Architectures : Arrays,Trees,Hypercubes.” ,Morgan Kaufmann Publishers, Inc.,(1992)[11] Marie-Claude Heydemann and Bertrand Ducourthial, “Cayley Graphs And Interconnection Networks” in Graph Symmetry, Algebraic Methods and Applications, "NATO ASI C", vol. 497 , p 167-226, 1997.[12] Michael Albert, R. E. L. Aldred and Derek Holton,”On 3*-connected graphs”preprint.[13] S.B. Akers and B. Krishnamurthy, “A Group Theoretic Model for Symmetric Interconnection Networks”, IEEE Transaction on Computer, Vol. c-38, No. 4, April 1989, pp. 555-566[14] Shahram. Latifi,Pradip K,Srimani,”SEP:A Fixed Degree Regular Network for Msaaively Parallel Systems.” preprint. [15] Shahram Latifi and Pradip Srimani,” A New Fixed Degree Regular Network for Parallel Processing,” Proceedings of Eighth IEEE Symposium on Parallel and Distributed Processing, October 1996.[16] Preparata, F. P. and Vuillemin, J. : “The Cube-Connected Cycle : A VersatileNetwork for Parallel Computation.” Communication of ACM Vol.24 No5,1987,p300-309[17] 林政寬,n階置換Cayley圖之研究, 中央大學數學研究所碩士論文,preprint.[18] 徐嘉陽, 特殊Cayley 圖的寬距, 中央大學數學研究所碩士論文(1994)[19] 雷偉明, Cayley 圖的直徑與寬直徑的研究, 中央大學數學研究所碩士論文(1996) 23

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top