系統識別號 | U0002-1907200623115800 |
---|---|
DOI | 10.6846/TKU.2006.00590 |
論文名稱(中文) | 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. |
論文全文使用權限 |
如有問題,歡迎洽詢!
圖書館數位資訊組 (02)2621-5656 轉 2487 或 來信