Kosmosas 2026 11 20 2 min. skaitymo

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ą.

Sekanti naujiena
Etnos ugnikalnis išleido retą dūmų žiedą
Kosmosas

Etnos ugnikalnis išleido retą dūmų žiedą

1 min. skaitymo

Skaityti →
Verta perskaityti
Featured Kvadratine
Straipsnis

Tavo telefonas tave stebi. Visada.

Du tėčiai nusiuntė medikams savo sūnų nuotraukas ir prarado viską - paskyras, laiškus, net telefono numerį. Jų nusikaltimas?…

9 min. skaitymo

Skaityti straipsnį →

Mūsų svetainėje nėra reklamų ir slapukų. Patinka turinys? Padėkite mums augti – pasidalinkite su draugais!

Atgal

Nustatymai

Ką rodyti pagrindiniame puslapyje?

Pasirinkimai įsimenami šioje naršyklėje.

Pranešimai

Tikrinama, ar šiame įrenginyje galima įjungti pranešimus...

Privatumo informacija
Į pagrindinį srautą

Kategorijos

Trumpam pakeiskite temą. Jūsų nustatymai išliks.

Įsidiekite programėlę

Įsidiekite „Pasaulio naujoves“ ir skaitykite naujienas tiesiogiai programėlėje.

Pasaulio naujovių programėlės ikona

Kur rasti programėlę?Įdiegę grįžkite į telefono ar planšetės pradžios ekraną. Raskite „Pasaulio naujovės“ ikoną ir paspauskite ją.

Programėlėje galėsite pasirinkti, ką skaityti. Naujienoms reikalingas internetas.

Jau esate programėlėje

Skaitykite naujienas čia, o kitą kartą programėlę atverkite paspaudę „Pasaulio naujovės“ ikoną savo įrenginio pradžios ekrane.

Pasirinkite, ką norite skaityti. Pasirinkimai išliks šiame įrenginyje.

Nustatymuose galite įjungti naujienų suvestines kartą arba du kartus per dieną.