系統識別號 | U0002-1701201303370000 |
---|---|
DOI | 10.6846/TKU.2013.00559 |
論文名稱(中文) | 完全圖分割成迴圈與星圖的探討 |
論文名稱(英文) | Decomposition of complete graphs into cycles and stars |
第三語言論文名稱 | |
校院名稱 | 淡江大學 |
系所名稱(中文) | 數學學系碩士班 |
系所名稱(英文) | Department of Mathematics |
外國學位學校名稱 | |
外國學位學院名稱 | |
外國學位研究所名稱 | |
學年度 | 101 |
學期 | 1 |
出版年 | 102 |
研究生(中文) | 黃建華 |
研究生(英文) | Chien-Hua Huang |
學號 | 698190120 |
學位類別 | 碩士 |
語言別 | 繁體中文 |
第二語言別 | |
口試日期 | 2012-12-27 |
論文頁數 | 46頁 |
口試委員 |
指導教授
-
高金美(cmfu@mail.tku.edu.tw)
委員 - 黃文中 委員 - 徐泰煒 |
關鍵字(中) |
完全圖 迴圈 星圖 分割 |
關鍵字(英) |
complete graph cycle star decomposition |
第三語言關鍵字 | |
學科別分類 | |
中文摘要 |
一個具有n個點的圖中,若任意兩點皆有邊相連,我們稱此圖為n個點的完全圖,記作Kn。一個具有n個點的連通圖,其每一點的度數皆為2,我們稱此圖為n-迴圈,記作Cn。一個具有n+1個點的連通圖,其中有一點的度數為n,其餘各點的度數皆為1,我們稱此圖為星圖,記作Sn,同構於K1,n。設G為一個簡單圖,G1,G2,…,Gt為G的子圖,若滿足下列條件: (1) E(G1)∪E(G2)∪ ... ∪E(Gt) = E(G); (2) 對於1 ≦ i ≠ j ≦ t,E(Gi) ∩ E(Gj) = 空集合, 則稱G可分割為G1,G2,…,Gt,記作G = G1+ G2+ … + Gt。若H是G的子圖,且G1,G2,…,Gt都與H同構,則稱G可分割成t個H,記為G = tH。若G可分割成p個G1與q個G2,則記為G = pG1 + qG2。 在本論文中,我們證明了: (1) 當n≡0 (mod 6),Kn可分割成C3和S3的各種組合。 (2) 當n≡1 (mod 6),Kn可分割成C3和S3的各種組合。 進而得到以下定理 定理:當n≡1,3 (mod 6),n ≧ 3且p、q為非負整數。 如果Kn可分割成p個C3和q個S3, 若且唯若p + q = n(n-1)/6 且q ≠ 1,2。 |
英文摘要 |
A complete graph Kn is a graph with n vertices and there is an edge joining any two vertices. An n-cycle Cn is a connected graph with n vertices and the degree of each vertex is 2. A star graph Sn is a graph with n+1 vertices and there is a vertex of degree n, the others are degree of 1. Let G be a simple graph and G1,G2,…,Gt be subgraphs of G. If E(G1)∪E(G2)∪…∪E(Gt) = E(G) and for all 1≦ i ≠ j ≦t,E(Gi)∩E(Gj) = empty set, then we call that G can be decomposed into G1, G2, … , Gt, denoted by G = G1+ G2+ … + Gt. If G1, G2, … , Gt are isomorphic to graph H, then we call G can be decomposed into H. If G can be decomposed into p copies of G1 and q copies of G2, that G can denoted by G = pG1 + qG2. In this paper, we show that: (1) if n≡1 (mod 6), then Kn can be decomposed into C3 and S3. (2) if n≡3 (mod 6), then Kn can be decomposed into C3 and S3. Combining the above results, we obtain the following theorem: Theorem: n≡1, 3 (mod 6), n≧3. For any nonnegative integers p and q. Kn can be decomposed into p copies of C3 and q copies of S3 if and only if p + q = n(n-1)/6 and q ≠ 1, 2。 |
第三語言摘要 | |
論文目次 |
目 錄 第一章 簡介 ……………………………………………………… 01 第二章 預備知識 ………………………………………………03 第三章 Kn分割成C3和S3 ……………………………16 第一節 n≡1(mod 6) ……………………………32 第二節 n≡3(mod 6) ……………………………41 第四章 結論 ……………………………………………………… 45 參考文獻 ……………………………………………………………… 46 圖目錄 圖2.1 G ………………………………………………………………… 03 圖2.2 H為G的子圖…………………………………………………… 03 圖2.3 連通圖G1和非連通圖G2 ……………………………………04 圖2.4 deg(v)=3 ………………………………………………………… 04 圖2.5 C4 ………………………………………………………………………… 05 圖2.6 K5 ………………………………………………………………………… 05 圖2.7 K2,3 ………………………………………………………………… 06 圖2.8 S4 ………………………………………………………………………… 07 圖2.9 K5= C5+C5 = 2C5………………………………………… 08 圖2.10 G H…………………………………………………………………… 08 圖3.1 K4 = 1C3 + 1S3 ………………………………………… 17 圖3.2 M1 ………………………………………………………………………… 24 圖3.3 M1 ………………………………………………………………………… 25 圖3.4 W1 ………………………………………………………………………… 26 圖3.5 W1 = 6S3…………………………………………………………… 26 圖3.6 M2 ………………………………………………………………………… 26 圖3.7 K15 = K2 ∪ K2,13 ∪ K13 …………………… 29 圖3.8 有洞的交換擬似群的建構STS的方法……………… 31 圖3.9 G ………………………………………………………………… 32 圖3.10 G ………………………………………………………………… 33 圖3.11 對應於x1°x2=x4,x1°x3=x2所形成的圖W …35 圖3.12 G …………………………………………………………………………… 37 圖3.13 G …………………………………………………………………………… 38 圖3.14 G …………………………………………………………………………… 39 圖3.15 對應於1°3=81°5=3所形成的圖W………………… 40 表目錄 表2.1 6 階有洞的交換擬似群 …………………………………………10 表2.2 6 階有洞的交換擬似群 …………………………………………12 表2.3 8 階有洞的交換擬似群 …………………………………………13 表2.4 5 階的擬似群({1,3,5,8,9},°)………………………14 表2.5 10 階部分有洞的交換擬似群…………………………………15 表2.6 10 階有洞的交換擬似群…………………………………………15 |
參考文獻 |
[1] Alspach, B., Gavlas, H.: Cycle decompositions of Knand Kn−I, J. Comb. Theory Ser. B 81(2001), 77–99. [2]Kirkman, T. P.: On a problem in combinations, Cambridge and Dublin Math. Journal 2 (1847), 191-204. [3] Lindner, C.C. and Rodger, C.A.: Design theory, Boca Raton, Florida, CRC Press (1997). [4] Šajna, M.: Cycle decompositions III: complete graphs and fixed length cycles. J. Comb. Des. 10(2002), 27–78. [5] Shyu, T. W.: Decomposition of complete graphs into cycles and stars, Graphs and Combinatorics (2011), pp. 1-13,doi:10.1007/s00373-011-1105-3. [6] Tarsi, M.: Decomposition of complete multigraph into stars. Discrete Math. 26(1979), 273–278. [7] Yamamoto, S., Ikeda, H., Shige-ede, S., Ushio, K., Hamada, N.: On claw decomposition of complete graphs and complete bipartie graphs. Hiroshima Math. J. 5(1975), 33–42. |
論文全文使用權限 |
如有問題,歡迎洽詢!
圖書館數位資訊組 (02)2621-5656 轉 2487 或 來信