淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-3008200515504600
中文論文名稱 可追蹤圖的探討
英文論文名稱 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.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2005-09-05公開。
  • 同意授權瀏覽/列印電子全文服務,於2005-09-05起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信