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


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-1907200623115800
中文論文名稱 K2n,2n-C4n 分割成長度為2k之迴圈的探討
英文論文名稱 The study of decomposing K2n,2n-C4n into cycles of length 2k
校院名稱 淡江大學
系所名稱(中) 數學學系碩士班
系所名稱(英) Department of Mathematics
學年度 94
學期 2
出版年 95
研究生中文姓名 陳怡君
研究生英文姓名 Yi-Chun Chen
學號 693150293
學位類別 碩士
語文別 中文
口試日期 2006-06-16
論文頁數 48頁
口試委員 指導教授-高金美
委員-傅恆霖
委員-高金美
委員-黃文中
中文關鍵字 完全二分圖  迴圈  分割 
英文關鍵字 complete bipartite graph  cycle  decomposition 
學科別分類 學科別自然科學數學
中文摘要 在這篇論文中,我們主要是探討一個完全二分圖扣除一個最大迴圈後是否仍可分割成C2k。
我們先證明了K2n,2n-C4n可以完全被分割成C2k,k=2,3,4,5,只要n≧k。進而證得,若k為偶數時,只要n≡1(mod k),K2n,2n-C4n都可分割成C2k。
接著,我們討論在K2n+1,2n+1中的圈分割,為使圖中點的度數為偶數,我們由K2n+1,2n+1中扣除一個最大迴圈及一因子的聯集G2n+1,我們先證明了K2n+1,2n+1-G2n+1可以完全被分割成C2k,k=2,3,4,5,只要n≧k。進而證得,若 k 為偶數時,只要n≡1(mod k),K2n+1,2n+1-G2n+1都可分割成C2k。
英文摘要 In this thesis, we try to decompose a graph which is a complete bipartite graph taking away a Hamiltonian cycle into cycles of length 2k.
First, we show that K2n,2n-C4n can be decomposed into C2k, k=2, 3, 4, 5, for all n≧k. Then we extend the results to all even k, if n≡1(mod k), K2n,2n-C4n can be decomposed into C2k.
After that, we consider the decomposition of K2n+1,2n+1-G2n+1, where G2n+1 is the union of C4n+2 and a 1-factor of K2n+1,2n+1, can be decomposed into C2k as k=2, 3, 4, 5, for all n≧k. Then we extend the results to all even k, if n≡1(mod k), K2n+1,2n+1-G2n+1 can be decomposed into C2k.
論文目次 第一章 簡介.......................................................................1
第二章 預備知識.................................................................3
第三章 K2n,2n-C4n分割成長度為2k之迴圈..........................7
第四章 K2n+1,2n+1-G2n+1分割成長度為2k之迴圈.............27
參考文獻..........................................................................47
圖2.1、2.2.........................................................................4
圖2.3、2.4、2.5、2.6..........................................................5
圖3.1.................................................................................7
圖3.2、3.3、3.4、3.5、3.6..................................................8
圖3.7...............................................................................10
圖3.8...............................................................................11
圖3.9、3.10......................................................................12
圖3.11..............................................................................13
圖3.12..............................................................................14
圖3.13..............................................................................15
圖3.14、3.15....................................................................16
圖3.16..............................................................................17
圖3.17、3.18....................................................................18
圖3.19..............................................................................19
圖3.20..............................................................................20
圖3.21..............................................................................21
圖3.22..............................................................................22
圖3.23、3.24....................................................................23
圖3.25..............................................................................24
圖3.26..............................................................................26
圖4.1................................................................................27
圖4.2、4.3........................................................................28
圖4.4................................................................................29
圖4.5................................................................................30
圖4.6................................................................................31
圖4.7................................................................................32
圖4.8、4.9........................................................................33
圖4.10..............................................................................35
圖4.11..............................................................................36
圖4.12..............................................................................37
圖4.13..............................................................................38
圖4.14..............................................................................39
圖4.15..............................................................................40
圖4.16..............................................................................41
圖4.17..............................................................................42
圖4.18..............................................................................44
圖4.19..............................................................................46
參考文獻 [1] P. Adams, D. E. Bryant, and A. Khodkar, (1998) (3,5)-cycle decompositions, J. Combin. Designs 6, 91-110.
[2] B. Alspach, (1981) Research problem 3, Discrete Math. 36, 333-334.
[3] B. Alspach and H.Gavlas, (2001) Cycle decompositions of Kn and Kn-I, submitted to J. Combin. Theory Ser. B 81, no. 1, 77-99.
[4] B. Alspach and S. Marshall, (1994) Even cycle decompositions of complete graphs minus a 1-factor, J. Combin. Designs 2, 441-458.
[5] D. E. Bryant, A. Khodkar and H. L. Fu, (m,n)-cycle systems. J. Statist. Planning ang Inference, to appear, 74, 1998, pp365-370.
[6] C. C. Chou, C. M. Fu, and W. C. Huang, (2000) Decomposition of 2Km,n into short cycles, Util. Math. 58, pp. 3-10.
[7] C. M. Fu and W. C. Huang, (1998) Decompositions of Km,n into 4-cycles and 8-cycles, Tamkang J. of Math. Vol. 29, No. 1, 69-72.
[8] R. Haggkvist, (1985) A lemma on cycle decomposition, Ann. Discrete Math. 27, 227-232.
[9] K. Heinrich, P. Horak and A. Rosa, (1989) On Alspach’s conjecture. Discrete Math. 77, 97-121.
[10] Y. S. Huang, The study of decomposing K2m,2n and K2m+1,2n+1F into cycles of length 4 or 2t, 碩士論文, 2003.
[11] Yuan-Lung Lin, The study of decompositions of K2m,2n into 4-cycles, 6-cycles, 8-cycles, or 10-cycles, 碩士論文, 2005.
[12] A. Rosa, Alspach’s conjecture is true for n≦10 , Mathematical reports, McMaster University.
[13] D. Sotteau, (1981) Decomposition of Km,n (K*m,n) into cycles (circuit) of length , J. Combin. Theory Ser. B, 30, 75-81.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2006-08-02公開。
  • 同意授權瀏覽/列印電子全文服務,於2006-08-02起公開。


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