De syv broer i Königsberg: Eulers bevis og grafteoriens begyndelse
Oplev Eulers klassiske løsning på De syv broer i Königsberg — startskuddet til grafteori og topologi, forklaret klart og med historisk kontekst.
De syv broer i Königsberg er et historisk berømt problem inden for matematik. Leonhard Euler løste problemet i 1735. Dette førte til begyndelsen af grafteorien. Dette førte så til udviklingen af topologien.
Baggrund
Byen Königsberg i Preussen (nu Kaliningrad, Rusland) lå på begge sider af Pregel-floden. Den omfattede to store øer, som var forbundet med hinanden og med fastlandet ved hjælp af syv broer. Lokalbefolkningen spurgte, om det var muligt at gå en rute gennem byen, så man krydsede hver bro præcis én gang.
Eulers idé og bevis
Euler løste problemet ved at abstrahere situationen: i stedet for at tænke på byens geografi tegnede han et netværk bestående af punkter (som repræsenterer landområderne) forbundet med linjer (som repræsenterer broerne). I moderne terminologi er dette en graf, hvor landområderne er knuder (eller vertices) og broerne er kanter (eller edges).
Hans centrale observation var denne enkle, men kraftfulde regel:
- Hvis man går langs en rute, der krydser hver kant præcis én gang (en såkaldt Eulersti), så må hver knude, undtagen evt. start- og slutknuden, have et lige antal kanter, fordi hver gang man går ind ad en kant må man gå ud ad en anden.
- Det følger, at en forbundet graf kan have en Eulersti kun hvis antallet af knuder med ulige grad (antal tilstødende kanter) er enten 0 eller 2. Hvis der er 0 er der endda en Eulerkreds (en rundtur, som begynder og slutter samme sted); hvis der er 2 er der en Eulersti, som begynder i den ene og slutter i den anden ulige knude.
Når man anvender denne regel på Königsberg-grafen, viser man hurtigt, at alle fire landområder har et ulige antal broer knyttet til sig (grad 3 eller 5 afhængigt af tælling). Da der er fire knuder med ulige grad — flere end 2 — er det umuligt at lave en rute, der krydser hver bro præcis én gang. Euler konkluderede derfor, at problemet ikke har nogen løsning.
Betydning og eftermæle
Eulers løsning var banebrydende, fordi han ikke blot løste en lokal gåde, men introducerede en ny måde at tænke på forbindelser og relationer — grundlaget for grafteorien. Ideen om at abstrahere problemer som netværk af knuder og kanter har siden vist sig at være afgørende i både ren og anvendt matematik.
Anvendelser omfatter bl.a.:
- ruteplanlægning og logistik,
- netværksanalyse (telekommunikation, strømnet),
- bioinformatik (sekvenssammenføjning) og
- teoretiske grene som topologi og kombinatorik.
Kort bevisidé (enkelt)
Antag, at en sådan rute findes. For hver gang man besøger en knude, undtagen eventuelle start- og slutknuder, indgår to brugte kanter (én ind, én ud). Derfor skal antallet af brugte kanter ved en knude være lige. Start- og slutknuden kan have et ulige antal brugte kanter (fordi man kun går ind eller kun går ud dér). Dermed kan højst to knuder have ulige grad. Hvis grafen har flere end to knuder med ulige grad, kan en sådan rute ikke eksistere. Königsberg-grafen har fire ulige knuder, så opgaven er umulig.
Konklusion
Det tilsyneladende simple problem med de syv broer i Königsberg blev startskuddet til en hel gren af matematikken. Eulers abstraktion og bevis er et klassisk eksempel på, hvordan en konkret praktisk opgave kan føre til dybtgående teoretisk indsigt.
Kort over Königsberg på Eulers tid, der viser den faktiske udformning af de syv broer, med fremhævelse af floden Pregel og broerne
Eulers analyse
For det første påpegede Euler, at valget af rute inden for hver landmasse er ligegyldigt. Den eneste vigtige egenskab ved en rute er den rækkefølge, i hvilken broerne krydses. Så han ændrede problemet til abstrakte termer. Dette lagde grunden til grafteori. Han fjernede alle funktioner undtagen listen over landmasser og broerne, der forbinder dem. I grafteoriens sprog erstattede han hver landmasse med et abstrakt "toppunkt" eller knudepunkt. Derefter erstattede han hver bro med en abstrakt forbindelse, en "kant". En kant (vej) registrerede, hvilke to hjørner (landmasser) der var forbundet. På denne måde dannede han en graf.
→
→ 
Den tegnede graf er et abstrakt billede af problemet. Kanterne kan derfor forbindes på en hvilken som helst måde. Det er kun vigtigt, om to punkter er forbundet eller ej. Hvis man ændrer billedet af grafen, ændrer man ikke selve grafen.
Dernæst bemærkede Euler, at når man kommer ind i et toppunkt via en bro, så forlader man også toppunktet via en bro (undtagen ved enderne af vandringen). I en hvilken som helst tur i grafen er antallet af gange, man kommer ind i et toppunkt, lig med antallet af gange, man forlader det. Hvis hver bro er blevet passeret præcis én gang, følger det, at for hver landmasse (bortset fra dem, der er valgt som start- og målpunkt), skal antallet af broer, der berører den pågældende landmasse, være lige. Det skyldes, at hvis der er n broer, er den krydset præcis 2n gange. Alle fire landmasser i det oprindelige problem er imidlertid berørt af et ulige antal broer (den ene er berørt af 5 broer, og hver af de tre andre er berørt af 3). Der er højst to masser, som kan være slutpunkter for en vandring. Så forslaget om, at en vandring skal krydse hver bro én gang, fører til en selvmodsigelse.
I moderne sprogbrug viser Euler, at det afhænger af knudernes grader, om det er muligt at gå gennem en graf, hvor hver kant krydses én gang eller ej. Graden af en knude er antallet af kanter, der berører den. Euler viser, at en nødvendig betingelse for at gå gennem grafen er, at den er forbundet og har præcis nul eller to knuder af ulige grad. Dette resultat, som Euler har fremlagt, blev senere bevist af Carl Hierholzer. En sådan vandring kaldes nu en Euler-sti eller Euler-gang. Hvis der er knuder af ulige grad, vil enhver eulersk sti starte ved den ene af dem og slutte ved den anden. Da grafen, der repræsenterer det historiske Königsberg, har fire knuder af ulige grad, kan den ikke have en eulersk sti.
Eulers arbejde blev præsenteret for Sankt Petersborg Akademiet den 26. august 1735. Det blev offentliggjort som Solutio problematis ad geometriam situs pertinentis (Løsningen af et problem vedrørende geometrien af positionen) i tidsskriftet Commentarii academiae scientiarum Petropolitanae i 1741. Den er tilgængelig på engelsk i The World of Mathematics.
Betydning i matematikkens historie
I matematikkens historie anses Eulers løsning af Königsberg-broproblemet for at være den første sætning i grafteori. Grafteori er et emne, der nu generelt betragtes som en gren af kombinatorikken.
Broernes nuværende tilstand
To af de syv oprindelige broer blev ødelagt under bombningen af Königsberg under Anden Verdenskrig. To andre blev senere revet ned. De blev erstattet af en moderne motorvej. De tre andre broer er bevaret, selv om kun to af dem er fra Eulers tid (den ene blev genopbygget i 1935). I 2000 var der således fem broer i Kaliningrad.
I grafteori har to af knuderne nu grad 2, og de to andre har grad 3. Derfor er en eulersk sti nu mulig, men da den skal begynde på den ene ø og slutte på den anden ø, er den upraktisk for turister.
Relaterede sider
- Icosian spil
- Hamilton-bane
- Vand, gas og elektricitet
- Rejsende sælger-problem
Spørgsmål og svar
Q: Hvad er problemet med de syv broer i Königsberg?
A: De syv broer i Königsberg er et berømt matematisk problem, der går ud på at finde en måde at gå gennem byen på ved at krydse hver af dens syv broer én gang og kun én gang.
Q: Hvem løste problemet med de syv broer i Königsberg?
A: Leonhard Euler løste problemet med de syv broer i Königsberg i 1735.
Q: Hvad førte løsningen af problemet med de syv broer i Königsberg til?
A: Løsningen af problemet med de syv broer i Königsberg førte til begyndelsen på grafteori, som derefter førte til udviklingen af topologi.
Q: Hvor ligger Königsberg?
A: Königsberg ligger i Preussen, som nu er en del af Kaliningrad i Rusland.
Q: Hvordan var Königsbergs layout?
A: Königsberg var anlagt på begge sider af Pregel-floden og omfattede to store øer, der var forbundet med hinanden og fastlandet med syv broer.
Q: Hvad var kravene for at løse problemet med de syv broer i Königsberg?
A: Problemet krævede, at man fandt en måde at gå gennem byen på ved at krydse hver bro én gang og kun én gang, hvor hver bro blev krydset helt hver gang. Øerne kunne ikke nås ad nogen anden rute end broerne, og turen behøvede ikke at starte og slutte det samme sted.
Q: Beviste Euler, at problemet med de syv broer i Königsberg har en løsning?
A: Nej, Euler beviste, at problemet med de syv broer i Königsberg ikke har nogen løsning.
Søge