系統識別號 | 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)。 |
論文全文使用權限 |
如有問題,歡迎洽詢!
圖書館數位資訊組 (02)2621-5656 轉 2487 或 來信