Königsberg-broproblemet og Euler’s sti- og kredsteorem

Königsberg-broproblemet

Königsberg-broproblemet er et historisk matematisk problem, der stammer fra byen Königsberg (nu Kaliningrad, Rusland) i det 18. århundrede. Byen var delt af floden Pregel, som omkransede to øer, forbundet til hinanden og fastlandet af syv broer.

Problemet gik ud på at finde en rute, hvor man krydser hver bro præcis én gang og vender tilbage til udgangspunktet (en “kreds”). Spørgsmålet blev stillet, om en sådan rute overhovedet var mulig.

I 1736 beviste den schweiziske matematiker Leonhard Euler, at det ikke kunne lade sig gøre. Hans arbejde markerede begyndelsen på grafteori, en gren af matematik, der undersøger netværk og forbindelser.

Euler’s analyse

Euler repræsenterede broerne og landmasserne som en graf:

• Landmasserne blev omdannet til knuder (noder).
• Broerne blev omdannet til kanter (linjer) mellem noderne.

For at finde en løsning til problemet, undersøgte Euler antallet af kanter, der møder hver knude. Dette kaldes knudens grad.

Euler’s sti- og kredsteorem

Euler udviklede to fundamentale resultater inden for grafteori:

1. Euler-sti

En Euler-sti er en sti i en graf, der besøger hver kant præcis én gang (men ikke nødvendigvis slutter samme sted som den begyndte).

• En Euler-sti er mulig, hvis og kun hvis præcis to knuder har ulige grad (alle andre knuder har lige grad).
• Hvis ingen knuder har ulige grad, er det også muligt at finde en Euler-sti, men den bliver i dette tilfælde en Euler-kreds (se nedenfor).

2. Euler-kreds

En Euler-kreds er en sti i en graf, der besøger hver kant præcis én gang og slutter samme sted, som den begyndte.

• En Euler-kreds er mulig, hvis og kun hvis alle knuder har lige grad, og grafen er sammenhængende (det vil sige, at alle noder er forbundet via kanter).

Løsning på Königsberg-broproblemet

I Königsberg-grafen har hver af de fire knuder en ulige grad:

• To knuder har tre kanter (grad 3).
• To andre knuder har fem kanter (grad 5).

Da der er flere end to knuder med ulige grad, er hverken en Euler-sti eller en Euler-kreds mulig. Dermed er det ikke muligt at krydse hver bro præcis én gang.

Betydning af Euler’s arbejde

Euler’s arbejde på Königsberg-broproblemet var banebrydende og førte til udviklingen af grafteori, som i dag har mange anvendelser, fra computerteknologi til logistik og netværksanalyse. Euler’s teorem gør det muligt at analysere komplekse netværk og forstå deres struktur og egenskaber.