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


下載電子全文限經由淡江IP使用) 
系統識別號 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起公開。


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