Matematikai pristatė spartesnį keturių spalvų teoremos spalvinimo algoritmą
Tarptautinė mokslininkų komanda pranešė radusi, jų teigimu, optimalų algoritmą keturių spalvų uždaviniui. Jis leidžia gerokai greičiau rasti spalvinimą, kai gretimos sritys negali būti nuspalvintos ta pačia spalva.
Keturių spalvų teorema teigia, kad bet kokiam žemėlapiui pakanka keturių spalvų, jei kaimyninės sritys turi skirtis. Šios idėjos ištakos siekia 1852 metus, kai anglų matematikas Francis Guthrie, spalvindamas Anglijos grafysčių žemėlapį, pastebėjo, kad jam pakanka keturių spalvų.
Tačiau įrodyti tai pasirodė labai sunku. 1879 metais paskelbtas pirmasis įrodymas vėliau buvo pripažintas klaidingu – klaida jame aptikta po 11 metų. 1976 metais pasirodęs įrodymas sukėlė diskusijų, nes rėmėsi labai didelės apimties kompiuteriniais skaičiavimais, kuriuos kitiems buvo sunku patikrinti. Aiškesnis variantas pasirodė 1997 metais, tačiau jis, nors ir gebėjo rasti spalvinimą, dideliems žemėlapiams veikė lėtai.
Naujasis metodas remiasi planarinių grafų aprašymu. Kad būtų galima pradėti spalvinimą, reikia nedidelės ypatingos struktūros – vadinamosios suvedamos konfigūracijos. Tyrėjai jas lygina su savotiškomis rankenomis, už kurių galima užsikabinti pradedant sprendimą.
Anksčiau dažnai pavykdavo rasti tik vieną tokią vietą. Dabar, pasak komandos, paaiškėjo, kad grafuose jų yra stebėtinai daug, todėl spalvinimą galima pradėti iš kelių vietų vienu metu. Būtent tai ir duoda didžiausią pagreitėjimą.
Ankstesnis algoritmas veikė kvadratiniu laiku: jei sričių skaičius padidėdavo 10 kartų, skaičiavimai trukdavo maždaug 100 kartų ilgiau. Naujasis algoritmas veikia tiesiniu laiku, todėl 10 kartų didesniam sričių skaičiui reikia maždaug 10 kartų daugiau laiko.
Komanda prie šios problemos dirbo apie dešimtmetį. Tyrėjai šį uždavinį net vadina „keturių spalvų liga“ – taip apibūdinamas įsitikinimas, kad tokios paprastos formuluotės teiginys turėtų turėti ir paprastą įrodymą.

