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


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-0307201019581200
中文論文名稱 完全圖分割成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.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2011-08-02公開。
  • 同意授權瀏覽/列印電子全文服務,於2011-08-02起公開。


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