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


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-1607201006312700
中文論文名稱 完全圖分割成5-太陽圖的探討
英文論文名稱 Decomposition of complete graphs into 5-sun graphs.
校院名稱 淡江大學
系所名稱(中) 數學學系碩士班
系所名稱(英) Department of Mathematics
學年度 98
學期 2
出版年 99
研究生中文姓名 黃逸齊
研究生英文姓名 Yi-Chi Huang
學號 697190030
學位類別 碩士
語文別 中文
口試日期 2010-06-18
論文頁數 48頁
口試委員 指導教授-高金美
委員-黃文中
委員-張薰文
中文關鍵字 完全圖  5-太陽圖  分割 
英文關鍵字 complete graph  5-sun graph  decomposition 
學科別分類 學科別自然科學數學
中文摘要 一個具有n個點的圖中,若任意兩點皆有邊相連,我們稱此圖為n個點的完全圖,記作Kn。一個具有n個點的連通圖,其每一點的度數皆為2,我們稱此圖為n-迴圈,記作Cn。令C5的頂點分別為v1、v2、v3、v4和v5,並在C5外面加入5個頂點為w1、w2、w3、w4和w5及5條邊{vi,wi},1≦i≦5,則稱此圖為5-太陽圖,記作S(C5)。
設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。若G1, G2,…, Gt都與H同構,則稱G可分割成H。
在本論文中,我們證明了:
(1) 當n≡1 (mod 20)時,Kn可分割成5-太陽圖。
(2) 當n≡0 (mod 20)時,Kn可分割成5-太陽圖。
(3) 當n≡5 (mod 20)時,Kn可分割成5-太陽圖。
(4) 當n=16,36時,Kn可分割成5-太陽圖。
英文摘要 A graph with n vertices in which every pair of distinct vertices is connected by a unique edge is called a complete graph with n vertices, denoted by Kn. A graph with n vertices in which every vertex has degree 2 is called a cycle, denoted by Cn. Let {v1, v2, v3, v4, v5} be the vertex set of C5. If we add another five vertices w1, w2, w3, w4, w5 and five edges {vi, wi}, 1≦i≦5, then we call this graph a 5-sun graph, denoted by S(C5). Let G be a simple graph and G1,G2,…,Gt be subgraphs of G.
If G1,G2,…,Gt satisfy the following conditions:
(1) E(G1)∪E(G2)∪...∪E(Gt)= E(G)
(2) ∀1≦i≠j≦t,E(Gi)∩E(Gj)= Ø
, then we call G can be decomposed into G1, G2, …, Gt. If G1, G2, …, Gt are isomorphic to H, then we call G can be decomposed into H.
In this thesis, we prove that:
(1) if n≡1 (mod 20), then Kn can be decomposed into 5-sun graphs.
(2) if n≡0 (mod 20), then Kn can be decomposed into 5-sun graphs.
(3) if n≡5 (mod 20), then Kn can be decomposed into 5-sun graphs.
(4) if n=16, 36, then Kn can be decomposed into 5-sun graphs.
論文目次 目錄
第一章 簡介.................1
第二章 預備知識.............2
第三章 Kn分割成S(C5)........14
第一節 n≡1 (mod 20)......16
第二節 n≡0 (mod 20)......22
第三節 n≡5 (mod 20)......30
第四節 n=16,36............42
參考文獻....................48

圖目錄
圖2.1 H為G的子圖..............................3
圖2.2 P5......................................3
圖2.3 連通圖G1和非連通圖G2....................4
圖2.4 C5......................................5
圖2.5 K5......................................5
圖2.6 H為G的1-因子...........................6
圖2.7 S(C5)...................................6
圖2.8 K5= C5+C5..............................7
圖3.1 K21的初始S(C5)及其差集..................16
圖3.2 K41的初始S(C5)的差集....................18
圖3.3 K61的初始S(C5)的差集....................19
圖3.4 當k≧3時,K20k+1的初始S(C5)及其差集.....20
圖3.5 K20的初始S(C5)及其差集..................22
圖3.6 K40的初始S(C5)的差集....................24
圖3.7 K60的初始S(C5)的差集....................25
圖3.8 當k≧2時,K20k的初始S(C5)的差集.........26
圖3.9 K25的初始S(C5)及其差集..................31
圖3.10 K45的初始S(C5)的差集....................33
圖3.11 K65的初始S(C5)的差集....................35
圖3.12 K85的初始S(C5)的差集....................37
圖3.13 當k≧4時,K20k+5的初始S(C5)的差集.......38
圖3.14 K16分割成12個S(C5)......................43
參考文獻 [1] P. Adams, D. Bryant and A. Khodkar, 3, 5-cycle decomposition, J. Combin. Des. 6 (1998), 91-110.
[2] M. Buratti, Existence of 1-rotational k-cycle systems of the complete graph, Graphs Combin. 20 (2004), 41-46.
[3] M. Buratti and A. Del Fra, Existence of cyclic k-cycle system of the complete graph, Discrete Math. 261 (2003), 113-125.
[4] Chin-Mei Fu, Nan-Hua Jhuang, Yuan-Lung Lin, Hsiao-Ming Sung, From Steiner Triple Systems to 3-Sun Systems, submitted (2010).
[5] 邱羣博,完全圖分割成4-迴圈太陽圖之探討,淡江大學數學學系碩士論文 (2008)。
[6] 沈灝,組合設計理論(第二版),上海交通大學出版社 (2008)。
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2011-08-12公開。
  • 同意授權瀏覽/列印電子全文服務,於2011-08-12起公開。


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