系統識別號 | U0002-0807201012181400 |
---|---|
DOI | 10.6846/TKU.2010.00249 |
論文名稱(中文) | λ重完全圖分割成箏形圖 |
論文名稱(英文) | Decomposition of λKn into kites |
第三語言論文名稱 | |
校院名稱 | 淡江大學 |
系所名稱(中文) | 數學學系碩士班 |
系所名稱(英文) | Department of Mathematics |
外國學位學校名稱 | |
外國學位學院名稱 | |
外國學位研究所名稱 | |
學年度 | 98 |
學期 | 2 |
出版年 | 99 |
研究生(中文) | 鄭智中 |
研究生(英文) | Chih-Chung Cheng |
學號 | 696190254 |
學位類別 | 碩士 |
語言別 | 繁體中文 |
第二語言別 | |
口試日期 | 2010-06-18 |
論文頁數 | 56頁 |
口試委員 |
指導教授
-
高金美
委員 - 黃文中 委員 - 周兆智 委員 - 潘志實 |
關鍵字(中) |
完全圖 λ重完全圖 分割 箏形圖 |
關鍵字(英) |
complete graph λ-fold complete graph decomposition kite |
第三語言關鍵字 | |
學科別分類 | |
中文摘要 |
一個含有n個點的簡單圖,其中任意兩點皆有一邊相連,則稱此圖為一個完全圖,記為Kn。若一個n點的重邊圖,任意兩點皆有λ個邊相連,則稱此圖為一個λ重完全圖,記為λKn。 一個圖H的點集合為V(H)={a,b,c,d},邊集合為E(H)={{a,b},{a,c},{b,c},{c,d}},則稱此圖H為箏形圖,記為(a,b,c; d)或(b,a,c; d)。 設G1, G2, …, Gt為圖 Kn 的子圖,若滿足以下條件: (1) E(G1)∪E(G2)∪…∪E(Gt) = E(Kn); (2) 對於1≦i≠j≦n, E(Gi)∩E(Gj) = ∅, 則稱Kn可分割成G1, G2, …, Gt。若Gi與箏形圖H同構,i=1, 2, …, n,則稱Kn可分割成箏形圖H。 設H為Kn的子圖,且H為箏形圖,λKn可分割成箏形圖H,表示可將λKn中的所有邊分成幾個子集合,每個子集合可形成一個箏形圖H,且Kn中的任一邊出現在λ個相異箏形圖H中。 在本篇論文中,我們證明了: λ≡1,3 (mod 4),且 n≡0,1 (mod 8) ⇔ λKn可分割成箏形圖。 λ≡2 (mod 4),且 n≡0,1 (mod 4) ⇔ λKn可分割成箏形圖。 λ≡0 (mod 4),且 ∀n≥4 ⇔ λKn可分割成箏形圖。 |
英文摘要 |
A simple graph with n vertices satisfies that every two vertices are joined by an edge, then we call this graph a complete graph with n vertices, denoted by Kn. If a multigraph with n vertices satisfies that every two vertices are joined by λ edges, then we call this graph a λ-fold complete graph with n vertices, denoted by λKn. Let H be the graph with the vertex set {a, b, c, d} and the edge set {{a, b}, {a, c}, {b, c}, {c, d}} ,we call H a kite graph, denoted by (a, b, c; d) or (b, a, c; d). Let G1, G2, …, Gt be subgraphs of Kn. If they satisfy the following conditions: (1) E(G1)∪E(G2)∪…∪E(Gt) = E(Kn) (2) ∀1≦i≠j≦n, E(Gi)∩E(Gj) = ∅ then we call λKn be decomposed into G1, G2, …, Gt. If Gi is isomorphic to a graph H, for each i = 1, 2, …, n, then we call Kn be decomposed into graphs H. Let H be a subgraph of Kn. If all edges of λKn can be partitioned into subsets which form a kite graph H and each edge of λKn is contained in λ different kite graphs H, then we call λKn can be decomposed into kite graphs H. In this thesis, we proved that (1) λ≡1,3 (mod 4) and n≡0,1 (mod 8) ⇔ λKn can be decomposed into kites. (2) λ≡2 (mod 4) and n≡0,1 (mod 4) ⇔ λKn can be decomposed into kites. (3) λ≡0 (mod 4) and ∀n≥4 ⇔ λKn can be decomposed into kites. |
第三語言摘要 | |
論文目次 |
目錄 第一章 簡介 1 第二章 預備知識 2 第三章 Kn可分割成箏形圖 9 第四章 λKn可分割成箏形圖 23 第一節 2Kn可分割成箏形圖 23 第二節 3Kn可分割成箏形圖 24 第三節 4Kn可分割成箏形圖 25 第四節 λKn可分割成箏形圖 55 參考文獻 56 圖目錄 圖2.1 簡單圖 2 圖2.2 重邊圖 2 圖2.3 P4 2 圖2.4 3 圖2.5 C3 3 圖2.6 K4 3 圖2.7 K3,3 4 圖2.8 K2,2,2 5 圖2.9 箏形圖 5 圖2.10 H為G的子圖 6 圖2.11 G可分割成G1和G2 7 圖3.1 K4,4,4分割成4個K2,2,2 10 圖3.2 K2,2,2分割成4個C3 10 圖3.3 K2,2,2分割成3個箏形圖 10 圖3.4 K8k的分割 12 圖3.5 K2k的分割 12 圖3.6 K8k的分割 15 圖3.7 K2k的分割 16 圖3.8 K8k+1的分割 18 圖3.9 K8k+1的分割 20 圖4.1 2K4 23 圖4.2 2K5 23 圖4.3 4K8k+2的分割 27 圖4.4 4K8k+2的分割 30 圖4.5 4個K3的聯集 33 圖4.6 4K8k+3的分割 34 圖4.7 4K8k+3的分割 38 圖4.8 4K8k+6的分割 41 圖4.9 4K8k+6的分割 45 圖4.10 4K8k+7的分割 49 圖4.11 4K8k+7的分割 52 |
參考文獻 |
[1] Ian Anderson , Combinatorial Designs and Tournaments, Oxford University Press, Incorporated (1998). [2] P. Adams, E. J. Billington, and C. C. Lindner, k-perfect 3k-cycle systems, J. Combin. Math. Combin. Comput. 15 (1994), 141-154. [3] Elizabeth J. Billington, Donald L. Kreher, The intersection problem for small G-designs (1995). [4] J. C. Bermond and J. Schönheim, G-decomposition of Kn, where G has four vertices or less, Discrete Math. 19 (1977), 113-120. [5] P. Erdös and J. Schönheim, Edge decomposition of the complete graph into copies of a connected graph, Proc. Toronoto, Algebraic aspects of Combinatorics (1975), 271-278. [6] C. Huang, Balanced graph designs in small graph. Utilitas Math. to appear. [7] Hung-Lin Fu, Combinatorial Designs. [8] C. C. Lindner, C. A. Rodger, Design theory, CRC-Press; 1st. edition (1997). [9] C. C. Linder, E. S. Yazici, The Triangle Intersection Problem for Kite System (2005). |
論文全文使用權限 |
如有問題,歡迎洽詢!
圖書館數位資訊組 (02)2621-5656 轉 2487 或 來信