Մաթեմատիկոսների միջազգային խումբը մշակել է ալգորիթմ, որը հնարավորություն է տալիս արդյունավետորեն գունավորելու ցանկացած քարտեզ՝ օգտագործելով առավելագույնը չորս գույն այնպես, որ հարևան շրջանները տարբեր գույներ ունենան։ Աշխատանքը նշանակալի առաջընթաց է հայտնի մաթեմատիկական խնդրի լուծման գործում, որի վրա հետազոտողները գլուխ են կոտրում 1852 թվականից։
Հետազոտությունն իրականացրել են Կոպենհագենի համալսարանի, Դանիայի տեխնիկական համալսարանի (DTU) և այլ գիտական հաստատությունների գիտնականները։ Արդյունքները հրապարակվել են arXiv նախատպությունների սերվերում։ Աշխատանքի առաջին մասը ներկայացվել է տեսական ինֆորմատիկայի FOCS 2026 միջազգային գիտաժողովում և արժանացել լավագույն հոդվածի մրցանակին։
Չորս գույնի խնդիրը ծագել է 1852 թվականին, երբ անգլիացի մաթեմատիկոս Ֆրենսիս Գաթրին նկատել է, որ Անգլիայի կոմսությունների քարտեզը գունավորելու համար իրեն բավականացրել է չորս գույն։ Նա ենթադրել է, որ այդ քանակը բավարար է ցանկացած քարտեզի համար՝ անկախ շրջանների թվից ու ձևից, եթե հարևան տարածքները պետք է տարբերվեն գույնով։
Առաջին ապացույցը հայտնվել է 1879 թվականին, սակայն 11 տարի անց դրանում սխալ է հայտնաբերվել։ Ամբողջական ապացույց հաջողվել է ստանալ միայն 1976 թվականին։ Այն վեճերի տեղիք է տվել, քանի որ մեծապես հիմնված էր համակարգչային հաշվարկների վրա, որոնք դժվար էր անկախ կերպով ստուգել։ 1997 թվականին մաթեմատիկոսներն առաջարկել են ավելի մատչելի ապացույց, սակայն համապատասխան ալգորիթմը մեծ քարտեզների դեպքում դանդաղ էր աշխատում։
Նոր ալգորիթմը չի փոխում չորս գույնի թեորեմն ինքնին, այլ լուծում է մեկ այլ խնդիր՝ հնարավորություն է տալիս ավելի արագ գտնելու գունավորման կոնկրետ տարբերակ։ Կոպենհագենի համալսարանի պրոֆեսոր Միկկել Թորուպը նշել է, թե նախկին ապացույցները հաստատում էին, որ չորս գույնով գունավորումը միշտ հնարավոր է, սակայն չէին ապահովում յուրաքանչյուր շրջանի գույնը որոշելու բավականաչափ արդյունավետ եղանակ։
Նոր արդյունքի բանալին գրաֆների կառուցվածքին առնչվող հայտնագործությունն էր։ Մաթեմատիկայում քարտեզը կարելի է ներկայացնել հարթ գրաֆի տեսքով՝ գագաթների և դրանք միացնող գծերի համակարգով, որը հարթության վրա տեղադրված է առանց հատումների։ Հետազոտողները պարզել են, որ այդպիսի գրաֆները պարունակում են շատ ավելի մեծ թվով, այսպես կոչված, բերվող կոնֆիգուրացիաներ, քան նախկինում կարծում էին։ Դրանք գրաֆի փոքր հատվածներ են, որոնք կարելի է օգտագործել որպես ելակետեր՝ գունավորումը կառուցելու համար։
«Պատկերացրեք, որ բերվող կոնֆիգուրացիաները բռնակներ են, որոնցից կարելի է բռնել՝ չորս գույնով գունավորումը սկսելու համար։ Մենք ցույց տվեցինք, որ գրաֆներն ունեն ոչ թե մեկ այդպիսի բռնակ, այլ զարմանալիորեն շատ»,- բացատրել է հետազոտության համահեղինակ, DTU-ի պրոֆեսոր Կարստեն Թոմասենը։
Դրա շնորհիվ ալգորիթմը կարող է աշխատանքը սկսել գրաֆի միանգամից բազմաթիվ հատվածներից և ավելի արդյունավետ մշակել մեծ քարտեզները։ Ըստ Թոմասենի՝ հաշվարկների բարդությունը հաջողվել է քառակուսայինից նվազեցնել գծայինի։ Սա նշանակում է, որ եթե քարտեզի շրջանների թիվը տասնապատկվի, հաշվարկների ժամանակը կավելանա մոտավորապես տասը, այլ ոչ թե հարյուր անգամ, ինչպես նախկին ալգորիթմի կիրառման դեպքում։
Հետազոտողները կարծում են, որ հայտնագործությունը կարող է օգտակար լինել նաև չորս գույնի դասական խնդրի շրջանակից դուրս։ Նոր մոտեցումը հնարավոր է կիրառել ավելի բարդ, ներառյալ՝ անցքեր ունեցող մակերևույթների հետ կապված գրաֆների, օրինակ՝ փրկօղակ կամ ծակոտկեն պանրի կտոր հիշեցնող մակերևույթների նկատմամբ։
Գիտնականներն ակնկալում են, որ բացահայտված օրինաչափությունները կօգնեն ուսումնասիրելու այլ գրաֆների կառուցվածքը և լուծելու ավելի բարդ մաթեմատիկական խնդիրներ։




























