| DC 欄位 |
值 |
語言 |
| DC.contributor | 數學系 | zh_TW |
| DC.creator | 楊千儒 | zh_TW |
| DC.creator | Chien-Ju Yang | en_US |
| dc.date.accessioned | 2024-7-23T07:39:07Z | |
| dc.date.available | 2024-7-23T07:39:07Z | |
| dc.date.issued | 2024 | |
| dc.identifier.uri | http://ir.lib.ncu.edu.tw:444/thesis/view_etd.asp?URN=111221012 | |
| dc.contributor.department | 數學系 | zh_TW |
| DC.description | 國立中央大學 | zh_TW |
| DC.description | National Central University | en_US |
| dc.description.abstract | 0-1矩陣是僅由0和1為元素構成的矩陣。令A為一個0-1矩陣，若存在任一A的子矩陣，透過將任意數量的元素1轉換成0可以使其與一0-1矩陣P相等，則稱此0-1矩陣A包含0-1矩陣P，且該子矩陣稱為一個P的複製。若0-1矩陣A不包含P，且將任一個元素0轉換成1會使得矩陣A包含P ，那麼我們稱A是一個P的飽和矩陣。取自[1]和[2]的研究結果，我們將介紹有最大和最小數量的1的Ik的飽和矩陣和Jk的飽和矩陣，並將一些證明改的更精簡。
另外，我們還會討論的是強制矩陣和置換趨避矩陣，這兩種都是行數和列數相同
的矩陣。令A為一個n × n的0-1矩陣，若A所包含的每個大小為n × n的置換矩陣皆包
含單位矩陣I3，那麼我們稱A是一個123-強制矩陣。若A所包含的每個n × n的置換矩陣
皆不包含k × k的單位矩陣Ik ，那麼A被稱為一個12 . . . k-置換趨避矩陣。我們會仔細釐
清[3]中對於有最大數量的1的123-強制矩陣的條件。最後，為了解決[1]中的一項未解問
題，對於12 . . . k-置換趨避矩陣，我們猜想在任意n × n的12 . . . k-置換趨避矩陣中，0的最小數量為((n-k+2)¦2)。 | zh_TW |
| dc.description.abstract | A 0-1 matrix consists of entries that are either 0 or 1. A 0-1 matrix A contains a 0-1
matrix P if A has a submatrix that can be made equal to P by changing any number
of 1-entries to 0-entries. This submatrix is called a copy of P in A. A 0-1 matrix A is
saturating for a 0-1 matrix P if A does not contain P, yet turning an arbitrary 0-entry of A into a 1-entry creates a copy of P in A. In the saturation problems, we introduce the results from [1] and [2] concerning the maximum and minimum numbers of 1-entries in matrices saturating for Ik and Jk, and succinctly rephrase some of the proofs. Another line of research focuses on square matrices. An n × n 0-1 matrix A is a 123-forcing matrix if every n × n permutation matrix in A contains the identity matrix I3. Conversely, an n × n 0-1 matrix A is 12..k-permutation-avoiding if none of n × n permutation matrix in A contains the identity matrix Ik. We clarify the characterization of 123-forcing matrices from [3] with the maximum number of 1-entries, and add missing parts to the original proof to make it complete. Finally, we conjecture that the minimum number of 0-entries in any n × n 12 . . . k-permutation-avoiding matrices is ((n-k+2)¦2), aiming to solve an open problem in [1]. | en_US |
| DC.subject | 0-1 矩陣 | zh_TW |
| DC.subject | 趨避矩陣 | zh_TW |
| DC.subject | 飽和 | zh_TW |
| DC.subject | 強制矩陣 | zh_TW |
| DC.subject | 置換趨避矩陣 | zh_TW |
| DC.subject | 0-1 matrix | en_US |
| DC.subject | excluded matrix | en_US |
| DC.subject | saturation | en_US |
| DC.subject | forcing matrix | en_US |
| DC.subject | permutation-avoiding matrix | en_US |
| DC.title | 0和1構成的飽和矩陣、123-強制矩陣與12..k-置換趨避矩陣 | zh_TW |
| dc.language.iso | zh-TW | zh-TW |
| DC.title | Saturation, 123-forcing, and 12..k-permutation-avoiding of 0-1 matrices | en_US |
| DC.type | 博碩士論文 | zh_TW |
| DC.type | thesis | en_US |
| DC.publisher | National Central University | en_US |