velikost textu

Průnikové reprezentace grafů

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Průnikové reprezentace grafů
Typ:
Diplomová práce
Autor:
Bc. Martin Töpfer
Vedoucí:
RNDr. Vít Jelínek, Ph.D.
Oponent:
RNDr. Ondřej Pangrác, Ph.D.
Id práce:
180912
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Informatický ústav Univerzity Karlovy (32-IUUK)
Program studia:
Informatika (N1801)
Obor studia:
Diskrétní modely a algoritmy (IDMA)
Přidělovaný titul:
Mgr.
Datum obhajoby:
11. 6. 2019
Výsledek obhajoby:
Výborně
Jazyk práce:
Angličtina
Klíčová slova:
outerstring graf, NP-těžkost, grounded reprezentace, průnikový graf, průniková reprezentace
Klíčová slova v angličtině:
outerstring graph, NP-hardness, grounded representation, intersection graph, intersection representation
Abstrakt:
Abstrakt: 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
Abstract v angličtině:
Abstract: This thesis is devoted to the outer and grounded string representations of graphs and their subclasses. A string representation of a graph is a set of strings (bounded continuous curves in a plane), where each string corresponds to one vertex of the graph. Two strings intersect each other if and only if the two corresponding vertices are adjacent in the original graph. An outer string graph is a graph with a string representation where strings are realized inside a disk and one endpoint of each string lies on the boundary of the disk. Similarly, in case of grounded string graphs the strings lie in a common half- plane with one endpoint of each string on the boundary of the half-plane. We give a summary of subclasses of grounded string graphs and proves several results about their mutual inclusions and separations. To prove those, we use an order-forcing lemma which can be used to force a particular order of the endpoints of the string on the boundary circle or boundary line. The second part of the thesis contains proof that recognition of outer string graphs is NP-hard. 1
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce Bc. Martin Töpfer 1.1 MB
Stáhnout Abstrakt v českém jazyce Bc. Martin Töpfer 63 kB
Stáhnout Abstrakt anglicky Bc. Martin Töpfer 76 kB
Stáhnout Posudek vedoucího RNDr. Vít Jelínek, Ph.D. 86 kB
Stáhnout Posudek oponenta RNDr. Ondřej Pangrác, Ph.D. 142 kB
Stáhnout Záznam o průběhu obhajoby prof. RNDr. Luděk Kučera, DrSc. 152 kB