系統識別號 | U0002-1507201309404700 |
---|---|
DOI | 10.6846/TKU.2013.00406 |
論文名稱(中文) | C4飽和圖的探討 |
論文名稱(英文) | The study of C4 saturated graph |
第三語言論文名稱 | |
校院名稱 | 淡江大學 |
系所名稱(中文) | 中等學校教師在職進修數學教學碩士學位班 |
系所名稱(英文) | Executive Master's Program In Mathematics for Teachers |
外國學位學校名稱 | |
外國學位學院名稱 | |
外國學位研究所名稱 | |
學年度 | 101 |
學期 | 2 |
出版年 | 102 |
研究生(中文) | 洪明岳 |
研究生(英文) | Ming-Yueh Hung |
學號 | 700190043 |
學位類別 | 碩士 |
語言別 | 繁體中文 |
第二語言別 | |
口試日期 | 2013-06-22 |
論文頁數 | 34頁 |
口試委員 |
指導教授
-
高金美
委員 - 顏經和 委員 - 李武炎 |
關鍵字(中) |
完全圖 完全多分圖 C4飽和圖 |
關鍵字(英) |
complete graph complete multipartite graph C4 saturated graph |
第三語言關鍵字 | |
學科別分類 | |
中文摘要 |
假設圖G 並不包含子圖C4,若在圖G 中任意不相鄰的兩點增加一邊後,就 會包含有子圖C4,那我們就稱圖G 為C4 飽和圖。令sat(n,C4)和ex(n,C4)分別代 表所有n 點C4 飽和圖中的邊數最小值與最大值。 在這篇論文中找到含有n 點C4 飽和圖的一種建構法,並給予含有n 點C4 飽和圖最少邊的一種建構法。再利用當n<=11 時C4 飽和圖的邊數之上、下界, 建構出其邊數介於sat(n,C4)和ex(n,C4)之間的n 點C4 飽和圖。接著應用圖的鄰接矩陣及C4 飽和圖的性質,利用Maple 判斷所產生的圖是否為C4 飽和圖。 我們定義了在完全多分圖中的C4 飽和圖,並探討完全多分圖Kn(m)的C4 飽 和圖中邊數最少的建構方式,得到以下結果: 1. sat(Kn,m, C4) <= m + n - 1,其中sat(Kn,m, C4) = min {│E(G)│: 圖G 為Kn,m 中C4 飽和圖}。 2. sat(Kn(m), C4) <= mn – 1 + ┌(n-2)/2┐*m, 其中sat(Kn(m), C4) = min {│E(G)│: 圖 G 為Kn(m) 中C4 飽和圖},┌x┐為大於等於x 的最小整數值。 |
英文摘要 |
Let G be a graph. If there is no 4-cycle contained in G and connecting any non adjacent vertices of G will obtain a 4-cycle, then we call G is a C4 saturated graph. Let sat(n, C4) and ex(n, C4) be the minimum and maximum number of edges of all C4 saturated graphs with n vertices, respectively. In this thesis, we obtain a construction of C4 saturated graph with n points, and give another construction of C4 saturated graph with minimum edge. For n <= 11, we give a C4 saturated graph with n vertices and q edges, for each q between sat(n, C4) and ex(n, C4). After that, we use Maple to check whether the graph is a C4 saturated graph by using the adjacency matrix of a graph and the properties of C4 saturated graphs. We define a C4 saturated graph in a complete multipartite graph Kn (m) and obtain the following results: 1. sat(Kn,m, C4) <= m + n - 1; and 2. sat(Kn(m), C4) <= mn – 1 + ┌(n-2)/2┐*m, where sat(K, C4) = min {|E(G)|: G is a C4 saturated graph in the graph K} and ┌x┐ is the smallest integer greater than x . |
第三語言摘要 | |
論文目次 |
目 錄 第一章 簡介 ………………………………1 第二章 基本定義 …………………………3 第三章 含有n個點的C4飽和圖 …………8 第四章 多分圖的C4飽和圖 ……………23 參考書目 ……………………………………34 |
參考文獻 |
參 考 書 目 [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]C. R. J. Clapham, A. Flockart, and J. Sheehan, Graphs without four-cycle, Journal of Graph Theory 13(1989), 29-47 [5] P. Erdos, A. Hajnal and J. W. Moon, A problem in graph theory, Amer. Math. Monthly71(1964) 1107-1110. [6]Z. Furedi, An upper bound on Zarankiewwcz’ problem, Combin. Probab. Comput. (5) (1996) 29-33. [7]Z.Furedi, New asymptotics for bipartite Turan numbers, J. Combin. Theory Ser. A 75 141-144. [8]I. Reiman, Uber ein Problem von K. Zarankiewicz, Acta Math. Acad. Sci. Hungar. 9(1958),269-278 [9]L. T. Ollmann,K2,2 saturated graphs with a minimal number of edges, In: F. Hoffman, R. B. Levow and R.S.D. Thomas, eds., Proc. 3rd Southeasten Conference on Combinatorics, Graph Theory and Computing, Boca Raton, Florida (1972) 367-392. [10]Z. Tuza, C4-saturated graphs of minimum size, Acta Univ. Carolin. - Math. Phys. 30(1989)161-167. [11]Yang Yuansheng and P. Rowlinson,On extremal graphs without four-cycles, utilitas Mathematica 41(1992), 204-220. |
論文全文使用權限 |
如有問題,歡迎洽詢!
圖書館數位資訊組 (02)2621-5656 轉 2487 或 來信