Please use this identifier to cite or link to this item: https://open.uns.ac.rs/handle/123456789/29038
DC FieldValueLanguage
dc.contributor.advisorStojaković Miloš-
dc.contributor.authorMikalački Mirjana-
dc.contributor.otherMašulović Dragan-
dc.contributor.otherStojaković Miloš-
dc.contributor.otherSzabó Tibor-
dc.contributor.otherVukobratović Dejan-
dc.date.accessioned2020-12-14T16:12:43Z-
dc.date.available2020-12-14T16:12:43Z-
dc.date.issued2014-02-20-
dc.identifier.urihttps://open.uns.ac.rs/handle/123456789/29038-
dc.description.abstract<p>\section*{Abstract}<br />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&gt;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&nbsp; \textit{Hamiltonicity game}, where the winning sets are the edge sets of all Hamilton cycles on $K_n$.<br /><br />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<br />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).<br />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$.&nbsp;&nbsp;</p><p>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&#39;s bias is 1, and Breaker&#39;s bias is $b, b\ge 1$.</p>en
dc.description.abstract<p>\section*{Izvod}</p><p>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\&#39;{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&gt;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\&#39;cu od 1. Na\v{s}a pa\v{z}nja je posve\&#39;{c}ena igri povezanosti, gde su pobedni\v{c}ki skupovi&nbsp; grane svih pokrivaju\&#39;cih stabala grafa $K_n$, kao i igri Hamiltonove konture, gde su pobedni\v{c}ki skupovi grane svih Hamiltonovih kontura grafa $K_n$.</p><p>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).<br />%$f^{mon}$, $f^-$ and $f^+$.<br />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}$.</p><p>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$.</p>sr
dc.language.isoen-
dc.publisherUniverzitet u Novom Sadu, Prirodno-matematički fakultet u Novom Sadusr
dc.publisherUniversity of Novi Sad, Faculty of Sciences at Novi Saden
dc.sourceCRIS UNS-
dc.source.urihttp://cris.uns.ac.rs-
dc.subjectPositional games on graphs, Maker-Breaker ga-mes, Avoider-Enforcer games, fast winning strategiesen
dc.subjectIgre na grafovima, Maker-Breaker igre, Avoider-Enforcer igre, brze pobedničke strategijesr
dc.titlePositional games on graphsen
dc.titlePozicione igre na grafovimasr
dc.typeThesisen
dc.identifier.urlhttps://www.cris.uns.ac.rs/DownloadFileServlet/Disertacija13956615938230.pdf?controlNumber=(BISIS)85754&fileName=13956615938230.pdf&id=1627&source=BEOPEN&language=enen
dc.identifier.urlhttps://www.cris.uns.ac.rs/record.jsf?recordId=85754&source=BEOPEN&language=enen
dc.identifier.externalcrisreference(BISIS)85754-
dc.source.institutionPrirodno-matematički fakultet u Novom Sadusr
item.grantfulltextnone-
item.fulltextNo Fulltext-
Appears in Collections:PMF Teze/Theses
Show simple item record

Page view(s)

14
Last Week
2
Last month
0
checked on May 10, 2024

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.