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


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-2406201223111700
中文論文名稱 不含 K_2,2 的二分極圖
英文論文名稱 Extremal K_2,2-free Bipartite Graphs
校院名稱 淡江大學
系所名稱(中) 中等學校教師在職進修數學教學碩士學位班
系所名稱(英) Executive Master's Program In Mathematics for Teachers
學年度 100
學期 2
出版年 101
研究生中文姓名 賴尚欣
研究生英文姓名 Shang-Hsin Lai
學號 799190060
學位類別 碩士
語文別 中文
口試日期 2012-06-14
論文頁數 32頁
口試委員 指導教授-高金美
委員-周兆智
委員-潘志實
中文關鍵字 Zarankiewicz問題  極圖  二分圖  導出子圖  圖的分割 
英文關鍵字 Zarankiewicz problem  extremal graph  bipartite graph  graph decomposition 
學科別分類
中文摘要 一個不含 K_2,2 的二分極圖是一個含有最多邊數且不含有子圖 K_2,2 的二分圖。若此二分圖為 K_m,n 的子圖,則求此二分極圖的邊數的問題也就是出名的Zarankiewicz 問題。在本論文中,我們令f(m,n)為 K_m,n 中不含 K_2,2 的二分極圖的邊數。我們獲得以下的結果:
①f(m,n)≤n/2+√(mn(m-1)+n^2/4)
②若 n≥(m|2),則 f(m,n)=(m|2)+n。
③若 m≡1,3 (mod 6),則 K_m 恰可分割成 m(m-1)/6 個邊相異的 K_3 子圖,且f(m,n)=(m|2)。
④若 ((m|2))/3≤n≤(m|2),則 f(m,n)=[((m|2)+3n)/2] 。
⑤若 m≡1,4 (mod 12),則 K_m 恰可分割成 m(m-1)/12 個邊相異的 K_4 子圖,且,f(m,n)=2(m|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 f(m,n) be the number of edges of the extremal K_2,2-free bipartite graph which is a subgraph of K_m,n. We obtain the following results:
①f(m,n)≤n/2+√(mn(m-1)+n^2/4)
②If ≥(m|2), then f(m,n)=(m|2)+n.
③If m≡1,3 (mod 6), then K_m decompose into (m(m-1))/6 edge-disjoint K_3 subgraphs, and f(m,n)=(m|2).
④If ((m|2))/3≤n≤(m|2), then f(m,n)=[((m|2)+3n)/2] .
⑤If m≡1,4 (mod 12), then K_m decompose into (m(m-1))/12 edge-disjoint K_4 subgraphs, and f(m,n)=2(m|2)/3.
論文目次 目錄

第一章 簡介 1
第二章 預備知識 3
第三章 主要內容 11
第3.1節 Zarankiewicz 問題 11
第3.2節 求f(m,n)值 11
第3.3節 二分圖與 f(m,n) 14
第3.4節 K_m 的裝填與 f(m,n) 17
參考文獻 32

圖表目錄
圖1 圖G 4
圖2 完全圖 K_m 6
圖3 完全二分圖 K_m,n 7
表1 鄰接矩陣 5
表2 關聯矩陣 6
表3 匹配 9
表4 K_8 的完美匹配 9
表5 K_5 的分割與裝填 10
表6 2×2 矩陣 11
表7 在2×n 矩陣加入1~2行 12
表8 二種添加方式 12
表9 加入的每行只能有1個1 13
表10 f(4,4) 與f(4,5) 14
表11 矩陣與二分圖轉換1 15
表12 矩陣與二分圖轉換2 15
表13 矩陣與二分圖轉換3 15-16
表14 出現 J_2×2 的情形 16
表15 導出子圖 17-18
表16 m=4 的導出子圖 19
表17 m=5、6、7 時的 f(m,n) 值 19
表18 K_7 分割成7個 K_3 子圖 23
表19 多加1個子圖時 23
表20 多加2個子圖時 23
表21 以 K_3 裝填 K_m 時的最小殘留 25
表22 ((m|2))/3≤n≤(m|2)時f(m,n)之值 27-28
表23 m≤n≤((m|2))/3時f(m,n) 之值 30-31
參考文獻 [1] Bollobes, B., “Extremal Graph Theory,” Academic Press, New York, 1978.
[2] Colbourn, Charles J. and Dinitz, Jeffrey H., The CRC Handbook of Combinatorial Designs, CRC Press, 1996.
[3] Culik, K., Teilwesise Losung eines verallgemeinerten Problems von Zarankiewicz, Anna. Soc. Polon. Math. 3 (1956), 165-168.
[4] Goddard, W., M.A. Henning and O.R. Oellermann, Bipartite Ramsey numbers and Zarankiewicz numbers, Discrete Math. 219 (2000), 85-89.
[5] Griggs, J., and H. Chih-Chang, On the half-half case of the Zarankiewicz problem, Discrete Math. 249 (2002), 9-104.
[6] Griggs, J., and J. Ouyang, (0,1)-Matrices with no half-half submatrix of ones, European J. Combinatorics 18 (1997), 751-761.
[7] Guy, R.K., A problem of Zarankiewicz Theory of Graphs, (Rosentstiehl, P. ed.) Gordon and Breach, New York (1967), 139-142.
[8] Guy, R.K., A problem of Zarankiewicz Theory of Graphs, (Erdos, P. and Kantona G., eds.) Academic Press, New York (1968), 119-150
[9] Guy, R.K., The many faceted problem of Zarankiewicz The Many Facets of Graphs Theory, Lecture Notes in Maths 110, pringer,(1969), 129-148.
[10] Guy, R.K., and S. Znam, A problem of Zarankiewicz Recent progress in Combinatorics, (Tutte, W.T., ed.) Academic Press, New York (1969), 237-243.
[11] Kirkman,Thomas P., On a Problem in Combinations, The Cambridge and Dublin Mathematical Journal. (Macmillan, Barclay, and Macmillan) 2 (1847), 191–204.
[12] Sierpinski, S., Sur un probleme concernant un reseau a 36 points, Ann. Pol. Math. 24 (1951), 173-174.
[13] Zarankiewicz, K. Problem P 101, Colloq. Math. 2 (1951), 301.
[14] 傅恆霖(Hung-Lin Fu),組合設計講義Combinational Designs (Lecture Notes), 65-78 http://www.math.nctu.edu.tw/hlfu/getCourseFile.php?CID=48&type=browser
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2012-06-26公開。
  • 同意授權瀏覽/列印電子全文服務,於2012-06-26起公開。


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