Show simple item record

Pozicione igre na grafovima

dc.contributor.advisorStojaković, Miloš
dc.contributor.otherMašulović, Dragan
dc.contributor.otherStojaković, Miloš
dc.contributor.otherSzabó, Tibor
dc.contributor.otherVukobratović, Dejan
dc.creatorMikalački, Mirjana
dc.date.accessioned2015-12-29T11:17:21Z
dc.date.available2015-12-29T11:17:21Z
dc.date.available2020-07-03T13:43:13Z
dc.date.issued2014-02-20
dc.identifier.urihttp://www.cris.uns.ac.rs/DownloadFileServlet/Disertacija13956615938230.pdf?controlNumber=(BISIS)85754&fileName=13956615938230.pdf&id=1627&source=NaRDuS&language=srsr
dc.identifier.urihttp://nardus.mpn.gov.rs/handle/123456789/1712
dc.identifier.urihttp://www.cris.uns.ac.rs/record.jsf?recordId=85754&source=NaRDuS&language=srsr
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.languageen
dc.publisherУниверзитет у Новом Саду, Природно-математички факултетsr
dc.rightsopenAccessen
dc.sourceУниверзитет у Новом Садуsr
dc.subjectPositional games on graphsen
dc.subjectIgre na grafovimasr
dc.subjectMaker-Breaker ga-mesen
dc.subjectAvoider-Enforcer gamesen
dc.subjectfast winning strategiesen
dc.subjectMaker-Breaker igresr
dc.subjectAvoider-Enforcer igresr
dc.subjectbrze pobedničke strategijesr
dc.titlePositional games on graphsen
dc.titlePozicione igre na grafovimasr
dc.typedoctoralThesissr
dc.rights.licenseCC0
dcterms.abstractСтојаковић Милош; Машуловић Драган; Сзабó Тибор; Стојаковић Милош; Вукобратовић Дејан; Микалачки Мирјана; Позиционе игре на графовима; Позиционе игре на графовима;
dc.identifier.fulltexthttp://nardus.mpn.gov.rs/bitstream/id/38159/Disertacija.pdf


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record