|
|
Geometric and algebraic properties of discrete structures
Rytíř, Pavel ; Loebl, Martin (vedoucí práce) ; Serra, Oriol (oponent) ; Kaiser, Tomáš (oponent)
V práci se zabýváme dvou-dimenzionálními simpliciálními komplexy a lineárními kódy. Řekneme, že lineární kód C nad tělesem F je trojúhelníkově reprezentovatelný, pokud exis- tuje dvou-dimenzionální simpliciální komplex ∆ takový, že kód C je propíchnutým kódem jádra ker ∆ incidenční matice simpliciálního komplexu ∆ nad F a dim C = dim ker ∆. Tento simpliciální komplex nazveme geometrickou reprezentací kódu C. Dokážeme, že každý lineární kód nad prvotělesem je trojúhelníkově reprezentovatelný. Pro konečná prvotělesa sestrojíme geometrickou reprezentaci takovou, že váhový polynom kódu C je dán jednoduchou formulí váhového polynomu prostoru cyklů simpliciálního kom- plexu ∆. Tedy geometrická reprezentace kódu C určuje jeho váhový polynom. Naše motivace pochází z teorie pfaffiánovských orientací grafů, která poskytuje polyno- miální algoritmus pro výpočet váhového polynomu prostoru řezů grafu s omezeným rodem. Tento algoritmus využívá geometrických vlastností nakreslení grafu na orientovatelnou ri- emannovskou plochu. Prostor řezů je lineární kód a odpovídající graf je jeho užitečnou geometrickou reprezentací. Dále studujeme vnořitelnost geometrických reprezentací do euklidovských prostorů. Ukážeme, že každý binární lineární kód má geometrickou reprezentaci v R4 . Charakte- rizujeme binární lineární kódy, které...
|
|
|
Algorithmic aspects of intersection-defined graph classes
Jedličková, Nikola ; Kratochvíl, Jan (vedoucí práce) ; Fiala, Jiří (oponent)
Geometricky reprezentovatel'né triedy grafov sú intenzívne študovanou oblast'ou výskumu v súčasnej literatúre, a to kvôli ich štrukturálnym charakterizáciám a efektívnym algoritmom. Najštudovanejšou triedou takých grafov je trieda intervalových grafov. V tejto práci sa za- meriame na dva problémy, zovšeobecňujúce problém rozpoznávania, pre triedy súvisiace s triedou intervalových grafov. V prvej časti sa zaoberáme tzv. zarovnanými intervalovými digrafmi. Táto trieda bola skúmaná ako správna analógia intervalových grafov. Pre intervalové grafy sú známe algo- ritmy pre rozširovanie čiastočných reprezentácií daných intervalov na úplnú intervalovú re- prezentáciu. My predstavíme podobný problém - rozširovanie čiastočných usporiadaní - a ukážeme polynomiálny algoritmus pre rozširovanie čiastočných usporiadaní zarovnaných intervalových digrafov. V druhej časti práce dokážeme NP-úplnost' pre dva špeciálne prípady problému simultánnych reprezentácií grafov, ktorý predstavil Jampani a Lubiw. Problém simultánnych reprezentácií pre danú triedu grafov sa pýta, či k grafov môže byt' reprezentovaných tak, že každý vrchol je reprezentovaný rovnakým objektom v každej reprezentácii. Dokázali sme, že tento problém je...
|
|
|
Geometric and algebraic properties of discrete structures
Rytíř, Pavel ; Loebl, Martin (vedoucí práce) ; Serra, Oriol (oponent) ; Kaiser, Tomáš (oponent)
V práci se zabýváme dvou-dimenzionálními simpliciálními komplexy a lineárními kódy. Řekneme, že lineární kód C nad tělesem F je trojúhelníkově reprezentovatelný, pokud exis- tuje dvou-dimenzionální simpliciální komplex ∆ takový, že kód C je propíchnutým kódem jádra ker ∆ incidenční matice simpliciálního komplexu ∆ nad F a dim C = dim ker ∆. Tento simpliciální komplex nazveme geometrickou reprezentací kódu C. Dokážeme, že každý lineární kód nad prvotělesem je trojúhelníkově reprezentovatelný. Pro konečná prvotělesa sestrojíme geometrickou reprezentaci takovou, že váhový polynom kódu C je dán jednoduchou formulí váhového polynomu prostoru cyklů simpliciálního kom- plexu ∆. Tedy geometrická reprezentace kódu C určuje jeho váhový polynom. Naše motivace pochází z teorie pfaffiánovských orientací grafů, která poskytuje polyno- miální algoritmus pro výpočet váhového polynomu prostoru řezů grafu s omezeným rodem. Tento algoritmus využívá geometrických vlastností nakreslení grafu na orientovatelnou ri- emannovskou plochu. Prostor řezů je lineární kód a odpovídající graf je jeho užitečnou geometrickou reprezentací. Dále studujeme vnořitelnost geometrických reprezentací do euklidovských prostorů. Ukážeme, že každý binární lineární kód má geometrickou reprezentaci v R4 . Charakte- rizujeme binární lineární kódy, které...
|
host ::
RSS.