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


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-2306200507391300
中文論文名稱 完全二分圖K2m,2n分割成4、6、8、10迴圈之探討
英文論文名稱 The study of decompositions of K2m,2ninto 4-cycles, 6-cycles, 8-cycles, or 10-cycles
校院名稱 淡江大學
系所名稱(中) 數學學系碩士班
系所名稱(英) Department of Mathematics
學年度 93
學期 2
出版年 94
研究生中文姓名 林遠隆
研究生英文姓名 Yuan-Lung Lin
學號 692150039
學位類別 碩士
語文別 中文
口試日期 2005-06-03
論文頁數 46頁
口試委員 指導教授-高金美
委員-江南波
委員-周兆智
中文關鍵字   二分圖  分割  迴圈 
英文關鍵字 graph  bipartite graph  decomposition  cycle 
學科別分類 學科別自然科學數學
中文摘要 一個圖的點集合如果可分為兩個互不相交的非空集合,且同一集合中的任意兩點皆不相連,則稱此圖為ㄧ個二分圖,若在不同的集合中的任意兩點都有邊相連,則稱此圖為完全二分圖,並用Km,n來表示。
ㄧ個完全二分圖Km,n能分割成一些子圖是指Km,n中的邊可以分成為一些邊均相異的子圖,且這些子圖的點集合的聯集為Km,n的點集合,邊集合的聯集為Km,n的邊集合。
在本篇論文中,首先我們證明當22及非負整數p、q、r、s,若4p+6q+8r+10s = 4mn,則我們可將完全二分圖K2m,2n分割成p個4-迴圈、q個6-迴圈、r個8-迴圈、s個10-迴圈。
英文摘要 A graph is called a bipartite graph if the vertex set of the graph can be partitioned into two disjoint nonempty sets, and any two vertices in the same set are not adjacency. Moreover, if any two vertices in the different set are adjacency, then this bipartite graph is called a complete bipartite graph, and denoted by Km,n.
A complete bipartite graph Km,n can be decomposed into some subgraphs if Km,n can be partitioned into edge-disjoint subgraphs, such that the union of vertex sets of these subgraphs is the vertex set of Km,n, and the union of edge sets is the edge set of Km,n.
In this thesis, we show that when 22 and non-negative integets p, q, r, s, if 4p+6q+8r+10s = 4mn, then K2m,2n can be decomposed into p 4-cycle, q 6-cycle, r 8-cycle, or s 10-cycle.
論文目次 目 錄
第一章 簡介 …………………………… 1
第二章 預備知識 ……………………… 3
第三章 分割成4、6、8、10迴圈 ……… 6
参考書目 …………………………………… 25
附錄一 …………………………………… 26
附錄二 …………………………………… 31
附錄三 …………………………………… 43
參考文獻 [1] P. Adams, D. E. Bryant, and A. Khodkar, (1998) (3,5)-cycle decompositions, J. Combin. Designs, 6, 91-110.
[2] B. Alspach and H.Gavlas, Cycle decompositions of Kn and Km,n - I,
J. Combin. Theory Ser. B (2001), 77-99.
[3] B. Alspach and S. Marshall, (1994) Even cycle decompositions of complete graphs minus a 1-factor, J. Combin. Designs 2, 441-458.
[4] B. Alspach, (1980) Research Problem 3, Discrete Math. 36, 333-334.
[5] D. E. Bryant, A. Khodkar and H. L. Fu, (m,n)-cycle systems. J. Statist. Planning ang Inference 74 (1998), 365-370.
[6] C. C. Chou, C. M. Fu and W. C. Huang, (2000) Decomposition of
2Km,n into short cycles, Utilitas Mathematica 58, pp. 3-10
[7] Dorit Dor, Michael Tarsi, (1997) Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture, SIAM Journal on Computing, Volume 26, Number 4, 1166-1187
[8] C. M. Fu and W. C. Huang, (1998) Decompositions of Km,n into 4-cycles and 8-cycles, Tamkang Journal of Math. Vol. 29, No. 1, 69-72
[9] R.Haggkvis, (1985) A lemma on cycle decomposition, Ann, Discrete Math., 27, 227-232.
[10] K. Heinrich, P. Horak and A. Rosa, (1989) On Alspach’s conjecture. Discrete Math., 77, 97-121.
[11] Y. S. Huang, (2003) The study of decomposing K2m,2n and K2m+1,2n+1 F into cycles of length 4 or 2t.
[12] A. Rosa, (1989) Alspach’s conjecture is true for , Mathematical reports, McMaster University.
[13] D. Sotteau, (1981) Decomposition of Km,n (K*m,n) into cycles(circuit) of length , J. Combin. Theory Ser. B, 30, 75-81.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2005-06-28公開。
  • 同意授權瀏覽/列印電子全文服務,於2005-06-28起公開。


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