Ši užduotis – tai gerai žinomas matematikos uždavinys, vadinamoji keturių spalvų teorema. Ja teigiama, kad bet koks dvimatis paveikslas, padalintas į sritis, pavyzdžiui, žemėlapis, gali būti nuspalvintasne daugiau kaip keturiomis spalvomis, laikantis taisyklės, kad jokios dvi bendrą kraštinę turinčios sritys negali būti nuspalvintos ta pačia spalva.

Keturių spalvų teorema turi daug taikymų informatikoje. Pavyzdžiui, planuojant skrydžius ir skirstant pakilimo ir tūpimo takus, kad būtų išvengta susidūrimų, parenkant mobiliųjų tinklų dažnius.

https://en.wikipedia.org/wiki/Four_color_theorem

Raktiniai žodžiai: keturių spalvų teorema, grafas.

Atsakymas: 3.

Galimi įvairūs sprendimai priklausomai nuo to, kokia spalva pradedama spalvinti ir kuri sritis pirmiausia pasirenkama spalvinti. Pateikiamas sprendimas, kai pasirenkama pirmoji spalva ir stengiamasi nuspalvinti kiek galima daugiau sričių, pradedant nuo viršutinio kairiojo kampo:

Antrąja spalva spalvinama, pradedant nuo apatinio kairiojo kampo:

Paėmę trečiąją spalvą, matome, kad galime nuspalvinti visas likusias sritis, ir dvi bendrą kraštinę turinčios sritys nebus tos pačios spalvos:

Tai rodo, kad trijų spalvų pakanka. Toliau reikia įsitikinti, kad negalime nuspalvinti šio paveikslo naudodami mažiau nei tris spalvas. Imkime x pažymėtą geltoną sritį: ji turi bendrų kraštinių su dviem sritimis, taigi turime 3 sritis, ir visos jos turi būti skirtingų spalvų. Vadinasi, neįmanoma šio paveikslo nuspalvinti, naudojant mažiau nei tris spalvas.