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


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-2006200803004500
中文論文名稱 完全圖分割成4-迴圈太陽圖之探討
英文論文名稱 The decomposition of complete graphs into sun graphs of 4-cycle
校院名稱 淡江大學
系所名稱(中) 數學學系碩士班
系所名稱(英) Department of Mathematics
學年度 96
學期 2
出版年 97
研究生中文姓名 邱群博
研究生英文姓名 Cyun-Bo Ciou
學號 695190206
學位類別 碩士
語文別 中文
口試日期 2008-06-06
論文頁數 33頁
口試委員 指導教授-高金美
委員-高金美
委員-江南波
委員-黃文中
中文關鍵字 完全二分圖  完全圖  4-迴圈  太陽圖  分解 
英文關鍵字 complete bipartite graph  complete graph  4-cycle  sun graph  decomposition 
學科別分類 學科別自然科學數學
中文摘要 當一個含有n個點的圖中,任兩點都有邊相連,我們稱此圖為完全圖,記為K_(n)。當一個圖中的點集合可以分成兩個非空的集合V_(1)及V_(2),若 V_(1)中的每一點都與V_(2)中的點有邊相連,且在V_(1)及V_(2)中的點都沒有邊相連,則稱此圖為完全二分圖;若 V_(1)中有m個點,V_(2)中有n個點,則此完全二分圖記為K_(m,n)。假設 v_(1), v_(2), v_(3), v_(4)為4-迴圈C_(4)的依序四個頂點,在 C_(4)外面加入4個點w_(1), w_(2), w_(3), w_(4)及4條邊 {v_(i), w_(i) }, 1≦ i≦ 4,所形成的圖稱為C_(4)的太陽圖,記為S(C_(4))。在本篇論文中,我們證明了
(1) 當m≧ n≧ 4, n≠ 5, 且若n= 4則m不為4k+2形態時,完全二分圖K_(m,n)能分割成4-迴圈太陽圖的充分必要條件為m×n為8的倍數,(2) 完全圖K_(n)能分割成4-迴圈太陽圖的充分必要條件為n≡ 0 或1 (mod 16)。
英文摘要 A graph with n vertices satisfies that every two vertices are connected by an edge, then we call this graph a complete graph with n vertices, denoted by K_(n). If the vertex set of a graph can be partitioned into two disjoint nonempty sets V_(1) and V_(2) , every vertex in V_(1) connects every vertex in V_(2) and there is no edge in V_(1) and V_(2), then we call this graph is a complete bipartite graph. If V_(1) contains m elements and V_(2) contains n elements, then we denote this complete bipartite graph K_(m,n). Let {v_(1), v_(2), v_(3), v_(4)} be the vertex set of a 4-cycle C_(4). If we add another four vertices w_(1), w_(2), w_(3), w_(4) and four edges {v_(i), w_(i)}, 1≦ i≦ 4 to C_(4), then we call this graph a sun graph of C_(4), denoted by S(C_(4)). In this thesis, we proved that
(1) if m≧ n≧ 4, n≠ 5, and if n= 4 then m is not the form of 4k+2, the complete bipartite graph K_(n,m) can be decomposed into sun graphs of 4-cycle (S(C_(4))) if and only if mn is a multiple of 8, and
(2) the complete graph K_(n) can be decomposed into sun graphs of 4-cycle (S(C_(4))) if and only if n≡ 0, 1 (mod 16).
論文目次 目錄
第一章 簡介..............................................................................................1
第二章 預備知識......................................................................................3
第三章 主要結果....................................................................................12
第一節 Km,n可分割成S(C4)................................................................12
第二節 Kn可分割成S(C4)..................................................................24
第三節 Kn可循環分割成S(C4)..........................................................30
參考文獻..................................................................................................33

圖表目錄
圖2.1..........................................................................................................3
圖2.2..........................................................................................................4
圖2.3..........................................................................................................4
圖2.4..........................................................................................................5
圖2.5..........................................................................................................6
圖2.6..........................................................................................................7
圖2.7..........................................................................................................7
圖2.8..........................................................................................................8
圖2.9..........................................................................................................9
圖2.10.......................................................................................................10
圖2.11.......................................................................................................11
圖3.1.........................................................................................................13
圖3.2.........................................................................................................14
圖3.3.........................................................................................................16
圖3.4.........................................................................................................18
圖3.5.........................................................................................................21
圖3.6.........................................................................................................25
圖3.7.........................................................................................................26
圖3.8.........................................................................................................27
圖3.9.........................................................................................................28
圖3.10.......................................................................................................30
圖3.11.......................................................................................................31
圖3.12.......................................................................................................32
參考文獻 參考文獻
[1] B. Alspach and H. Gavlas, Cycle decompositions of Kn and Kn – I, J. Combin. Theory Ser. B., 81, no.1,(2001), 77-99.
[2] E. J. Billington, D.G. Hoffman, Decomposition of complete tripartite graphs into gregarious 4-cycles. Discrete Math, 261(2003)87-111.
[3] F. Buckley, M. Lewinter, A friendly introduction to graph theory. Prentice Hall, 2003.
[4] M. Buratti, A. Del Fra, Existence of cyclic k-cycle system of the complete graph. Discrete Math, 261(2003)113-125.
[5] Wei-Hung Lee, Decompose complete tripartite graph into asteroidal graph. Tamkang University, 2007.
[6] D. B. West, Introduction to graph theory 2nd Ed. Prenfice Hall, 1996, 2001.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2008-07-22公開。
  • 同意授權瀏覽/列印電子全文服務,於2008-07-22起公開。


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