Název:
Matice bez zakázaných intervalových minorů
Překlad názvu:
Matrices without forbidden interval minors
Autoři:
Surma, David ; Jelínek, Vít (vedoucí práce) ; Klazar, Martin (oponent) Typ dokumentu: Bakalářské práce
Rok:
2020
Jazyk:
cze
Abstrakt: [cze][eng] V 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. 1In 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
Klíčová slova:
binární matice; intervalový minor; zakázaný vzor; binary matrix; forbidden pattern; interval minor