20.500.12556/RUL-187629 Igra ugibanja barve klobuka delo diplomskega seminarja Hat guessing game V nalogi preučujemo igro ugibanja barve klobuka na grafih. Igralci so predstavljeni z vozlišči grafa, povezave pa določajo, kateri igralci se med seboj vidijo. Pred začetkom igre se igralci dogovorijo za deterministično strategijo, nato pa nasprotnik, ki strategijo pozna, vsakemu igralcu dodeli klobuk ene izmed možnih barv. Vsak igralec vidi barve klobukov svojih sosedov, ne vidi pa svoje barve. Igralci skušajo uganiti barvo svojega klobuka. Uspešnost strategij merimo s parametroma $H_k$ in $HG$. Parameter $H_k$ pove, koliko pravilnih odgovorov lahko igralci zagotovijo pri $k$ barvah, parameter $HG$ pa je največje število barv, pri katerem lahko igralci še zagotovijo vsaj en pravilen odgovor. V nalogi pokažemo, da za poln graf $K_n$ velja $H_k(K_n)=\lfloor \frac{n}{k} \rfloor$ in $HG(K_n)=n$. Za poljubne neusmerjene grafe pri dveh barvah predstavimo izrek, po katerem je $H_2(G)$ enak velikosti največjega prirejanja v grafu. Nato izpeljemo nekaj osnovnih spodnjih in zgornjih mej za parameter $HG$ ter predstavimo znane klasifikacije za izbrane družine grafov. Za drevesa velja $HG(T)=2$, pri ciklih pa je $HG(C_n)=3$ natanko tedaj, ko je $n=4$ ali $3 \mid n$; sicer je $HG(C_n)=2$. Obravnavamo tudi kaktuse in vetrnične grafe, kjer lahko parameter $HG$ doseže višje vrednosti. Na koncu pa opišemo še nekaj različic igre in navedemo izbrana odprta vprašanja. In this thesis, we study the hat guessing game on graphs. The players are represented by the vertices of a graph, and the edges determine which players can see each other. Before the game starts, the players agree on a deterministic strategy. Then an adversary, who knows the strategy, assigns each player a hat of one of the possible colors. Each player sees the colors of the hats worn by their neighbors, but not the color of their own hat. The players try to guess their own hat color. We measure the performance of strategies by the parameters $H_k$ and $HG$. $H_k$ gives the number of correct guesses the players can guarantee with $k$ colors, while $HG$ is the largest number of colors for which they can still guarantee at least one correct guess. We show that for the complete graph $K_n$ we have $H_k(K_n)=\lfloor \frac{n}{k} \rfloor$ and $HG(K_n)=n$. For arbitrary undirected graphs with two colors, we present a theorem stating that $H_2(G)$ is equal to the size of a maximum matching in the graph. We then derive some basic lower and upper bounds for the parameter $HG$ and present known classifications for selected families of graphs. For trees, we have $HG(T)=2$. For cycles, $HG(C_n)=3$ if and only if $n=4$ or $3 \mid n$; otherwise, $HG(C_n)=2$. We also discuss cactus graphs and windmill graphs, where the parameter $HG$ can take larger values. Finally, we describe a few variants of the game and list some selected open problems. igra ugibanja barve klobuka teorija grafov graf vidnosti zmagovalna strategija parameter $HG$ parameter $H_k$ kaktus vetrnični graf hat guessing game graph theory visibility graph winning strategy hat guessing number hat number cactus graph windmill graph true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2026-09-12 08:15:30 2026-09-12 08:15:33 2026-09-22 13:23:48 0000-00-00 00:00:00 2026 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17:519.8 163681 292016643 24368.pdf 24368.pdf 1 0D955E2EF2CECD5C63F0DF0DEC7AC03C e05459096c189a9d5ad3c5956b7617fe2e470ef831600862b6efb041cbaac920 55ad275f-ae71-11f1-8bc5-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=247329 Fakulteta za matematiko in fiziko 0 0 0