|
|
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
|
|
|
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.
|
|
|
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
|
host ::
RSS.