完全圖分割成迴圈與星圖的探討

淡江大學機構典藏 > 理學院 > 數學學系暨研究所 > 學位論文 > Item 987654321/87449

請使用永久網址來引用或連結此文件: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/87449

題名:	完全圖分割成迴圈與星圖的探討
其他題名:	Decomposition of complete graphs into cycles and stars
作者:	黃建華;Huang, Chien-Hua
貢獻者:	淡江大學數學學系碩士班高金美;Kau, Chin-Mei
關鍵詞:	完全圖;迴圈;星圖;分割;complete graph;cycle;STAR;decomposition
日期:	2013
上傳時間:	2013-04-13 11:07:27 (UTC+8)
摘要:	一個具有n個點的圖中，若任意兩點皆有邊相連，我們稱此圖為n個點的完全圖，記作Kn。一個具有n個點的連通圖，其每一點的度數皆為2，我們稱此圖為n-迴圈，記作Cn。一個具有n+1個點的連通圖，其中有一點的度數為n，其餘各點的度數皆為1，我們稱此圖為星圖，記作Sn，同構於K1,n。設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，記作G = G1+ G2+ … + Gt。若H是G的子圖，且G1,G2,…,Gt都與H同構，則稱G可分割成t個H，記為G = tH。若G可分割成p個G1與q個G2，則記為G = pG1 + qG2。　在本論文中，我們證明了： (1) 當n≡0 (mod 6)，Kn可分割成C3和S3的各種組合。 (2) 當n≡1 (mod 6)，Kn可分割成C3和S3的各種組合。進而得到以下定理定理：當n≡1,3 (mod 6)，n ≧ 3且p、q為非負整數。如果Kn可分割成p個C3和q個S3，若且唯若p + q = n(n-1)/6 且q ≠ 1,2。 A complete graph Kn is a graph with n vertices and there is an edge joining any two vertices. An n-cycle Cn is a connected graph with n vertices and the degree of each vertex is 2. A star graph Sn is a graph with n+1 vertices and there is a vertex of degree n, the others are degree of 1. Let G be a simple graph and G1,G2,…,Gt be subgraphs of G. If E(G1)∪E(G2)∪…∪E(Gt) = E(G) and for all 1≦ i ≠ j ≦t，E(Gi)∩E(Gj) = empty set, then we call that G can be decomposed into G1, G2, … , Gt, denoted by G = G1+ G2+ … + Gt. If G1, G2, … , Gt are isomorphic to graph H, then we call G can be decomposed into H. If G can be decomposed into p copies of G1 and q copies of G2, that G can denoted by G = pG1 + qG2. In this paper, we show that: (1) if n≡1 (mod 6), then Kn can be decomposed into C3 and S3. (2) if n≡3 (mod 6), then Kn can be decomposed into C3 and S3. Combining the above results, we obtain the following theorem: Theorem: n≡1, 3 (mod 6), n≧3. For any nonnegative integers p and q. Kn can be decomposed into p copies of C3 and q copies of S3 if and only if p + q = n(n-1)/6 and q ≠ 1, 2。
顯示於類別:	[數學學系暨研究所] 學位論文

文件中的檔案:

檔案	大小	格式	瀏覽次數
index.html	0Kb	HTML	171	檢視/開啟

在機構典藏中所有的資料項目都受到原著作權保護.

TAIR相關文章

資料載入中.....