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


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-2007200601180600
中文論文名稱 完全雙分圖中不含C4飽和子圖的探討
英文論文名稱 The study of C4-saturated bipartite graphs
校院名稱 淡江大學
系所名稱(中) 數學學系碩士班
系所名稱(英) Department of Mathematics
學年度 94
學期 2
出版年 95
研究生中文姓名 林泰平
研究生英文姓名 Tai-Ping Lin
學號 693150137
學位類別 碩士
語文別 中文
口試日期 2006-06-16
論文頁數 40頁
口試委員 指導教授-高金美
委員-傅恆霖
委員-周兆智
委員-高金美
中文關鍵字   雙分圖  不含C4的飽和圖 
英文關鍵字 graph  bipartite graph  C4-saturated 
學科別分類 學科別自然科學數學
中文摘要 如果圖G中不含C4,但再增加一邊之後就會產生C4,則稱圖G是不含C4的飽和圖。圖G為在Km,n中不含C4的飽和子圖,即表示圖G為Km,n的子圖,且為不含C4的飽和圖。在此篇論文中,主要是討論在Km,n中不含C4飽和子圖的可能邊數。我們令S(m,n)={t︱存在G為在Km,n中不含C4的飽和子圖,且︱E(G)︱=t},利用組合設計中之史坦納三元系及Bryant和Fu論文中判別圖G是否為含有最多邊的不含C4的飽和圖的建構法,而獲得當n足夠大時S(m,n)的最大值,及m≡0,1,2,3(mod 6)時S(m,n)的最大值。當1≦m≦6時,獲得S(m,n)的所有元素,進而建構出一些在Km,n中不含C4的飽和子圖,產生S(m,n)中所含的一些元素。
英文摘要 A C4-saturated graph is a graph G which contains no C4,but when adding any edge in G will results C4.A C4-saturated bipartite graph in Km,n is a subgraph G of Km,n and G is a C4-saturated graph.In this thesis,we consider the possible number of edges of C4-saturated bipartite graphs in Km,n .We define S(m,n)={t|there exists a graph G which is a C4-saturated bipartite graph in Km,n with t edges}.By using the Steiner triple system in combinatorial designs and the construction in the paper of Bryant and Fu which showed that a maximum C4-saturated bipartite graph in Km,n ,we obtain the maximum value of S(m,n) when n is large or m≡0,1,2,3(mod 6).After that,we obtain the spectrum of S(m,n) when 1≦m≦6.We get some elements in S(m,n).
論文目次 第一章 簡介 …………………………………… 1
第二章 預備知識 ……………………………… 5
第三章 Km,n中不含C4的飽和子圖最大和最小邊數12
第四章 Km,n中不含C4 的飽和子圖的邊數 …… 20
參考書目 ………………………………………… 38
附錄 ……………………………………………… 39 

圖 表 目 錄

圖2.1,2.2 …………………………………… 5
圖2.3,2.4,2.5 ……………………………… 6
圖2.6 ………………………………………… 7
圖2.7 ………………………………………… 8
圖2.8,2.9 …………………………………… 9
圖2.10,2.11,2.12,2.13,2.14,2.15,2.16,
2.17,2.18 ……………………………… 10
圖3.1 ………………………………………… 14
圖3.2 ………………………………………… 17
圖3.3 ………………………………………… 19
表4.1,4.2,4.3 ……………………………… 27
圖4.4,4.5 …………………………………… 30
圖4.6,4.7 …………………………………… 31
圖4.8,4.9 …………………………………… 33
圖4.10,4.11 ………………………………… 34
圖4.12,4.13 ………………………………… 37
 
參考文獻 [1] A.E. Andreev, On an algebraic method for construction
of extremal Boolean matrices, Comput. Artif. Intell. 10
(2) (1991) 99-109.
[2] B. Bollobas, Extremal Graph Theory, Academic Press, New
York, 1978.
[3] D.E. Bryant and Hung-Lin Fu, C4-saturated bipartite
graphs, Discrete Math. 259 (2002) 263-268.
[4] Z. Furedi, An upper bound on Zarankiewicz’problem,
Combin. Probab. Comput. (5) (1996) 29-33.
[5] Z. Furedi, New asymptotics for bipartite Turan
numbers, J. Combin. Theory Ser. A 75 141-144.
[6] J.R. Griggs, Chih-Chang Ho, On the half-half case of
the Zarankiewicz problem, preprint.
[7] J.R. Griggs, Ouyang, (0,1)-matrices with no half-half
submatrix of ones, European J. Combin. 18 (1997) 751-
761.
[8] T.P. Kirkman, On a problem in combinations, Cambridge
and Dublin Math. Journal, 2 (1847), 191-204.
[9] K. Zarankiewicz, Problem p 101, Colloq. Math. 2 (1951)
301.

論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2006-08-01公開。
  • 同意授權瀏覽/列印電子全文服務,於2006-08-01起公開。


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