Original title: Poziční hry s efektivní vítěznou strategií
Translated title: Positional games with efficient winning strategy
Authors: Svoboda, Jakub ; Šámal, Robert (advisor) ; Valla, Tomáš (referee)
Document type: Bachelor's theses
Year: 2017
Language: cze
Abstract: [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
Keywords: positional games;strong games;efficient strategy; poziční hry;silné hry;efektivní strategie

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/90444

Permalink: http://www.nusl.cz/ntk/nusl-365041


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses