|
|
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
|
|
|
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
|
|
|
Průnikové reprezentace grafů
Töpfer, Martin ; Jelínek, Vít (vedoucí práce) ; Šámal, Robert (oponent)
Průnikový graf je graf, ve kterém mezi dvěma vrcholy vede hrana, právě když jim odpovídající objekty se protínají. Tato práce se zabývá průnikovými grafy L-útvarů (tzv. L-grafy) a jejich speciálním případem, kdy konce všech L-útvarů jsou na jedné přímce (tzv. vnějškovými L-grafy). Po přehledu, co platí o L-grafech, používáme podobné postupy na vnějškové L-grafy. Ukážeme, že intervalové grafy, tětivové grafy (circular graphs) a vnějškově rovinné grafy jsou vnějškové L-grafy. Poté charakterizujeme vnějškové L-grafy pomocí uspořádání vrcholů bez zakázaných vzorů. Powered by TCPDF (www.tcpdf.org)
|
host ::
RSS.