Studentski seminar, 11. mart 2022.

Naredni sastanak Seminara biće održan onlajn u petak 11. marta 2022. sa početkom u 12 časova.

Predavač: Strahinja Gvozdić, Fakultet prirodnih nauka u Orseju, Univerzitet Pariz-Sakle


Naslov predavanja: IGRA POGAĐANjA ŠEŠIRA NA GRAF


Detaljnije:
Igra pogađanja šešira na grafu podrazumeva neki graf  G u čijim čvorovima stoje ljudi na čije se glave postavljaju šeširi u nekoj od  q mogućih boja. Svaka osoba može da vidi samo boje šešira ljudi u susednim čvorovima i ne može da vidi svoju boju šešira. Potrebno je naći strategiju po kojoj svaka osoba može pogađati svoju boju šešira isključivo na osnovu boja šešira koje vidi, te koja nam garantuje da će pri svakom izboru boja barem jedna osoba tačno pogoditi svoju boju šešira. Najveće  q za koje postoji takva strategija naziva se HG-brojem grafa. U toku predavanja ćemo predstaviti neke osnovne rezultate o ovom grafovskom svojstvu i  pokazaćemo koje se grupe čvorova mogu obrisati iz datog grafa bez promene HG-broja. Uvešćemo i hromatsku varijaciju igre, u kojoj se  garantuje da su boje susednih čvorova različite, i pokazati da je ovde HG-broj kompletnog grafa na  n  čvorova dat sa 2n-1.

Link za pristup predavanju je
https://miteam.mi.sanu.ac.rs/asset/CihYM6Nratzix7c8G

Link za registraciju korisnika grupe Studentski seminar je
https://miteam.mi.sanu.ac.rs/asset/M4zcEwxkzy5PqNS73


 Ostavite vaš komentar 

Komentari(0)

Nažalost nije moguće ostaviti komentar.