Positional games on graphs
Pozicione igre na grafovima
dc.contributor.advisor | Stojaković, Miloš | |
dc.contributor.other | Mašulović, Dragan | |
dc.contributor.other | Stojaković, Miloš | |
dc.contributor.other | Szabó, Tibor | |
dc.contributor.other | Vukobratović, Dejan | |
dc.creator | Mikalački, Mirjana | |
dc.date.accessioned | 2015-12-29T11:17:21Z | |
dc.date.available | 2015-12-29T11:17:21Z | |
dc.date.available | 2020-07-03T13:43:13Z | |
dc.date.issued | 2014-02-20 | |
dc.identifier.uri | https://nardus.mpn.gov.rs/handle/123456789/1712 | |
dc.identifier.uri | http://www.cris.uns.ac.rs/DownloadFileServlet/Disertacija13956615938230.pdf?controlNumber=(BISIS)85754&fileName=13956615938230.pdf&id=1627&source=NaRDuS&language=sr | sr |
dc.identifier.uri | http://www.cris.uns.ac.rs/record.jsf?recordId=85754&source=NaRDuS&language=sr | sr |
dc.description.abstract | \section*{Abstract} We study Maker-Breaker games played on the edges of the complete graph on $n$ vertices, $K_n$, whose family of winning sets $\cF$ consists of all edge sets of subgraphs $G\subseteq K_n$ which possess a predetermined monotone increasing property. Two players, Maker and Breaker, take turns in claiming $a$, respectively $b$, unclaimed edges per move. We are interested in finding the threshold bias $b_{\cF}(a)$ for all values of $a$, so that for every $b$, $b\leq b_{\cF}(a)$, Maker wins the game and for all values of $b$, such that $b>b_{\cF}(a)$, Breaker wins the game. We are particularly interested in cases where both $a$ and $b$ can be greater than $1$. We focus on the \textit{Connectivity game}, where the winning sets are the edge sets of all spanning trees of $K_n$ and on the \textit{Hamiltonicity game}, where the winning sets are the edge sets of all Hamilton cycles on $K_n$. Next, we consider biased $(1:b)$ Avoider-Enforcer games, also played on the edges of $K_n$. For every constant $k\geq 3$ we analyse the $k$-star game, where Avoider tries to avoid claiming $k$ edges incident to the same vertex. We analyse both versions of Avoider-Enforcer games, the strict and the monotone, and for each provide explicit winning strategies for both players. Consequentially, we establish bounds on the threshold biases $f^{mon}_\cF$, $f^-_\cF$ and $f^+_\cF$, where $\cF$ is the hypergraph of the game (the family of target sets). We also study the monotone version of $K_{2,2}$-game, where Avoider wants to avoid claiming all the edges of some graph isomorphic to $K_{2,2}$ in $K_n$. Finally, we search for the fast winning strategies for Maker in Perfect matching game and Hamiltonicity game, again played on the edge set of $K_n$. Here, we look at the biased $(1:b)$ games, where Maker's bias is 1, and Breaker's bias is $b, b\ge 1$. | en |
dc.description.abstract | \section*{Izvod} Prou\v{c}avamo takozvane Mejker-Brejker (Maker-Breaker) igre koje se igraju na granama kompletnog grafa sa $n$ \v{c}vorova, $K_n$, \v{c}ija familija pobedni\v{c}kih skupova $\cF$ obuhvata sve skupove grana grafa $G\subseteq K_n$ koji imaju neku monotono rastu\'{c}u osobinu. Dva igra\v{c}a, \textit{Mejker} (\textit{Pravi\v{s}a}) i \textit{Brejker} (\textit{Kva\-ri\-\v{s}a}) se smenjuju u odabiru $a$, odnosno $b$, slobodnih grana po potezu. Interesuje nas da prona\dj emo grani\v{c}ni bias $b_{\cF}(a)$ za sve vrednosti pa\-ra\-me\-tra $a$, tako da za svako $b$, $b\le b_{\cF}(a)$, Mejker pobe\dj uje u igri, a za svako $b$, takvo da je $b>b_{\cF}(a)$, Brejker pobe\dj uje. Posebno nas interesuju slu\v{c}ajevi u kojima oba parametra $a$ i $b$ mogu imati vrednost ve\'cu od 1. Na\v{s}a pa\v{z}nja je posve\'{c}ena igri povezanosti, gde su pobedni\v{c}ki skupovi grane svih pokrivaju\'cih stabala grafa $K_n$, kao i igri Hamiltonove konture, gde su pobedni\v{c}ki skupovi grane svih Hamiltonovih kontura grafa $K_n$. Zatim posmatramo igre tipa Avojder-Enforser (Avoider-Enforcer), sa biasom $(1:b)$, koje se tako\dj e igraju na granama kompletnog grafa sa $n$ \v{c}vorova, $K_n$. Za svaku konstantu $k$, $k\ge 3$ analiziramo igru $k$-zvezde (zvezde sa $k$ krakova), u kojoj \textit{Avojder} poku\v{s}va da izbegne da ima $k$ svojih grana incidentnih sa istim \v{c}vorom. Posmatramo obe verzije ove igre, striktnu i monotonu, i za svaku dajemo eksplicitnu pobedni\v{c}ku strategiju za oba igra\v{c}a. Kao rezultat, dobijamo gornje i donje ograni\v{c}enje za grani\v{c}ne biase $f^{mon}_\cF$, $f^-_\cF$ i $f^+_\cF$, gde $\cF$ predstavlja hipergraf igre (familija ciljnih skupova). %$f^{mon}$, $f^-$ and $f^+$. Tako\dj e, posmatramo i monotonu verziju $K_{2,2}$-igre, gde Avojder \v{z}eli da izbegne da graf koji \v{c}ine njegove grane sadr\v{z}i graf izomorfan sa $K_{2,2}$. Kona\v{c}no, \v{z}elimo da prona\dj emo strategije za brzu pobedu Mejkera u igrama savr\v{s}enog me\v{c}inga i Hamiltonove konture, koje se tako\dj e igraju na granama kompletnog grafa $K_n$. Ovde posmatramo asimetri\v{c}ne igre gde je bias Mejkera 1, a bias Brejkera $b$, $b\ge 1$. | sr |
dc.language | en | |
dc.publisher | Универзитет у Новом Саду, Природно-математички факултет | sr |
dc.rights | openAccess | en |
dc.rights.uri | https://creativecommons.org/share-your-work/public-domain/cc0/ | |
dc.source | Универзитет у Новом Саду | sr |
dc.subject | Positional games on graphs | en |
dc.subject | Igre na grafovima | sr |
dc.subject | Maker-Breaker ga-mes | en |
dc.subject | Avoider-Enforcer games | en |
dc.subject | fast winning strategies | en |
dc.subject | Maker-Breaker igre | sr |
dc.subject | Avoider-Enforcer igre | sr |
dc.subject | brze pobedničke strategije | sr |
dc.title | Positional games on graphs | en |
dc.title | Pozicione igre na grafovima | sr |
dc.type | doctoralThesis | en |
dc.rights.license | CC0 | |
dcterms.abstract | Стојаковић Милош; Машуловић Драган; Сзабó Тибор; Стојаковић Милош; Вукобратовић Дејан; Микалачки Мирјана; Позиционе игре на графовима; Позиционе игре на графовима; | |
dc.identifier.fulltext | https://nardus.mpn.gov.rs/bitstream/id/38159/Disertacija.pdf | |
dc.identifier.fulltext | http://nardus.mpn.gov.rs/bitstream/id/38159/Disertacija.pdf | |
dc.identifier.rcub | https://hdl.handle.net/21.15107/rcub_nardus_1712 |