簡易檢索 / 詳目顯示
| 研究生： |
卓駿焰 |
|---|---|
| 論文名稱： |
(s,t)單色矩形於二色棋盤之存在性 The Existence of (s,t)-Monochromatic-rectangles in a 2-colored Checkerboard |
| 指導教授： | 張宜武 |
| 學位類別： |
碩士
Master |
| 系所名稱： |
理學院 - 應用數學系 Department of Mathematical Sciences |
| 論文出版年： | 2016 |
| 畢業學年度： | 104 |
| 語文別： | 英文 |
| 論文頁數： | 34 |
| 中文關鍵詞： | 完全二分圖 、單色子圖 |
| 相關次數： | 點閱：26 下載：8 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
本文藉由矩形棋盤著色探討完全二分圖K_{m,n}由兩種顏色任意塗邊，使得此兩色著邊之完全二分圖$K_{m,n}$會包含單色子圖K_{s,2}、K_{s,3}與K_{s,t} （s大於或等於 2），我們將討論參數n與s之間滿必須滿足何種關係。
本文也將介紹處理棋盤著色問題的一般方法與技巧，以及透過棋盤如何將棋盤問題轉化為圖論問題，並且將它推廣。
口試委員會審定書 i
中文摘要 ii
Abstract iii
Contents iv
List of Figures vi
1 Introduction 1
2 (2,2)-Monochromatic-rectangles in a Checkerboard 3
2.1 The Case of 2×n Checkerboard 4
2.2 The Case of 3×n Checkerboard 5
2.3 The Case of 4×n Checkerboard 6
2.4 The Case of 5×n Checkerboard 7
2.5 Summary 9
3 (2,t)-monochromatic-rectangles in a Checkerboard 13
3.1 The Case of 2×n Checkerboard 13
3.2 The Case of 3×n Checkerboard 13
3.3 The Case of 4×n Checkerboard 14
3.4 The Case of 5×n Checkerboard 14
3.5 Summary 23
4 (3,2)-Monochromatic-rectangles in a Checkerboard 24
4.1 The Case of 3×n Checkerboard 24
4.2 The Case of 4×n Checkerboard 24
4.3 The Case of 5×n Checkerboard 24
4.4 The Case of 6×n Checkerboard 25
4.5 Summary 26
5 (3,t)-Monochromatic-rectangles in a Checkerboard 27
5.1 The Case of 5×n Checkerboard 27
5.2 The Case of 6×n Checkerboard 28
5.3 Summary 28
6 (s,2)-Monochromatic-rectangles in a Checkerboard 29
6.1 The Case of (2s−2)×n Checkerboard 29
6.2 The Case of (2s−1)×n Checkerboard 29
6.3 The Case of 2s×nCheckerboard 30
6.4 Summary 31
7 (s,t)-Monochromatic-rectangles in a Checkerboard 32
7.1 The Case of (2s−1)×n Checkerboard 32
7.2 The Case of 2s×n Checkerboard 33
7.3 Summary 33
Bibliography 34
[1] Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer. Ramsey theory. Wiley Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., Hoboken, NJ, 2013.
[2] Douglas B. West. Introduction to graph theory. Prentice Hall, Inc., Upper Saddle River, NJ, 1996.
[3] 李炯生. 棋盤染色問題與二部 Ramsey 數. 數學, 21(3):63–72, 9 月 1997.
[4] 林子軒. The coloring of a checkerboard and the monochromatic subgraphs of a complete bipartite graph. 國立政治大學應用數學系碩士學位論文, 2013.
