一個具有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.