Igra ugibanja barve klobukaTurk, Rene (Avtor) Iršič Chenoweth, Vesna (Mentor) Marc, Tilen (Komentor) igra ugibanja barve klobukateorija grafovgraf vidnostizmagovalna strategijaparameter $HG$parameter $H_k$kaktusvetrnični grafV 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.20262026-09-12 08:15:30Delo diplomskega seminarja/zaključno seminarsko delo/naloga187629UDK: 519.17:519.8VisID: 163681COBISS_ID: 292016643sl