Danske forskere løser 174 år gammel matematisk gåde med ny algoritme

Kan ethvert landkort farvelægges med højst fire farver, uden at lande, der grænser op til hinanden, får samme farve? Det spørgsmål har optaget matematikere siden 1852. Nu har et internationalt forskerhold, herunder de danske professorer Mikkel Thorup og Carsten Thomassen, fundet en effektiv algoritme, der kan løse problemet.

Professorerne Carsten Thomassen, Ken-ichi Kawarabayashi, Mikkel Thorup og Bojan Mohar under et møde på Københavns Universitet i september 2026. Foto: Mikkel Thorup
Firefarveproblemet blev oprindeligt formuleret af den engelske matematiker Francis Guthrie. Selvom det i 1976 blev bevist, at alle landkort kan farvelægges med højst fire farver, har det været vanskeligt at udvikle en effektiv metode til rent faktisk at finde farverne.
Den nye algoritme gør beregningerne markant hurtigere. Forskerne er gået fra en metode med kvadratisk tidsforbrug til lineær tid, hvilket betyder, at beregningstiden vokser proportionalt med kortets størrelse.
”Vi er gået fra en hastighed, der i matematikken hedder kvadratisk tid, til lineær tid. Det betyder, at selv om et landkort bliver 10 gange større, bliver beregningen kun omkring 10 gange langsommere – hvor den med den tidligere algoritme ville blive omkring 100 gange langsommere,” forklarer Carsten Thomassen.
Gennembruddet skyldes en ny forståelse af såkaldte reducerbare konfigurationer i matematiske grafer. Forskerne har opdaget, at der findes langt flere af disse strukturer, end man tidligere har været klar over. Det giver mulighed for at begynde farvelægningen flere steder og dermed arbejde hurtigere.
Resultatet kan desuden få betydning ud over almindelige landkort. Den nye matematiske indsigt kan også bruges til at undersøge mere komplicerede overflader med huller, eksempelvis et bildæk eller en emmentalerost.
Forskningsartiklen er blevet udvalgt til FOCS 2026, en af verdens førende konferencer inden for teoretisk datalogi, hvor den også har modtaget prisen for årets bedste forskningsartikel.
Fakta om firefarveproblemet
- Formuleret: I 1852 af den engelske matematiker Francis Guthrie.
- Grundidé: Ethvert landkort kan farvelægges med højst fire farver, så nabolande har forskellige farver.
- Danske forskere: Professor Mikkel Thorup fra Københavns Universitet og professor Carsten Thomassen fra DTU.
- Forskerhold: Omfatter også Ken-ichi Kawarabayashi, Bojan Mohar, Yuta Inoue og Atsuyuki Miyashita.
- Gennembrud: En optimal algoritme, der løser problemet i lineær tid.
- Forskningspris: Artiklen er udvalgt til FOCS 2026 og har vundet konferencens pris for bedste forskningsartikel.
- Perspektiv: Metoden kan også få betydning for matematiske undersøgelser af mere komplicerede overflader.










Accepter kun nødvendige cookies