 |
| 系統識別號 |
U0002-2107201019364500 |
| 中文論文名稱
|
二重完全圖分割成3-太陽圖的探討 |
| 英文論文名稱
|
The study of 3-sun decomposition of 2-fold complete graphs |
| 校院名稱 |
淡江大學 |
| 系所名稱(中) |
數學學系碩士班 |
| 系所名稱(英) |
Department of Mathematics |
| 學年度 |
98 |
| 學期 |
2 |
| 出版年 |
99 |
| 研究生中文姓名 |
鄭至程 |
| 研究生英文姓名 |
zheng-zhi cheng |
| 學號 |
697190212 |
| 學位類別 |
碩士 |
| 語文別 |
中文 |
| 口試日期 |
2010-06-18 |
| 論文頁數 |
51頁 |
| 口試委員 |
指導教授-高金美
委員-傅恆霖
委員-張薰文
|
| 中文關鍵字 |
二重完全圖
3-太陽圖
分割
|
| 英文關鍵字 |
2-fold complete graph
3-sun graph
decompoition
|
| 學科別分類 |
學科別＞自然科學＞數學
|
| 中文摘要 |
當一個含有n個點的圖中，任兩個點都有邊相連，我們稱此圖為n點的完全圖，記為Kn。若任兩個點都有兩個邊相連，我們稱此圖為n點的二重完全圖，記為2Kn。假設Cn = (v1, v2, v3, ..., vn)，在Cn外面加入n個點w1, w2,w3, ..., wn及n條邊{vi, wi}, 1≦i≦n，所形成的圖稱為Cn的太陽圖，記為S(Cn)。設G為一個簡單圖，且G1, G2, G3, ..., Gt為G的子圖，若滿足下列條件：
(1) E(G1)∪E(G2)∪E(G3)∪...∪E(Gt) = E(G)
(2)對於1≦i, j≦t, i不等於j,E(Gi)∩E(Gj) = Ø
則稱G可分割成G1, G2, G3, ..., Gt。若G1, G2, G3, ..., Gt均與圖H同構，則稱G可分割成圖H。
在此論文中，我們證明了：
(1)當n ≡ 1 or 3 (mod 6)時，2Kn可分割成循環3-太陽圖。
(2)當n ≡ 0 or 4 (mod 6)時，2Kn可分割成1-旋轉3太陽圖。
|
| 英文摘要 |
A graph with n vertices such that every two vertices are joined by an edge is called a complete graph with n vertices, denoted by Kn. If every two vertices are joined by two edges, then we call this graph a 2-fold complete graph with n vertices, denoted by 2Kn. Let (v1, v2, v3, ..., vn) be an n-cycle Cn. If we add another n vertices w1, w2, w3, ..., wn and n edges {vi, wi}, 1≦i≦n, then we call this graph an n-sun graph,denoted by S(Cn). Let G be a simple graph and G1, G2, G3, ..., Gt be subgraphs of G. If G1, G2, G3, ..., Gt satisfy the following conditions：
(1) E(G1)∪E(G2)∪E(G3)∪...∪E(Gt) = E(G)
(2) 1≦i, j≦t, i is not j,E(Gi)∩E(Gj) = Ø
Then we call G be decomposed into G1, G2, G3, ..., Gt. If G1, G2, G3, ..., Gt are isomorphic to H, then we call G can decomposed into H.
In this thesis, we have the following results.
(1) n ≡ 1 or 3 (mod 6), 2Kn can be decomposed into cyclic 3-sun graphs.
(2) n ≡ 0 or 4 (mod 6), 2Kn can be decomposed into 1-rotational 3-sun graphs.
|
| 論文目次 |
第一章 簡介................................................................................................1
第二章 預備知識..........................................................................................3
第三章 2Kn可分割成循環或1-旋轉3-太陽圖...................................................12
第一節 n ≡ 1 (mod 6)，則2Kn可分割成循環3-太陽圖.....................................13
第二節 n ≡ 0 (mod 6)，則2Kn可分割成1-旋轉3-太陽圖...................................21
第三節 n ≡ 3 (mod 6)，則2Kn可分割成循環3-太陽圖.....................................27
第四節 n ≡ 4 (mod 6)，則2Kn可分割成1-旋轉3-太陽圖...................................39
參考文獻...................................................................................................51
圖表目錄
圖2.1 P5.....................................................................................................3
圖2.2 C6 = (1,2,3,4,5,6)...............................................................................4
圖2.3 K6.....................................................................................................5
圖2.4 H為G的子圖.......................................................................................5
圖2.5 K4可分割成G1, G2.............................................................................6
圖2.6 H為G的一個1-因子..............................................................................7
圖2.7 S(C3).................................................................................................7
圖2.8 △(K4)................................................................................................8
圖2.9 3-太陽圖差序列...................................................................................8
圖2.10 G+2為圖G的一個平移........................................................................9
圖3.1 2K7的初始3-太陽圖...........................................................................14
圖3.2 2K13的初始3-太陽圖.........................................................................15
圖3.3 2K19的初始3-太陽圖.........................................................................16
圖3.4 2K37的初始3-太陽圖....................................................................17, 18
圖3.5 2K12的初始3-太陽圖.........................................................................22
圖3.6 2K18的初始3-太陽圖.........................................................................23
圖3.7 2K36的初始3-太陽圖.........................................................................25
圖3.8 2K9的初始3-太陽圖...........................................................................28
圖3.9 2K15的初始3-太陽圖.........................................................................30
圖3.10 2K21的初始3-太陽圖..................................................................31, 32
圖3.11 2K33的初始3-太陽圖........................................................................33
圖3.12 2K39的初始3-太陽圖........................................................................35
圖3.13 2K10的初始3-太陽圖........................................................................40
圖3.14 2K16的初始3-太陽圖........................................................................42
圖3.15 2K22的初始3-太陽圖........................................................................44
圖3.16 2K34的初始3-太陽圖..................................................................45, 46
圖3.17 2K40的初始3-太陽圖........................................................................48
|
| 參考文獻 |
[1] I. An (1990) Combinatorial designs construction methods, Ellis Horwood Limited.
[2] A. J. W. Hilton (1969) On Steiner and similar triple systems. Math. Scand. 24 208-216.
[3] E. S. O'Keefe (1961) Verification of a conjecture of T. Skolem. Math. Scand. 9 80-82.
[4] A. Rosa (1966) Poznamka o cyklickych Steinerovych systemoch trojic. Math. Fyz. Cas. 16 285-290.
[5] T. Skolem (1957) On certain distributions of integers in pairs with given differences. Math. Scand. 5 57-68
[6] T. Skolem (1958) Some remarks on the triple systems of Steiner. Math. Scand. 6 273-280.
[7] D. B. West (2001) Introduction to graph theory 2¬nd Ed. Prenfice Hall, Inc。
[8] Jian-Xing Yin and Bu-Sheng Gong (1990) Existence of G-designs with | V(G) | = 6. Combinatorial designs and applications (Huangshan,1988), 201-218, Lecture Notes in Pure and Appl. Math. 126, Dekker, New York.
[9] 沈灝 (2008) 組合設計理論, 第二版, 上海交通大學出版社。
|
| 論文使用權限 |
同意紙本無償授權給館內讀者為學術之目的重製使用，於2011-08-11公開。同意授權瀏覽/列印電子全文服務，於2011-08-11起公開。 |
 |
|
 |
