Daug realaus gyvenimo uždavinių gali būti modeliuojami duomenų struktūra, vadinama grafu. Grafas yra sudarytas iš viršūnių aibės (dažnai žymimų taškais) ir šias viršūnes jungiančių briaunų (dažnai vaizduojamų linijomis) aibės. Įvairūs gyvenime kylantys uždaviniai – įvykių tvarkaraščių sudarymas ir paskyrimų planavimas – gali būti sprendžiami priskiriant skirtingas spalvas kiekvienai grafo viršūnei arba briaunai. Informatikos sritis, nagrinėjanti tokio tipo uždavinius, vadinama grafų spalvinimu.

Raktiniai žodžiai: grafai, grafų spalvinimas.

Teisingas atsakymas 3.

Turnyras gali būti vaizduojamas žemiau pateikta schema. Du bebrus jungianti linija rodo, kad šie bebrai žaidžia vienas su kitu. Aišku, kad nėra linija sujungtų dviejų bebrų, kurie galėtų sužaisti visus savo žaidimus (visą turnyrą) ta pačia rakete.

Problemą galima išspręsti kiekvieną bebrą spalvinant schemoje taip, kad jokie du linija sujungti bebrai nebūtų nuspalvinti ta pačia spalva. Viską pabaigus bebrai, kurie bus nuspalvinti ta pačia spalva, galės žaisti žaidimus ta pačia rakete. Be to, reikia numatyti mažiausią galimą spalvų skaičių, nes mums reikia rasti mažiausią teniso rakečių skaičių.

Bebrui Lukui galime priskirti pirmą spalvą, tarkim, raudoną. Kadangi Lukas linija sujungtas su Gabija, Kamile ir Matu, šiems bebrams turime priskirti kitas spalvas (t. y. ne raudoną). Priskirkime Gabijai antrą spalvą, pavyzdžiui, mėlyną. Matome, kad bebras Matas linija sujungtas ir su Luku (nuspalvintu raudonai), ir su Gabija (nuspalvinta mėlynai). Vadinasi, Matui reikia priskirti trečią spalvą – žalią. Nors Kamilė taip pat sujungta ir su Luku, ir su Gabija, bet nesujungta su Matu, todėl Kamilei galime priskirti tą pačią – žalią – spalvą kaip ir Matui. Bebras Joris linija sujungtas ir su Gabija (nuspalvinta mėlyna spalva), ir su Kamile (nuspalvinta žalia spalva), bet nėra sujungtas su Luku, kuriam priskirta raudona spalva. Vadinasi, Joriui galime priskirti tą pačią spalvą kaip Lukui – raudoną. Galų gale Paulina yra sujungta tik su Matu (nuspalvintas žalia spalva), todėl jai galime priskirti bet kurią spalvą iš esamų, išskyrus žalią. Vadinasi, tai gali būti mėlyna arba raudona.

Kadangi visiems bebrams nuspalvinti prireikė 3 spalvų, darome išvadą, kad turnyrui organizuoti užteks trijų rakečių: viena rakete dalysis Lukas ir Joris (raudona spalva), kita rakete – Matas ir Kamilė (žalia spalva), o trečią raketę naudos Gabija (mėlyna spalva). Paulina galės naudotis arba Luko ir Jorio rakete, arba Gabijos rakete.

Organizuoti turnyrą turint mažiau kaip tris raketes nepavyks, nes, pavyzdžiui, Lukas žaidžia su Matu, Matas žaidžia su Gabija, o Gabija – su Luku. Taigi, jei bus tik dvi raketės, vienas iš šių trijų žaidimų turės būti žaidžiamas ta pačia rakete, o tai neįmanoma.