Matice bez zakázaných intervalových minorů
Matrices without forbidden interval minors
bakalářská práce (OBHÁJENO)
Zobrazit/ otevřít
Trvalý odkaz
http://hdl.handle.net/20.500.11956/119444Identifikátory
SIS: 219042
Kolekce
- Kvalifikační práce [10693]
Autor
Vedoucí práce
Oponent práce
Klazar, Martin
Fakulta / součást
Matematicko-fyzikální fakulta
Obor
Obecná informatika
Katedra / ústav / klinika
Informatický ústav Univerzity Karlovy
Datum obhajoby
7. 7. 2020
Nakladatel
Univerzita Karlova, Matematicko-fyzikální fakultaJazyk
Čeština
Známka
Výborně
Klíčová slova (česky)
binární matice, intervalový minor, zakázaný vzorKlíčová slova (anglicky)
binary matrix, interval minor, forbidden patternV práci zkoumáme strukturu binárních matic, které neobsahují vzor P jako intervalový minor. Zabýváme se rovněž maticemi kritickými pro P, tedy maticemi neobsahujícími P, které po změně libovolného 0-prvku na 1-prvek zakázaný vzor P obsahují. Nejprve popi- sujeme matice kritické pro libovolný jednořádkový vzor. Dále se zabýváme všemi vzory o dvou řádcích a třech sloupcích, které obsahují nejvýše čtyři 1-prvky. Nakonec charak- terizujeme matice kritické pro střídavý vzor o rozměrech 2 × 4. 1
In the thesis, we study the structure of binary matrices which do not contain a pat- tern P as an interval minor. We also deal with matrices that are critical for P, i.e., matrices without P which after changing any 0-entry to 1-entry contain the forbidden pattern P. First, we describe matrices critical for any one-line pattern. Then we deal with all patterns with two rows and three columns which contain at most four 1-entries. Finally, we characterize the matrices critical for the alternating pattern of size 2 × 4. 1