Datavetenskapsforskare från Köpenhamns universitet och Danmarks Tekniske Universitet (DTU) trodde att de var fem år ifrån att lösa en mattegåta från 1980-talet. I verkligheten, och utan att veta, de hade nästan knäckt problemet och hade precis gett bort mycket av lösningen i en forskningsartikel. Lösningen skulle kunna användas för att förbättra morgondagens telefoner och datorer.

Jacob Holm och Eva Rotenberg

En riktig hjärngyckel. Det är så man säkert kan beskriva detta matematiska problem inom disciplinen grafteori. Två matematiker från Köpenhamns universitets institution för datavetenskap och DTU har nu löst ett problem som världens snabbaste och smartaste har brottats med sedan 1980-talet.

De två datavetarna, Docent Jacob Holm vid KU och docent Eva Rotenberg vid DTU gav nästan bort sin lösning sommaren 2019, efter att ha skickat in en forskningsartikel som blev föregångaren till artikeln där de till slut löste mattegåtan.

"Vi hade nästan gett upp med att få den sista biten och lösa gåtan. Vi trodde att vi hade ett mindre resultat, en som var intressant, men på inget sätt löst problemet. Vi gissade att det skulle bli ytterligare fem års arbete, i bästa fall, innan vi skulle kunna lösa pusslet, " förklarar Jacob Holm, som är en del av BARC, algoritmsektionen vid KU:s institution för datavetenskap.

Problemet med tre verktyg

1913, en föregångare till den nu lösta matematiska gåtan publicerades i The Strand Magazine som "The Three Utilities Problem". Det fick tidningens läsare att klia sig i huvudet och fundera. I problemet, var och en av tre stugor måste ha vatten, gas och el, medan "linjerna" mellan husen och vattnet, el och gas får inte korsa varandra – vilket inte är möjligt.

En lösning mellan raderna

Enkelt uttryckt, pusslet handlar om hur man kopplar ihop ett antal punkter i en graf utan att låta linjerna som förbinder dem korsas. Och hur, med en matematisk beräkning – en algoritm – kan du göra ändringar i ett omfattande "grafnätverk" för att säkerställa att inga linjer skär varandra utan att behöva börja om från början. Egenskaper som kan användas för, bland annat, bygga enorma vägnät eller den lilla insidan av datorer, där elektriska kretsar på kretskort inte får korsa.

Jacob Holm har varit intresserad av den matematiska gåtan sedan 1998, men svaret avslöjades först medan de två forskarna läste igenom sin redan inskickade forskningsartikel. Sålänge, forskarna hörde om en ny matematisk teknik som de insåg kunde tillämpas på problemet.

"När du läser vår forskningsartikel, vi insåg plötsligt att lösningen fanns framför våra ögon. Vår nästa reaktion var "åh nej - vi har skjutit oss själva i foten och gett bort lösningen, säger docent Eva Rotenberg vid DTU.

Om grafteori

En graf är en mycket enkel konstruktion som används för att modellera saker som kan beskrivas som objekt och sambanden mellan dem. Grafteori är både ett område inom matematiken och ett viktigt verktyg inom datavetenskap.

I detta sammanhang, en graf kan illustreras med ett diagram som består av ett antal punkter (noder, hörn) associerade med ett antal linjer (kanter). Varje kant illustreras som en linje (eller böjd bit) med noder som sina två ändpunkter.

Om lösningen

Det finns två typer av uppdateringar i dynamiska grafer:Den ena kan ta bort en kant och du kan infoga en ny kant. Dessa två operationer måste utföras av användaren, medan en algoritm håller reda på nätverkets ritning hela tiden. Det är algoritmen som forskarna har hittat receptet på.

Kan användas för datorelektronik

Det var då de två forskarna fick fullt upp med att skriva forskningsuppsatsen och knyta ihop lösa trådar för att lösa den gåta som Holm hade arbetat med periodvis sedan 1998.

"Vi arbetade på artikeln utan uppehåll, i fem till sex veckor. Och, det slutade med att fylla mer än 80 sidor, säger Eva Rotenberg.

Lyckligtvis, ingen slog dem till lösningen och de två forskarna kunde presentera sina resultat vid de viktigaste teoretiska datavetenskapskonferenserna, som var avsedda att hållas i Chicago, men det slutade med att de hölls praktiskt taget.

Så, vad kan lösningen på denna matematiska gåta användas till? De två forskarna vet inte säkert, men de har några förslag.

"Vår forskning är grundforskning, så vi vet sällan vad den kommer att användas till. Redan från början, vi tycker att tillämpningar är svåra att föreställa sig, säger Jacob Holm, vem lägger till, "Utformningen av mikrochips och kretskort, finns i all elektronik, kan vara ett område där vårt resultat kommer att användas. När du drar ledningar på ett kretskort, de får aldrig skära varandra. Annat, kortslutning kommer att uppstå. Detsamma gäller mikrochips, som innehåller miljontals transistorer och för vilka man måste ha en grafritning."