Gyorsabb eljárást dolgoztak ki a négyszín-tétel gyakorlati megoldására
A négyszín-tétel gyakorlati alkalmazásában ért el jelentős áttörést egy nemzetközi matematikuscsoport, amelynek eredményét az idei Foundations of Computer Science, vagyis FOCS konferencián ismertették. A tízéves kutatás Mikkel Thorup, a Koppenhágai Egyetem számítógéptudósa, valamint Carsten Thomassen, a Dán Műszaki Egyetem matematikusa és kollégáik nevéhez fűződik. A tétel alapját Francis Guthrie vetette fel 1852-ben: bármely, egyértelmű határokkal felosztott síkbeli térkép régiói legfeljebb négy színnel kiszínezhetők úgy, hogy a közös határral érintkező területek különböző színűek legyenek.
A probléma első bizonyítása 1879-ben még hibásnak bizonyult, a teljes megoldásra pedig 1976-ig kellett várni. Ez volt az első jelentős matematikai tétel, amelyet számítógépes program igazolt, az eljárás azonban olyan összetett és terjedelmes volt, hogy nehezen lehetett emberileg ellenőrizni. Az 1997-es átláthatóbb változat sem oldotta meg a gyakorlati gondot: az algoritmus a térképek méretének növekedésével jelentősen lelassult.
Az új módszer a térképeket síkgráfként kezeli, és a kutatók által felfedezett matematikai összefüggésnek köszönhetően sokkal több „kicsinyíthető alakzatot” vagy kiindulási pontot talál. Így a négyszínezés több részterületen párhuzamosan kezdhető meg. Az eljárás a korábbi négyzetes idő helyett lineáris időben működik: tízszer nagyobb térkép esetén nem százszorosára, hanem körülbelül tízszeresére nő a számítási idő. Az algoritmus különleges, lyukakkal rendelkező felületeken is alkalmazható, és később a gráfelmélet mellett telekommunikációs hálózatok tervezésében vagy erőforrás-allokációs problémákban is hasznos lehet.