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


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-0807201012181400
中文論文名稱 λ重完全圖分割成箏形圖
英文論文名稱 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).
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2010-08-12公開。
  • 同意授權瀏覽/列印電子全文服務,於2011-08-12起公開。


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