系統識別號 | U0002-0307201019581200 |
---|---|
DOI | 10.6846/TKU.2010.00053 |
論文名稱(中文) | 完全圖分割成4-迴圈或漢米爾頓迴圈之探討 |
論文名稱(英文) | Decomposition of complete graph into 4-cycles or Hamilton cycles |
第三語言論文名稱 | |
校院名稱 | 淡江大學 |
系所名稱(中文) | 數學學系碩士班 |
系所名稱(英文) | Department of Mathematics |
外國學位學校名稱 | |
外國學位學院名稱 | |
外國學位研究所名稱 | |
學年度 | 98 |
學期 | 2 |
出版年 | 99 |
研究生(中文) | 何婉嫙 |
研究生(英文) | Wan-Hsuan Ho |
學號 | 697190022 |
學位類別 | 碩士 |
語言別 | 繁體中文 |
第二語言別 | |
口試日期 | 2010-06-18 |
論文頁數 | 33頁 |
口試委員 |
指導教授
-
高金美
委員 - 傅恆霖 委員 - 潘志實 |
關鍵字(中) |
圖 完全圖 分割 迴圈 漢米爾頓迴圈 |
關鍵字(英) |
graph complete graph decomposition cycle Hamilton cycle |
第三語言關鍵字 | |
學科別分類 | |
中文摘要 |
當一個含有 n 個點的簡單圖中,任意兩點皆有邊相連,則稱此圖為完全圖,記為 K_n;當一個含有 n 個點的連通圖,若其每一個點的度數皆為 2,則稱此圖為 n-迴圈,記為 C_n。 若一個完全圖 K_n可分割成4-迴圈或 n-迴圈是指 K_n中的邊可分割成一些邊均相異的4-迴圈或 n-迴圈,且這些迴圈之邊的聯集即為 K_n中的邊集合。 在本篇論文中,我們證明了: (1) 當 n 為奇數且 n≥3 時,設 α,β 為正整數或零,若 4α+βn=(n(n-1))/2 ,則 K_n 可以分割成 α 個4-迴圈以及 β 個漢米爾頓迴圈。 (2) 當 n 為偶數且 n≥4 時,設 α,β 為正整數或零,若 4α+βn=(n(n-2))/2 ,則 K_n-I 可以分割成 α 個4-迴圈以及 β 個漢米爾頓迴圈,其中 I 為 K_n 的一個1-因子。 |
英文摘要 |
A complete graph with n vertices is a simple graph in which every pair of distinct vertices is connected by a unique edge, denoted by K_n. The cycle is a connected graph with n vertices which all vertices are degree 2 and denoted by C_n. A complete graph K_n can be decomposed into 4-cycles and n-cycles if K_n can be partitioned into edge-disjoint 4-cycles and n-cycles such that the union of edge sets of these cycles is the edge set of K_n. In this thesis, we prove that: (1) For odd integer n, n≥3, if there exists nonnegative integers α and β such that 4α+βn=(n(n-1))/2 , then K_n can be decomposed into α 4-cycles and β n-cycles. (2) For even integer n, n≥4, if there exists nonnegative integers α and β such that 4α+βn=(n(n-2))/2 , then K_n-I can be decomposed into α 4-cycles and β n-cycles, where I is a 1-factor of K_n. |
第三語言摘要 | |
論文目次 |
第一章 簡介 1 第二章 預備知識 3 第三章 K_n 分割成 C_4 或 C_n 13 第四章 K_n-I 分割成 C_4 或 C_n 26 參 考 文 獻 32 圖 目 錄 圖2.1 3 圖2.2 3 圖2.3 4 圖2.4 4 圖2.5 5 圖2.6 5 圖2.7 6 圖2.8 6 圖2.9 7 圖2.10 8 圖2.11 9 圖2.12 9 圖2.13 10 圖2.14 10 圖2.15 11 圖2.16 11 圖3.1 14 圖3.2 15 圖3.3 16 圖3.4 16 圖3.5 17 圖3.6 17 圖3.7 19 圖3.8 20 圖3.9 22 圖3.10 24 圖4.1 29 |
參考文獻 |
[1] P. Adams, D. Bryant and A. Khodar, 3,5-cycles decompositions, J.Combin. Des. 6 (1998) , 91-110. [2] B. Alspach, Research Problem 3, Discrete Math. 36 (1981), 333. [3] B. Alspach and H. Gavlas, Cycle decompositions of K_n and K_n-I, J. Combin. Theory Ser. B 81 (2001), 77-99. [4] P. Balister, Packing Circuits into K_n, Combin. Probab. Comput. 10 (2001), 463-499. [5] P. Balister, On the Alspach Conjectrue, Combin. Probab. Comput. 10 (2001), 95-125. [6] J.-C. Bermond, O. Favaron, and M. Matheo, Hamiltonian decomposition of Cayley graphs of degree 4, J. Combin. Theory Ser. B 46 (1989), 142-153. [7] D. Bryant, Cycle decompositions of complete graphs, Surveys in Cambridge, 2007, London Math. Soc. Lecture Note Ser. , 346, Univ. Press, Cambridge, 2007, 67-97. [8] D. Bryant and B. Maenhaut, Decompositions of complete graphs into triangles and Hamilton cycles, J. Combin. Des. 12 (2004), 221-232. [9] H. L. Fu and K. C. Hung, The Hamilton-Waterloo problem for two even cycle factors, Taiwanese Journal of Mathematics Vol. 12, No. 4, 933-940. [10] H. L. Fu, C. A. Rodger, Four-cycle systems with two regular leaves, Graphs and Combinatorics, 17 (2001), 457–461. [11] K. Heinrich, P. Horak and A. Rosa, On Alspach’s conjecture, Discrete Math. 77 (1989), 97-121. [12] A. Rosa, Alspach’s conjecture is true for n≤10, Mathematical Reports, McMaster University. [13] M. Šajna, Cycle Decompositions III: Complete graphs and fixed length cycles. J. Combin. Des. 10 (2002), 27-78. |
論文全文使用權限 |
如有問題,歡迎洽詢!
圖書館數位資訊組 (02)2621-5656 轉 2487 或 來信