
17.11.2026, 12:58
Professorerne Carsten Thomassen fra DTU og Mikkel Thorup fra Datalogisk Institut ved Københavns Universitet, KU, har været med til at skabe en algoritme, som effektivt har løst en ellers 174 år gammel matematisk hovedpine.
I 174 år har matematikere verden over bakset med om det virkelig kan passe, at man altid kan farvelægge ethvert landkort med højst fire farver, så ingen lande, der grænser op mod hinanden, har samme farve, som det blev påstået af den engelske matematiker Francis Guthrie i 1852 efter at have erfaret, at han kun behøvede fire farver, da han lavede et kort over engelske grevskaber. Problemet har siden været at bevise, at hans påstand altid holder, uanset hvordan landkortet ser ud. Et bevis blev fremlagt i 1879, og holdt i 11 år, før man opdagede en fejl. I 1976 kom så et fuldt bevis, men, det var kontroversielt, blandt andet fordi det byggede på omfattende computerberegninger, som andre matematikere havde svært ved at efterprøve. I 1997 kom endnu et og mere overskueligt bevis, der også kunne finde en firefarvning, men som algoritmisk var langsomt, hvis man skulle farvelægge store landkort.
Nu har et internationalt hold af matematikere med blandt andet de to danske professorer Carsten Thomassen fra DTU og Mikkel Thorup fra Datalogisk Institut ved KU, gjort det første gennembrud i 30 år: De har fundet den optimale algoritme, der kan firefarve ethvert landkort effektivt.
”De tidligere beviser viste godt nok, at det altid er muligt at farvelægge et landkort med fire farver. Men de er ikke gode til rent faktisk at finde frem til farverne for hvert enkelt landområde på et kort. Den nye algoritme er effektiv og giver en langt hurtigere måde at farvelægge på,” siger Mikkel Thorup, og oplyser, at en forskningsartikel om arbejdet netop er blevet præsenteret på en af verdens førende konferencer inden for teoretisk datalogi, FOCS, hvor den har vundet prisen for årets bedste forskningsartikel.
Mikkel Thorup og forskerkollegerne, der blandt andet tæller Carsten Thomassen, Ken-ichi Kawarabayashi og Bojan Mohar, har arbejdet med firefarveproblemet i cirka ti år. Deres algoritme er mere effektiv end de tidligere, er, at den bygger på en helt særlig matematisk indsigt, som forskerholdet har opnået.
I matematisk sprog kaldes en overflade som et landkort for en planær graf. Forskerne har fundet ud af, at grafer indeholder langt flere såkaldte reducerbare konfigurationer, end man hidtil har troet. Det er små udsnit af grafen, som giver matematikere et sted at tage fat, når de skal finde frem til farvelægningen.
”Tænk på reducerbare konfigurationer som håndtag, man kan gribe fat i for at komme i gang med at farvelægge grafen. Vi viser, at der ikke bare findes ét, men ufatteligt mange håndtag i grafer. Og det var der ingen, der vidste før,” siger Carsten Thomassen.
Fordi forskerne nu kan finde ’håndtag’ mange steder i grafen, hvor man hidtil kun kunne finde et enkelt, kan de begynde farvelægningen mange steder og dermed farve selv meget store kort meget hurtigere.
”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.
Med det aktuelle gennembrud har forskerne ikke blot fundet en hurtigere metode til at farvelægge landkort. Indsigten i grafers opbygning rækker ud over det klassiske firefarveproblem. Den giver flere muligheder for at studere langt mere komplicerede typer af grafer og overflader:
”Det er faktisk sådan, at fordi der er så mange håndtag, vil idéen også kunne bruges, når man ser på andre typer overflader end et fladt landkort. Det kunne for eksempel være overflader med huller som et bildæk eller en emmentaler-ost. Derfor tror vi, at resultatet kan få betydning langt ud over det årelange firefarve-problem,” siger Mikkel Thorup.
Vi samarbejder med,
og er talerør for følgende: