§ 瀏覽學位論文書目資料
  
系統識別號 U0002-1607201006312700
DOI 10.6846/TKU.2010.00416
論文名稱(中文) 完全圖分割成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)。
論文全文使用權限
校內
紙本論文於授權書繳交後1年公開
同意電子論文全文授權校園內公開
校內電子論文於授權書繳交後1年公開
校外
同意授權
校外電子論文於授權書繳交後1年公開

如有問題,歡迎洽詢!
圖書館數位資訊組 (02)2621-5656 轉 2487 或 來信