|
| |
|
|
Structural and complexity questions of graph theory
Gavenčiak, Tomáš ; Kratochvíl, Jan (vedoucí práce) ; Hliněný, Petr (oponent) ; Fomin, Fedor (oponent)
DIZERTAČNÍ PRÁCE Tomáš Gavenčiak Studium strukturálních a složitostních otázek teorie grafů Původní hra na četníky a zloděje, kterou roku 1983 navrhli Nowakowski a Winkler, a nezávisle Quilliot, je kombinatorická pronásledovací hra na grafech. Od té doby bylo navrženo a studováno mnoho podobných a příbuzných her, a to jak s čistě teoretickou motivací, tak pro jejich aplikace v teorii grafů a souvislosti s grafovými parametry. V práci předkládáme přehled této oblasti teorie her a bližší pozornost věnujeme následujícím třem výsledkům. Ukazujeme nová omezení na počet četníků nutných k polapení zloděje v několika typech průnikových grafů; speciálně ukazujeme, že na každém souvislém průnikovém grafu křivek vyhraje už 15 četníků. Dále představujeme polynomiální algoritmus rozhodující hru na četníky a rychlého zloděje na intervalových grafech a jako nástroj zobecňujeme problém defenzivní dominance a nabízíme pro něj polynomiální algoritmus na intervalových grafech. Nakonec navrhujeme a prozkou- máváme zobecnění stromové hloubky, her na maršály a zloděje a grafových minorů na hypergrafy a hypergrafové páry.
|
|
| |
|
|
Structural and complexity questions of graph theory
Gavenčiak, Tomáš ; Kratochvíl, Jan (vedoucí práce) ; Hliněný, Petr (oponent) ; Fomin, Fedor (oponent)
DIZERTAČNÍ PRÁCE Tomáš Gavenčiak Studium strukturálních a složitostních otázek teorie grafů Původní hra na četníky a zloděje, kterou roku 1983 navrhli Nowakowski a Winkler, a nezávisle Quilliot, je kombinatorická pronásledovací hra na grafech. Od té doby bylo navrženo a studováno mnoho podobných a příbuzných her, a to jak s čistě teoretickou motivací, tak pro jejich aplikace v teorii grafů a souvislosti s grafovými parametry. V práci předkládáme přehled této oblasti teorie her a bližší pozornost věnujeme následujícím třem výsledkům. Ukazujeme nová omezení na počet četníků nutných k polapení zloděje v několika typech průnikových grafů; speciálně ukazujeme, že na každém souvislém průnikovém grafu křivek vyhraje už 15 četníků. Dále představujeme polynomiální algoritmus rozhodující hru na četníky a rychlého zloděje na intervalových grafech a jako nástroj zobecňujeme problém defenzivní dominance a nabízíme pro něj polynomiální algoritmus na intervalových grafech. Nakonec navrhujeme a prozkou- máváme zobecnění stromové hloubky, her na maršály a zloděje a grafových minorů na hypergrafy a hypergrafové páry.
|
|
| |
host ::
RSS.