|
| |
|
|
Hry na grafech ve vztahu k zdvihovým parametrům grafů
Gavenčiak, Tomáš ; Smrž, Otakar (oponent) ; Kratochvíl, Jan (vedoucí práce)
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í.
|
|
|
On-line algoritmy barvení bipartitních grafů
Chludil, Josef ; Gavenčiak, Tomáš (oponent) ; Pangrác, Ondřej (vedoucí práce)
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.
|
host ::
RSS.