Národní úložiště šedé literatury Nalezeno 2 záznamů.  Hledání trvalo 0.00 vteřin. 
Matching covers of cubic graphs
Slívová, Veronika ; Šámal, Robert (vedoucí práce) ; Rollová, Edita (oponent)
Hypotéza Berge a Fulkersona říká, že každý kubický graf bez mostů lze pokrýt šesti perfektními párováními tak, aby každá hrana byla obsažena právě ve dvou z nich. Další hypotéza od Berge říká, že každý kubický graf bez mostů lze pokrýt pomocí pěti perfektních párování. Obě hypotézy jsou zkoumány přes čtyřicet let. Abreu a kol. [2016] vytvořili novou třídu kubických grafů, zvanou treelike snarky a ukázali, že grafy z této třídy nemohou být pokryty méně než pěti perfektními párováními. My ukážeme, že jejich dolní odhad na počet perfektních párování je těsný. Bergovu domněnku dokonce dokážeme pro větší třídu grafů. Nakonec ukážeme, že také Berge-Fulkersonova hypotéza platí pro třídu treelike snarků.
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.

Viz též: podobná jména autorů
2 Slívová, Vladimíra
Chcete být upozorněni, pokud se objeví nové záznamy odpovídající tomuto dotazu?
Přihlásit se k odběru RSS.