|
| |
|
|
Intersection representations of graphs
Töpfer, Martin ; Jelínek, Vít (vedoucí práce) ; Pangrác, Ondřej (oponent)
V této diplomové práci zkoumáme podtřídy vnějškových (outer) a uzem- něných (grounded) string grafů. Stringem rozumíme omezenou spojitou křivku v rovině. Průniková reprezentace grafu pomocí stringů je množina stringů, kde každý string odpo- vídá jednomu vrcholu z původního grafu. Dva stringy se protínají právě tehdy, když mezi jejich odpovídajícími vrcholy vedla v původním grafu hrana. Graf je vnějškový string graf, pokud existuje jeho reprezentace, kde jsou všechny stringy uvnitř disku a každý string má jeden ze svých konců na hranici disku. Obdobně je graf uzemněný string graf, pokud existuje jeho reprezentace, ve které má každý string jeden svůj konec na společné přímce a zbytky všech stringů jsou na stejné straně od hraniční přímky. V diplomové práci uvádíme přehled tříd string grafů a dokazujeme několik tvrzení ohledně vzájemné inkluze těchto tříd. K tomu nám slouží lemma, díky kterému umíme předepisovat u vnějško- vých a uzemněných grafů pořadí, v jakém se vyskytují na hraniční přímce (resp. hraniční kružnici) konce jednotlivých stringů. V druhé části práce dokazujeme, že rozpoznávání vnějškových string grafů je NP-těžké. 1
|
|
|
Partial representation extension for subclasses of interval graphs
Onduš, Daniel ; Kratochvíl, Jan (vedoucí práce) ; Jelínek, Vít (oponent)
Problém rozširovania čiastočných reprezentácii pre intervalové grafy rozhoduje, či je možné reprezentáciu niekoľkých vrcholov rozšíriť na reprezentáciu celého grafu. V tejto práci nadviažeme na výsledok Klavíka a kol., ktorí dokázali, že REPEXT je pre triedy vlastných a jednotkových intervalových grafov rozhodnuteľný v po- lynomiálnom čase. Popíšeme vlastnosti PI± a U± grafov a ich reprezentácií, a predstavíme algorit- mus rozhodujúci REPEXT pre tieto triedy v polynomiálnom čase. V priebehu práce charakterizujeme vzťahy medzi indukovanými K1,3 v grafe a ukážeme že pre každý K1,3 vieme vybrať otvorený vrchol. Tiež definujeme pojmy reprezentácií rovnakých typov zoradenia a lokálne podobných reprezentácií ako aj vynútené a lokálne vynútené uzavreté (otvorené) intervaly. Tieto pojmy sú kľú- čové pri rozširovaní čiastočných reprezentácií tried intervalových grafov, ktoré pri- púšťajú rôzne typy intervalov v jednej reprezentácii. Charakterizujeme vynútené a lokálne vynútené uzavreté intervaly pre U± grafy použitím celočíselných me- dzier v predreprezentácii a skonštruujeme spodné odhady pre najpravejšie konce komponentov v polynomiálnom čase.
|
|
| |
|
|
Matice bez zakázaných intervalových minorů
Surma, David ; Jelínek, Vít (vedoucí práce) ; Klazar, Martin (oponent)
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. 1
|
|
|
Algorithmic aspects of intersection representations
Chmel, Petr ; Jelínek, Vít (vedoucí práce) ; Kratochvíl, Jan (oponent)
Jelikož některé problémy jsou v obecném případě (NP-)těžké, jedním z možných pří- stupů je řešení těchto problémů na omezené třídě grafů. V této práci se zaměřujeme na grafy indukované osově zarovnanými L-tvary, tzv. L-grafy, a podobnou třídu osově zarovnaných L-tvarů a L-tvarů, tzv. {L, L}-grafy, přičemž dva vrcholy jsou spojeny hra- nou, právě když se jejich křivky protínají. Dokazujeme, že rozpoznávání jak L-grafů, tak {L, L}-grafů je NP-úplné. V druhé části práce se zaměřujeme na další obvyklé rozhodovací problémy na L-grafech a příbuzných třídách: nalezení klikovosti, 3-obarvení či nezávislosti grafu.
|
|
|
Computational and structural apects of interval graphs and their variants
Novotná, Jana ; Kratochvíl, Jan (vedoucí práce) ; Jelínek, Vít (oponent)
Intervalové grafy, průnikové grafy úseček (intervalů) na reálné přímce, hrají klíčovou roli při studování algoritmů a specifických strukturálních vlastností. Velmi studovanou třídou jsou také jednotkové intervalové grafy, vlastní podtřída intervalových grafů, kde každý interval má jednotkovou délku. V práci se věnu- jeme smíšeným jednotkovým intervalovým grafům, grafům vzniklým zobecněním jednotkových intervalových grafů, kde každý interval má stále jednotkovou délku, ale může být různého typu (uzavřený, otevřený, polouzavřený). Tato drobná modi- fikace zahrnuje výrazně širší třídu grafů, například smíšené jednotkové intervalové grafy nejsou na rozdíl od jednotkových grafů spáruprosté. Heggernes, Meister a Papadopoulos přišli s bublinkovým modelem, takovou reprezentací jednotkových intervalových grafů, která se jeví užitečná při konstrukci různých algoritmů. Tento model rozšiřujeme na třídu smíšených intervalových grafů. Původní bublinkový model využili autoři Boyaci, Ekim a Shalom, kteří s jeho pomocí dokazovali, že problém největšího řezu v jednotkovém intervalovém grafu je polynomiální. V jejich důkazu jsme však objevili nejspíše neopravitelnou chybu. Dalším přínosem práce jsou ukázky využití našeho rozšířeného bublinkového mod- elu, na němž stavíme subexponenciální algoritmus pro problém největšího řezu...
|
|
|
Intersection representations of graphs
Töpfer, Martin ; Jelínek, Vít (vedoucí práce) ; Pangrác, Ondřej (oponent)
V této diplomové práci zkoumáme podtřídy vnějškových (outer) a uzem- něných (grounded) string grafů. Stringem rozumíme omezenou spojitou křivku v rovině. Průniková reprezentace grafu pomocí stringů je množina stringů, kde každý string odpo- vídá jednomu vrcholu z původního grafu. Dva stringy se protínají právě tehdy, když mezi jejich odpovídajícími vrcholy vedla v původním grafu hrana. Graf je vnějškový string graf, pokud existuje jeho reprezentace, kde jsou všechny stringy uvnitř disku a každý string má jeden ze svých konců na hranici disku. Obdobně je graf uzemněný string graf, pokud existuje jeho reprezentace, ve které má každý string jeden svůj konec na společné přímce a zbytky všech stringů jsou na stejné straně od hraniční přímky. V diplomové práci uvádíme přehled tříd string grafů a dokazujeme několik tvrzení ohledně vzájemné inkluze těchto tříd. K tomu nám slouží lemma, díky kterému umíme předepisovat u vnějško- vých a uzemněných grafů pořadí, v jakém se vyskytují na hraniční přímce (resp. hraniční kružnici) konce jednotlivých stringů. V druhé části práce dokazujeme, že rozpoznávání vnějškových string grafů je NP-těžké. 1
|
|
|
The complexity of constrained graph drawing
Hora, Martin ; Jelínek, Vít (vedoucí práce) ; Fink, Jiří (oponent)
Označkované nakreslení rovinného grafu G je uspořádaná dvojice (G, g) sklá- dající se z rovinného nakreslení G grafu G a z funkce g, jež přiřazuje popisky (barvy) jeho stěnám. V práci se zabýváme problémem Embedding Restriction Satisfiability (ERS), který řeší, zda má daný graf označkované nakreslení splňující předepsanou sadu podmínek. ERS je relativně nový problém, a tak se toho o něm zatím mnoho neví. Nicméně má velký potenciál. Zobecňuje totiž několik problémů hledajících specifická nakreslení grafů, jako je například problém částečně vno- řené rovinnosti (Partially Embedded Planarity). ERS se tedy může stát jedním z ústředích problémů v oblasti kreslení rovinných grafů. V této práci zkoumáme výpočetní složitost ERS. Jednak ukážeme, že ERS je NP-úplné, a poté vyšetříme složitost několika omezených verzí tohoto problému. Cílem je najít hranici mezi NP-těžkými a polynomiálními variantami. 1
|
|
|
Enumeration of polyomino fillings
Karpilovskij, Mark ; Jelínek, Vít (vedoucí práce) ; Klazar, Martin (oponent)
V práci dokazujeme dva nové výsledky o 0-1-vyplněních skew diagramů, které neobsahují dlouhé rostoucí a klesající řetězce. V první polovině práce ukážeme, že pro velkou třídu skew diagramů existuje bijekce mezi řídkými vyplněními bez rostoucího řetězce dané délky a řídkými vyplněními bez klesajícího řetězce stejné délky. Ve druhé polovině práce zobecníme známou nerovnost mezi počtem řídkých vyplnění skew diagramu bez rostoucího řetězce délky 2 a počtem řídkých vyplnění bez klesajícího řetězce délky 2 na všechna možná 0-1-vyplnění. 1
|
host ::
RSS.