Matematik

Köningsbergs broar och grafteori

Josefin Dejeborn-Holmes

Under 1700-talet började invånarna i staden Königsberg (nuvarande Kaliningrad) grubbla över en fråga som skulle ge upphov till läran om grafteori. Då stadens centrum var byggt över två öar med sju broar uppstod följande fråga: Gick det att passera alla sju broar på en promenad utan att korsa samma bro två gånger?

Staden Königsberg var byggd ovanpå två öar

Svaret på det fann den schweiziske matematikern Leonard Euler år 1736, som bevisade att det inte var möjligt. En besvikelse för Königsbergs invånare, men i samband med Eulers bevis ritade han en schematisk bild av broarna och fastlandet för att få en överblick av problemet (och för att slippa vandra själv!). Denna kan ses nedan och blev den första av många grafer att komma!

Eulers graf över Königsbergs broar

När man tänker på en graf kanske tanken först går till en funktion i ett koordinatsystem, men inom grafteorin behandlas istället grafer som presenterar relationer mellan olika objekt. Det kan exempelvis vara städer på en karta, eller som i figuren ovan; förhållandet mellan fastlandet och broarna Königsberg. Fastlandet representeras av prickar som kallas noder och broarna representeras av linjer kallade kanter inom grafteori. 

Euler bevisade att om det finns fler än två noder med ett udda antal kanter, alltså broar, skulle en promenad där varje bro passerades endast en gång vara omöjlig. Detta beror på att en nod med ett udda antal kanter måste vara antingen en start- eller slutpunkt för promenaden, och en sammanhängande promenad kan såklart bara ha en av varje. För att man ska kunna nå en nod och lämna den krävs det vidare att det för varje ingång till noden finns en utgång. 

Om det finns exakt två noder med udda antal kanter eller om ingen nod har ett udda antal kanter är minst en promenad möjlig. När alla broar passeras endast en gång kallas det för en Eulerväg. Den vägtypen kräver inte att man börjar eller slutar på samma plats, men gör man det så kallas det istället för en Eulerkrets. I Königsberg fanns det fyra noder med udda antal kanter, varpå det inte var möjligt att hitta någon Eulerväg eller Eulerkrets som uppfyllde invånarnas krav.

Grafteori i allmänhet handlar om att lösa problem som kan representeras med en nätverksstruktur, precis som Euler gjorde med Königsbergs sju broar. Låt oss testa två problem och undersöka om en Eulerväg eller Eulerkrets finns i graferna.

Utifrån Eulers konstateranden undersöker vi hur många kanter som varje nod har i grafen. I grafen finns det tre noder (A, B och E) som har två stycken kanter vardera i förbindelse, samt två noder (D och C) med tre kanter var i anslutning. Det finns högst två noder med ett udda antal förbindelser, varpå grafen innehåller minst en Eulerväg som vi kan rita ut.

Nästa graf är lite mer klurig, men vi gör samma sak och räknar antal kanter hos varje nod.

Det går att se att två noder är förbundna med två kanter vardera och fyra noder är i anslutning med tre kanter var. Baserat på Eulers konstaterande om att en promenad endast var möjlig om det fanns högst två noder med ett udda antal kanter, kan vi dra slutsatsen att grafen inte innehåller en Eulerväg eller Eulerkrets.

Grafteori har en mängd tillämpningar, såsom att hitta den kortaste vägen i ett givet sammanhang via programmering. Då använder man sig av en matematisk algoritm kallad Dijkstras algoritm. Dijkstras algoritm beräknar avståndet för alla möjliga vägar mellan två noder, jämför vägen för att slutligen hitta den kortaste vägen. 

Grafteori kan även användas för att analysera olika typer av nätverk, såsom datanätverk. Genom att representera ett nätverk på internet som en graf kan man få insikter i hur effektivt ett nätverk är, anslutningsmöjligheter, och även identifiera kritiska noder eller länkar som krävs för att upprätthålla nätverket och motverka störningar. Även spridningen  av virus kan hindras genom att studera grafen för ett nätverk.

En graf behöver inte heller ha matematiska eller tekniska tillämpningar, utan ett socialt nätverk över vänner på Facebook eller kontakter på Linkedln är också en typ av graf.  Då fungerar en användare som en nod och en kant som en relation mellan två användare, vilket gör att man ofta får förslag på vänner på Facebook och underlättar för företag att nå ut med reklam till fler personer på nätet.

Vi lever alltså i en matematisk värld. Spännande, eller hur? Från att ha besvarat gåtan om Königsbergs broar till att utforska sociala relationer online så har grafteorin vuxit till ett mångsidigt område, som finner matematiken i vardagen.

Källor som användes i den här artikeln


Stephan C. Carlson ; Königsberg bridge problem; Britannica ; 2023; https://www.britannica.com/science/Konigsberg-bridge-problem, 2024-04-09.

Matteboken; Vandringar, vägar och kretsar; Matteboken ; https://www.matteboken.se/lektioner/mattespecialisering/grafteori/vandringar-vagar-och-kretsar#!/, 2024-04-09.

Estefania Cassingena Navone; Dijkstra’s Shortest Path Algoritm – A Detailed and Visual Introduction. freeCodeCamp; freeCodeCamp ; 2020; https://www.freecodecamp.org/news/dijkstras-shortest-path-algorithm-visual-introduction/, 2024-04-09.

OpenSistemas; Graph theory applied to social media analysis; OpenSistemas ; 2020; https://opensistemas.com/en/graph-theory-applied-to-social-media-analysis/, 2024-04-09.

Teo Paoletti; Leonard Euler’s Solution to the Konigsberg Bridge Problem; Mathematical Association of America ; 2011; https://maa.org/press/periodicals/convergence/leonard-eulers-solution-to-the-konigsberg-bridge-problem, 2024-04-09.

Xavier Polanco; Clusters, Graphs, and Networks for Analysing Internet-Web-Supported Communication within a Virtual Community. 7th International ISKO Conference, Granada, Spain; HAL science ; 2011; https://hal.science/hal-00161192v1/file/XP_CoSiteAnalysis.pdf, 2024-04-09.

Framsidebild: Ensar *, Pexels; https://www.pexels.com/photo/river-by-the-town-in-italy-17785605/

Illustrationer: Josefin Dejeborn-Holmes