15. juli 2020

Forskere fik travlt: Havde nær foræret løsning på matematikgåde fra 1980’erne væk

DATALOGI

Forskere fra Københavns Universitet og DTU troede de var fem års arbejde fra at løse en matematisk gåde fra 1980’erne, men i virkeligheden havde de uden at vide det næsten knækket problemet og foræret en stor del af løsningen væk i en forskningsartikel, de lige havde udgivet. Løsningen kan måske bruges til at forbedre vores telefoner og computere i fremtiden.

Jacob og Eva
Jacob Holm, Datalogisk Institut og Eva Rotenberg, DTU. Foto: KU

Under gennemlæsningen af vores videnskabelige artikel gik det pludselig op for os, at løsningen lå lige foran os. Og næste reaktion var ’åh nej – vi har skudt os selv i foden og foræret den væk'.

lektor Eva Rotenberg, DTU.

En rigtig hjernevrider. Sådan kan man vist roligt betegne det matematiske problem inden for disciplinen grafteori, som to matematikere fra Datalogisk Institut på Københavns Universitet og DTU netop er kommet med en løsning på, efter kloge hoveder verden over har undret sig over problemet siden 1980’erne.

Men de to dataloger, adjunkt Jacob Holm fra KU og lektor Eva Rotenberg fra DTU havde nær givet løsningen væk, da de tilbage i sommeren 2019, netop havde afleveret den forskningsartikel, som blev forløberen til den artikel, der endeligt løste gåden.

”Vi havde næsten opgivet at komme det sidste stykke og løse gåden. Vi tænkte, at vi havde et lille resultat, der var interessant, men som på ingen måde løste problemet. Vi gættede på, at der ville være fem års arbejde endnu, før vi i bedste fald kunne løse gåden,” fortæller Jacob Holm, som til daglig er en del af algoritmesektion BARC på Datalogisk Institut.

Løsningen var mellem linjerne

Meget forsimplet handler gåden om, hvordan man kan forbinde en række punkter i en graf uden at stregerne imellem punkterne i grafen krydser hinanden. Og hvordan man med en matematisk beregning, eller algoritme, kan lave ændringer i et omfattende ”graf-netværk” og stadig sikre sig, at ingen linjer krydser hinanden uden at skulle starte helt forfra. Egenskaber, som bl.a. kan bruges til at bygge store vejnetværk og indmaden i vores computere, hvor elektriske kredsløb på printplader ikke må krydse hinanden.

Den matematiske gåde, som Jacob Holm har interesseret sig for siden 1998, åbenbarede sig for alvor, da de to forskere gav den afleverede forskningsartikel en grundig gennemlæsning. For i mellemtiden havde forskerne Holm hørt om en ny matematisk teknik, som de nu opdagede kunne anvendes på problemet

”Under gennemlæsningen af vores videnskabelige artikel gik det pludselig op for os, at løsningen lå lige foran os. Og næste reaktion var ’åh nej – vi har skudt os selv i foden og foræret den væk',” siger lektor Eva Rotenberg, DTU.

En forløber til den matematiske gåde, som nu er blevet løst, fik allerede i 1913 læsere af magasinet ”The Strand Magazine” til at gruble, da den i populær form blev trykt under navnet ”The Three Utilities Problem”. I problemet skal tre hytter alle have tilført vand, gas og elektricitet, men ”rørene” eller linjerne mellem husene og vand, el og gas må ikke krydse hinanden, hvilket ikke kan lade sig gøre. Foto: Wikipedia

Om grafteori
En graf er en meget simpelt konstruktion, der bruges til at modellere alt, hvad der kan beskrives som objekter og forbindelser mellem objekter. Grafteori er både et område inden for matematik og et vigtigt hjælpemiddel i datalogien. En graf kan i denne sammenhæng illustreres ved et diagram bestående af et antal punkter (knuder) forbundet med et antal streger (kanter). Hver kant illustreres som et linjestykke (eller kurvestykke) med knuder som sine to endepunkter.

Kan måske bruges til elektronik i computere

Og så fik de to forskere ellers travlt med at skrive forskningsartiklen og få de sidste løse ender bundet sammen i løsningen af den gåde, som Jacob Holm har arbejdet på on and off siden 1998.
”Vi arbejdede non-stop på artiklen, som endte med at fylde over 40 sider, i fem-seks uger,” siger Eva Rotenberg.

Heldigvis var der ikke nogen, der overhalede dem indenom og de to forskere har for kort tid siden præsenteret resultatet på den vigtigste konferencer inden for teoretisk datalogi, som skulle være afholdt i Chicago, men som endte med at være virtuel.

Og hvad kan løsningen af den her matematiske gåde så bruges til? De to forskere ved det ikke med sikkerhed, men de har nogle bud.

”Vores forskning er grundforskning, så vi ved sjældent, hvad det ender med at blive brugt til, og vi har svært ved at forestille os det fra start,” siger Jacob Holm og uddyber:

”Men design af mikrochips og printplader, som findes i al vores elektronik, kan være et område, hvor man kan bruges vores resultat. Når man tegner ledningerne på en printplade, så er de pinedød nødt til at ligge sådan, at de ikke krydser hinanden, for ellers får man kortslutninger imellem tingene. Det samme gælder mikrochips, som rummer millioner af transistorer, som man bliver nødt til at have en graf-tegning over.”

Om løsningen
Der er to slags opdateringer i dynamiske grafer: Man kan slette en kant, og man kan indsætte en ny kant. Disse to operationer skal brugeren kunne lave, mens en algoritme hele tiden holder styr på en tegning af netværket. Denne algoritme har de forskere fundet opskriften på. Læs hele forskningsartiklen her