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