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


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-2606201208290600
中文論文名稱 不含K_2,3的二分極圖
英文論文名稱 Extremal K_2,3-free Bipartite Graphs
校院名稱 淡江大學
系所名稱(中) 中等學校教師在職進修數學教學碩士學位班
系所名稱(英) Executive Master's Program In Mathematics for Teachers
學年度 100
學期 2
出版年 101
研究生中文姓名 沈春梅
研究生英文姓名 Chun-Mei Shen
學號 799190037
學位類別 碩士
語文別 中文
口試日期 2012-06-14
論文頁數 40頁
口試委員 指導教授-高金美
委員-黃文中
委員-潘志實
委員-高金美
中文關鍵字 Zarankiewicz問題  二分極圖  二分圖  圖的分割  完全圖 
英文關鍵字 Zarankiewicz problem  extremal graph  bipartite graph  graph decomposition  complete graph. 
學科別分類
中文摘要 一個不含K_2,2的二分極圖是一個含有最多邊數且不含有子圖K_2,2的二分圖。若此二分圖為K_m,n的子圖,則求此二分極圖的邊數的問題也就是出名的Zarankiewicz問題。在本論文中,我們令g(m,n)為K_m,n中不含K_2,3的二分極圖的邊數。我們得到一些結果。
英文摘要 An extremal K_2,2-free bipartite graphs is a bipartite graph which contains the maximum number of edges and does not contain any subgraph K_2,2 . If this bipartite graph is a subgraph of K_m,n, then finding the number of edges of the extremal bipartite graph is the well-known Zarankiewicz Problem . In this thesis , we let be the number of edges of the extremal K_2,3-free bipartite graph which is a subgraph of K_m,n .We obtain some results.
論文目次 目錄

第一章 簡介-----------------------------------------1

第二章 預備知識-------------------------------------3

第三章 主要內容----------------------------------------6
第3.1節 Zarankiewicz問題-------------------6
第3.2節 g(m,n)的值-------------------------6
第3.3節 2_Km,n分成相異的兩個STS(m) --------21

參考文獻-----------------------------------------------39

圖表目錄
圖1 不為簡單圖 3
圖2 簡單圖 3
圖3 二分圖與完全二分圖 4
圖4 完全圖與二重完全圖 4
圖5 K_4 分割成1個K_3及3個K_2 5
圖6 K_4,4的子圖 5
圖7 完全子圖 8
圖8 2K_3分成3個完全子圖 9
圖9 2K_3分割成4個完全子圖 9
圖10 2K_3分割成5個完全子圖 10
圖11 2K_3分成5個完全子圖 10
圖12 2K_3分割成6個完全子圖 10
圖13 2K_3分割成6個完全子圖 10
圖14 2K_3分割成7個完全子圖 11
圖15 2K_4分割成4個完全子圖 12
圖16 2K_5分成n個完全子圖 14
表1 g(4,n)的值 12
表2 g(5,n)的值 15
表3 兩個STS(7) 21
表4 兩個STS(13) 22
表5 兩個STS(9) 23
表6 兩個STS(15) 23-24
表7 2K_10分割成30個相異的K_3 25
表8 2K_6分割成10個相異的K_3 27
表9 2K_12分割成44個相異的K_3 27-28
表10 2K_8的分割 32
表11 2K_11可分割 33-34




參考文獻 [1] Bollobás, B., “Extremal Graph Theory,” Academic Press, New York, 1978.
[2] Culik, K., Teilwesise Losung eines verallgemeinerten Problems von Zarankiewicz,
Anna. Soc. Polon. Math. 3 (1956), 165-168.
[3] Goddard, W., M.A. Henning and O.R. Oellermann, Bipartite Ramsey numbers and
Zarankiewicz numbers, Discrete Math. 219 (2000),85-89.
[4] Griggs, J., and J. Ouyang, (0,1)-Matrices with no half-half submatrix of
ones,European J. Combinatorics 18 (1997),751-761
[5] Guy, R.K., A problem of Zarankiewicz Theory of Graphs, (Rosentstiehl, P. ed.)
Gordon and Breach, New York (1967),139-142.
[6] Guy, R.K., A problem of Zarankiewicz Theory of Graphs, (Erdös, P. and Kantona G.,
eds.) Academic Press, New York (1968), 119-150.
[7] Guy, R.K., The many faceted problem of Zarankiewicz The Many Facets of Graphs
Theory, Lecture Notes in Maths 110, Springer, (1969), 129-148.
[8] Guy, R.K., and S. Znám, A problem of Zarankiewicz Recent progress in
Combinatorics, (Tutte, W.T., ed.) Academic Press, New York (1969), 237-243.
[9] Sierpinski, S., Sur un problème concernant un reseau á 36 points, Ann. Pol. Math. 24
(1951), 173-174.
[10] Zarankiewicz, K. Problem P 101, Colloq. Math. 2 (1951), 301.
[11]傅恆霖(Hung-Lin Fu),組合設計講義Combinational Designs (Lecture Notes),65-78
http://www.math.nctu.edu.tw/hlfu/getCourseFile.php?CID=48&type=browser

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


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