Název: Poziční hry s efektivní vítěznou strategií
Překlad názvu: Positional games with efficient winning strategy
Autoři: Svoboda, Jakub ; Šámal, Robert (vedoucí práce) ; Valla, Tomáš (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2017
Jazyk: cze
Abstrakt: [cze] [eng]
V práci zkoumáme hry, ve kterých dva hráči obarvují hrany nekonečného úplného grafu a snaží se vytvořit určitý, cílový, podgraf obarvený svou barvou. Nejprve se budeme uvažovat situaci, kdy cílový podgraf je úplným grafem a uká- žeme, že první hráč má vyhrávající strategii, když je cílový podgraf úplný graf na nejvýše třech vrcholech. Potom lehce změníme podmínky hry a ukážeme, že první hráč má vyhrávající strategii, pokud může omezit graf, na kterém se hraje, nebo zahrát několik tahů navíc. Nakonec budeme uvažovat hru, v níž musí být minorem cílového podgrafu úplný graf. Ukážeme vyhrávající strategii pro malou velikost úplného grafu, který musí být minorem cílového podgrafu a zamyslíme se nad důvody, proč by první hráč měl vyhrát jakoukoliv hru tohoto typu. 1 We study games where two players are coloring edges of infinite complete graph. Both players are trying to create given target subgraph colored by their colors. Firstly, we will look at situation when the target subgraph is a complete graph. We will show that first player has winning strategy if the target subgraph is complete graph on at most three vertices. Then we will slightly change the rules. This will help us show that the first player has a winning strategy if he can bound the size of the complete graph on which the game is played or he can color a few edges more then the opponent. At the end we will discuss game, when a complete graph of a given size is a minor of target subgraph. We will show a winning strategy for the first player and for small size of complete graph which is the minor of target subgraph. We also will discuss, why the first player should have winning strategy for all games of this type. 1
Klíčová slova: poziční hry;silné hry;efektivní strategie; positional games;strong games;efficient strategy

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/90444

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-365041


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce