|
|
On-line algoritmy barvení bipartitních grafů
Chludil, Josef ; Pangrác, Ondřej (vedoucí práce) ; Gavenčiak, Tomáš (oponent)
Instancí problému on-line barvení grafu je graf a pořadí jeho vrcholů, algoritmus potom barví popořadě vrcholy a jako informaci zná graf indukovaný předchozími vrcholy. Přirozeným algoritmem je First Fit, který obarví vrchol první přípustnou barvou. Tento algoritmus má ale slabiny, poměr mezi nalezeným a optimálním řešením může být až lineární vzhledem k počtu vrcholů grafu, a to i pro grafy bipartitní. Pro ty je ale znám algoritmus s logaritmickým aproximačním faktorem.
|
|
|
Hry na grafech
Gavenčiak, Tomáš ; Kratochvíl, Jan (vedoucí práce) ; Pergel, Martin (oponent)
V této práci studujeme některé vlastnosti jedné hry typu cop&robber, při které se dva hráči - Policista (Cop) a Lupič (Robber) - střídají v tázích na konečném neorientovaném grafu. Oba hráči se pohybují rychlostí nanejvýš jedna hrana za tah a znají v každém okamžiku celý stav hry. Pokud se Policista kdykoli ocitne na stejném poli jako Lupič, vyhraje Policista. Pokud k tomuto nikdy nedojde, vyhrává Lupič. Hry tohoto typu jsou důležité jako modely prohledávání grafu i pro svou souvislost s invarianty zdvihu grafu. Zabýváme se blíže vlastnostmi grafů, na kterých existuje výherní strategie pro Policistu (tzv. cop-win grafy), a hledáním nejlepších strategií pro oba hráče. Již dříve bylo známo, že počet tahů, za který je Policista schopen vyhrát na jakémkoli cop-win grafu na n vrcholech je zhora omezen n 3, a existují grafy vyžadující n 4. V této práci ukazujeme, že tento počet je právě n 4.
|
|
| |
|
|
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.
|
|
|
Hry na grafech ve vztahu k zdvihovým parametrům grafů
Gavenčiak, Tomáš ; Kratochvíl, Jan (vedoucí práce) ; Smrž, Otakar (oponent)
V práci se zabýváme variantou tzv. hry na četníky a zloděje s nekonečně rychlým zlodějem a jejími vztahy s ostatními podobnými hrami. Srovnáváme tzv. vrtulníkovou hru charakterizující tree-width, klasickou verzi hry na četníky a zloděje a varianty s různě rychlými zloději. U varianty s nekonečně rychlým zlodějem rozebíráme její složitost a charakterizujeme všechny grafy, kde vyhrává jeden četník. Jako hlavní výsledek ukazujeme polynomiální algoritmus rozhodující hru na intervalových grafech a zodpovídáme tak otevřenou otázku z článku Fomin a kol.: On tractability of Cops and Robbers game, IFIP TCS 2008, 171-185. V důkazu polynomiality rozhodovacího problému zavádíe novou, ekvivalentní pomocnou hru na intervalové reprezentaci grafu, o jejímž rozhodování ukážeme, že je polynomiální. Ekvivalence her je dokázána technikou redukcí herních strategií.
|
|
|
Compact I/O-Efficient Graph Representations
Tětek, Jakub ; Gavenčiak, Tomáš (vedoucí práce) ; Mareš, Martin (oponent)
Cílem této práce je vyvinout rychlou pamět'ově efektivní reprezentaci někte- rých grafů, které se vyskytují v praktických problémech. Uvažujeme separovatelné třídy grafů (např. rovinné grafy nebo grafy s ome- zeným rodem) a ukazujeme, jak grafy z takových tříd reprezentovat způsobem, který (1) dovoluje v průměru I/O-efektivní přístup k vrcholům při procházce a (2) používá málo paměti. Konkrétně ukazujeme kompaktní reprezentaci grafů ze separovatelných tříd s počtem I/O-přístupů při náhodné procházce délky k rovným O(K/(Bw)1−c ) s vysokou pravděpodobností. V druhé části práce se zabýváme rozložením vrcholů stromu v paměti. Uka- zujeme rozložení, které má optimální počet I/O-přístupů v nejhorším případě při procházení z kořene do listu. Dále ukazujeme aditivní (+1)-aproximaci op- timálního kompaktního rozložení vrcholů a dáváme tento výsledek do kontrastu s důkazem NP-těžkosti přesného řešení. Dále v této práci dokazujeme zobecnění věty o rekurzivních separátorech. První zobecnění rozšiřuje větu pro vážené grafy a druhé zobecnění nahrazuje ve znění věty minimální velikost regionu za průměrnou velikost. 1
|
|
|
Výměna směrovacích informací
Čepelík, David ; Mareš, Martin (vedoucí práce) ; Gavenčiak, Tomáš (oponent)
V práci představujeme efektivní způsob serializace složitých objektů do úsporné binární reprezen- tace vycházející z Concise Binary Object Representation (CBOR). Součástí práce je výkonná a dobře otestovaná knihovna pro serializaci dat a její implementace v programu BIRD Internet Routing Daemon. 1
|
|
|
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.
|
|
|
Optimisation using graph searching on special graph classes
Chejnovská, Anna ; Gavenčiak, Tomáš (vedoucí práce) ; Šámal, Robert (oponent)
Pro graf definujeme minimální pokrytí cestami jako nejmenší množinu vrcholově disjunktních cest, které pokrývají všechny vrcholy grafu. Tento problém je jedním z běžných zobecnění známého problému hledání Hamiltonovské cesty v grafu. V této práci vyjdeme ze článku Corneil et al. (2013), kde byl představen certifikující algoritmus pro hledání minimálního pokrytí cestami na cocomparability grafech (doplněk grafu relace neostrého částečného uspořádání). Tento algoritmus nejprve představíme, poté experimentálně prozkoumáme jeho robustnost vůči pěti operacím na hranách a vrcholech. Dopad těchto operací na velikost minimálního pokrytí cest rozebereme také teoreticky. Powered by TCPDF (www.tcpdf.org)
|
|
|
Cops and robber game on directed complete graphs
Slívová, Veronika ; Gavenčiak, Tomáš (vedoucí práce) ; Jelínek, Vít (oponent)
BAKALÁŘSKÁ PRÁCE - ABSTRAKT Veronika Slívová Tato práce se zabývá hrou Cops and robber (četníci a zloděj) na turnajích (graf vzniklý zorientováním hran úplného grafu). Ukážeme, že na polapení zloděje stačí málo četníků, pokud turnaj obsahuje vrchol vysokého výstupního stupně. Naopak počet četníků potřebný k polapení zloděje na libovolném turnaji nelze omezit. Dále se práce zabývá cirkulárními turnaji a turnaji vzniklými cyklickou orientací každé trojice ze Steinerovského systému trojic. Vyvrátíme domněnku Geňi Hahna, že počet četníků potřebný k polapení zloděje na libovolném grafu, který vznikl orientací Steinerovského systému trojic, je omezený. Dokážeme, že k polapení zloděje na libovolném cirkulárním turnaji, potřebujeme také neomezený počet četníků. Prozkoumáme i variantu 2-rychlého četníka, který vyhraje hru na libovolném turnaji prvním tahem. Naopak na turnajích s vrcholy stejného výstupního stupně je 2-rychlý zloděj polapitelný triviálně nebo jej nelze chytit.
|
host ::
RSS.