Forskere lod næsten løsningen på en matematisk gåde glide væk

Datalogiske forskere fra Københavns Universitet og Danmarks Tekniske Universitet (DTU) mente, at de var fem år fra at løse en matematikgåde fra 1980'erne. I virkeligheden, og uden at vide, de havde næsten knækket problemet og havde netop givet meget af løsningen væk i en forskningsartikel. Løsningen kunne bruges til at forbedre morgendagens telefoner og computere.

Jacob Holm og Eva Rotenberg

En sand hjernetrim. Sådan kan man roligt beskrive dette matematiske problem i disciplinen grafteori. To matematikere fra Københavns Universitets Institut for Datalogi og DTU har nu løst et problem, som verdens hurtigste og klogeste har kæmpet med siden 1980'erne.

De to dataloger, Adjunkt Jacob Holm fra KU og lektor Eva Rotenberg fra DTU gav næsten deres løsning væk i sommeren 2019. efter at have indsendt en forskningsartikel, der blev forløberen for artiklen, hvor de endelig løste matematikgåden.

"Vi havde næsten opgivet at få den sidste brik og løse gåden. Vi troede, at vi havde et mindre resultat, en der var interessant, men på ingen måde løst problemet. Vi gættede på, at der ville være yderligere fem års arbejde, i bedste fald, før vi ville være i stand til at løse gåden, " forklarer Jacob Holm, som er en del af BARC, algoritmesektionen på KU's Institut for Datalogi.

Problemet med de tre forsyningsselskaber

I 1913, en forløber for den nu løste matematiske gåde blev udgivet i The Strand Magazine som "The Three Utilities Problem". Det fik bladets læsere til at klø sig i hovedet og gruble. I problemet, hver af tre hytter skal have vand, gas og elektricitet, mens "linjerne" mellem husene og vandet, elektricitet og gas må ikke krydse hinanden - hvilket ikke er muligt.

En løsning mellem linjerne

Kort fortalt, puslespillet handler om, hvordan man forbinder et antal punkter i en graf uden at lade linjerne, der forbinder dem, krydses. Og hvor, med en matematisk beregning – en algoritme – kan du foretage ændringer i et omfattende "grafnetværk" for at sikre, at ingen linjer skærer hinanden uden at skulle starte forfra. Egenskaber der kan bruges til, blandt andet, opbygning af enorme vejnetværk eller computers lille indre, hvor elektriske kredsløb på printplader ikke må krydse.

Jacob Holm har været interesseret i den matematiske gåde siden 1998, men svaret blev først afsløret, mens de to forskere læste deres allerede indsendte forskningsartikel igennem. I mellemtiden, forskerne hørte om en ny matematisk teknik, som de indså kunne anvendes på problemet.

"Mens du læser vores forskningsartikel, vi indså pludselig, at løsningen var for øjnene af os. Vores næste reaktion var 'åh nej - vi har skudt os selv i foden og givet løsningen væk, siger lektor Eva Rotenberg fra DTU.

Om grafteori

En graf er en meget simpel konstruktion, der bruges til at modellere ting, der kan beskrives som objekter og sammenhængene mellem dem. Grafteori er både et matematikområde og et vigtigt værktøj inden for datalogi.

I denne sammenhæng, en graf kan illustreres med et diagram bestående af et antal punkter (knudepunkter, hjørner) forbundet med et antal linjer (kanter). Hver kant er illustreret som en linje (eller buet stykke) med noder som sine to endepunkter.

Om løsningen

Der er to slags opdateringer i dynamiske grafer:Den ene kan slette en kant, og du kan indsætte en ny kant. Disse to handlinger skal udføres af brugeren, mens en algoritme holder styr på netværkets tegning hele tiden. Det er den algoritme, som forskerne har fundet opskriften på.

Kan bruges til computerelektronik

Det var her, de to forskere fik travlt med at skrive forskningsoplægget og binde løse ender for at løse den gåde, som Holm havde arbejdet på med mellemrum siden 1998.

"Vi arbejdede på artiklen uden stop, i fem til seks uger. Og, det endte med at fylde mere end 80 sider, siger Eva Rotenberg.

Heldigvis, ingen slog dem til løsningen, og de to forskere var i stand til at præsentere deres resultater på de vigtigste teoretiske datalogiske konferencer, som skulle afholdes i Chicago, men endte med at blive holdt virtuelt.

Så, hvad kan løsningen på denne matematiske gåde bruges til? De to forskere ved det ikke med sikkerhed, men de har et par forslag.

"Vores forskning er grundforskning, så vi ved sjældent, hvad det ender med at blive brugt til. Selv fra starten, vi finder applikationer svære at forestille sig, siger Jacob Holm, hvem tilføjer, "Designet af mikrochips og printkort, findes i al elektronik, kunne være et område, hvor vores resultat ender med at blive brugt. Når du tegner ledninger på et printkort, de må aldrig krydse hinanden. Ellers, der vil opstå kortslutninger. Det samme gælder for mikrochips, som indeholder millioner af transistorer, og som man skal have en graftegning til."