系統識別號 | U0002-3008200515504600 |
---|---|
DOI | 10.6846/TKU.2005.00783 |
論文名稱(中文) | 可追蹤圖的探討 |
論文名稱(英文) | The study of traceable graphs |
第三語言論文名稱 | |
校院名稱 | 淡江大學 |
系所名稱(中文) | 數學學系碩士班 |
系所名稱(英文) | Department of Mathematics |
外國學位學校名稱 | |
外國學位學院名稱 | |
外國學位研究所名稱 | |
學年度 | 93 |
學期 | 2 |
出版年 | 94 |
研究生(中文) | 林欣誼 |
研究生(英文) | Hsin-I Lin |
學號 | 692150179 |
學位類別 | 碩士 |
語言別 | 繁體中文 |
第二語言別 | |
口試日期 | 2005-06-03 |
論文頁數 | 35頁 |
口試委員 |
指導教授
-
高金美
委員 - 江南波 委員 - 周兆智 |
關鍵字(中) |
可追蹤圖 全部可追蹤圖 |
關鍵字(英) |
traceable graphs totally traceable graphs |
第三語言關鍵字 | |
學科別分類 | |
中文摘要 |
在本論文中,我們討論全部可追蹤圖的性質,並獲得利用米希爾斯基建構法建構出的圖M(G)中,只要圖G是一個迴圈或是漢米爾頓圖,則圖M(G)就會是一個是全部可追蹤的圖。 接著,我們定義了π(G)為圖G中,可追蹤的邊數佔所有邊數的比例,即當G有b個邊,其中a個邊為可追蹤邊的個數,則π(G)=a/b。並獲得下面的結果: (1) 任給兩個正整數a, b,只要 a≦b≦[(a2 +4)/4],則存在一個邊數為b的圖G中含有a個可追蹤的邊,即π(G)=a/b。 (2) 任給正整數n,則對於所有介於n – 1和1+(n – 1)2/4 之間的整數b,存在一個點數為n,邊數為b的圖G,使得π(G)=(n – 1)/b。 (3) 任給大於等於5的正整數n,則對於所有介於 和(n2–5n+14)/2之間的整數b,存在一個點數為n,邊數為b的圖G,使得π(G)=(b – 1)/b。 |
英文摘要 |
In this thesis, we discuss the properties of a totally traceable graph, and using Mycielski’s construction to construct a sequence of totally traceable graphs M(G) as G is a Hamiltonian graph. Next, we define π(G) to be the ratio of traceable edges and total edges of G. That is if G has b edges which contains a traceable edges, then π(G) = a/b. We obtains the following results: (1) Given any two positive integers a, b and a≦b≦[(a2 +4)/4], then there is a graph G with b edges such that π(G) = a/b. (2) Given any positive integer n, then there is a graph G with n vertices and b edges such that π(G) = (n – 1)/b, for each b, n–1≦b≦1+(n – 1)2/4. (3) Given any positive integer n, then there is a graph G with n vertices and b edges such that π(G) = (b – 1)/b, for each b, ≦b≦(n2–5n+14)/2. |
第三語言摘要 | |
論文目次 |
第一章 緒論………………………………………………..1 第二章 預備知識…………………………………………..3 第三章 全部可追蹤圖……………………………………..6 第四章 米希爾斯基圖的特性…………………………….12 第五章 不是全部可追蹤圖…………………………….....17 參考文獻……………………………………………………...35 |
參考文獻 |
〔1〕 K. T. Balinska, M. L. Gargano and L.V. Quintas, An Edge Partition Problem Concerning Hamilton Paths, Congressus Numerantium, 152(2001), 45-54. 〔2〕 R. Balakrishman and K. Ranganathan, Graph Theory, Springer (2000). 〔3〕 G. Chartrand and L. Lesniak, Graphs and Digraphs, 3rd Edition, Chapman and Hall (1996). 〔4〕 R.J. Faudree and R.J. Gould, Characterizing forbidden pairs for Hamiltonian properties, Discrete Math. 173,45-60(1997). 〔5〕 A. Gibbons, Algorithmic Graph Theory, Cambridge University Press(1989). 〔6〕 L.V. Quintas, Edge partitions and Hamilton paths, Presented at Mathematics and Computer Science Seminar, Pace University,October 10,2000. 〔7〕 R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford University Press, 1998. 〔8〕 G. Sargsyan, A theorem on Hamilton paths, Presented at Mathematics and Computer Science Seminar, Pace Uniersity, October 10, 2000. 〔9〕 Douglas B. West, Introduction to Graph Theory 2nd Ed. Prenfice Hall, Inc. 2001. |
論文全文使用權限 |
如有問題,歡迎洽詢!
圖書館數位資訊組 (02)2621-5656 轉 2487 或 來信