Danske forskere finder smart løsning på 174 år gammel gåde
Videnskab.dk - Automatisk oplæsning · Videnskab.dk
Beskrivelse
Kan et hvilket som helst landkort farvelægges med kun fire farver, uden at ét eneste land grænser op til et andet med samme farve? Ja, påstod den engelske matematiker Francis Guthrie i 1852. Siden har forskere verden over jagtet gyldige matematiske beviser for påstanden. Nu har to professorer fra Københavns Universitet (KU) og DTU, sammen med en række internationale kolleger, fundet en optimal algoritme til at løse det matematiske problem, skriver KU i en pressemeddelelse. Løsningen kommer på bagkant af 10 års arbejde, efter matematikerne blev så besatte af problemet, at de ligefrem kalder det 'firefarver-sygdommen'. "Sygdommen er, at man tænker, at der må findes et simpelt bevis på så simpel en påstand. Og jeg skyder på, at der dags dato er mindst 1.000 matematikere, der har haft firefarve-sygdommen, hvor man prøver i månedsvis, men simpelthen ikke kan få det til at passe sammen," siger Mikkel Thorup, der er professor ved Datalogisk Institut på Københavns Universitet og en af forskerne bag den nye løsning, i pressemeddelelsen. Andre forskere har før fremlagt matematiske beviser for firefarver-problemet. 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. Årsagen til, at den nye algoritme er mere effektiv end de tidligere, er, at den bygger på en ny matematisk indsigt, som forskerholdet har opnået. Det drejer sig om de såkaldte 'reducerbare konfigurationer' i en graf, som forskerne har fundet frem til, at der findes langt flere af, end man hidtil har troet. "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 professor og medforfatter Carsten Thomassen fra DTU. Fordi forskerne nu kan finde disse 'håndtag' mange steder i grafen, hvor man før kun kunne finde et enkelt, kan de begynde farvelægningen mange steder. Det gør dem i stand til at farvelægge selv store kort meget hurtigere end før, ifølge pressemeddelelsen. Teknikken kan desuden også overføres til andet end landkort. De kan blandt andet gøre det muligt at studere nogle mere komplicerede typer af grafer og overflader med huller - såsom bildæk eller emmentaler-ost. Matematikernes løsning er ikke udgivet i et fagfællebedømt tidsskrift, men ligger online i en såkaldt preprint-artikel. Den blev for nylig præsenteret på en konference i New York, hvor den vandt konferencens pris for bedste forskningsartikel.