Königsbergs syv broer

Kort over Königsberg på Eulers tid. Floden Pregel og de syv broer er markerede.

Königsbergs syv broer eller Königsbergs broproblem er et berømt matematisk problem, som er inspireret af virkeligheden. Floden Pregel går gennem byen Königsberg (nu: Kaliningrad), og i alt syv broer forbinder de to sider af byen med hinanden og med to øer, som ligger midt i floden. Spørgsmålet er, om det er muligt at finde en tur gennem byen, så man går over hver bro præcis én gang.

Eulers løsning

Euler beviste i 1736 at det ikke kunne lade sig gøre. Da han beviste det, omformulerede han problemet til et grafteoretisk problem. Han indså, at landområdernes og broernes form ikke havde betydning og erstattede landområderne med punkter og forbandt dem med streger (også kaldet kanter). som repræsenterede broerne.

→ →

Formen på en graf kan ændres, som man har lyst til, uden at selve grafen ændres, så længe kanterne mellem knudepunkterne er de samme. Det betyder ikke noget, om kanterne mellem punkterne er lige, eller om et knudepunkt er placeret til højre eller til venstre for et andet.

Euler indså, at problemet kunne løses ved udelukkende at se på valensen af knuderne, dvs. antallet af kanter der har endepunkt i en knude. I grafen for Königsbergs broer har tre knuder valensen 3, mens én knude har valensen 5. Euler beviste, at der findes en rute, som går over alle kanter netop én gang, hvis og kun hvis grafen er sammenhængende, og netop to eller ingen af knuderne har ulige valens. En sådan rute kaldes i dag en Euler-tur. Der gælder desuden, at hvis der er to knuder med ulige valens, så må disse to punkter være start- og slutknuderne for Euler-turen. Da grafen for Königsbergs broer indeholder fire knuder med ulige valens, findes der ingen Euler-tur over Königsbergs broer.

Dette kan illustreres med et konkret eksempel: Den østlige ø har tre broer. Hvis man kommer til øen over den ene bro, skal man forlade den over den anden eller tredje bro. Vælger man den anden, kan man senere vende tilbage over den tredje, men hvordan kommer man så videre? Man har nu gået over de tre broer præcis én gang hver og er nu på øen, som imidlertid ikke er målet. For at komme videre til målet, er man derfor nødt til at fortsætte ad en af de tre broer, men derved går man over den givne bro to gange, hvilket netop ikke var ønsket. Skal ønsket opfyldes, er en fjerde ubetrådt bro nødvendig, men en sådan eksisterer ikke.

Betydning for matematikkens historie

Eulers løsning på Königsbergs broproblem bliver regnet for at være den første sætning inden for grafteori. Desuden er det interessant, at Euler indså, at det ikke var broernes præcise placering, men hvad de forbandt, der var vigtigt. Dette minder nemlig om de tanker, der ligger bag topologi, som først blev opfundet senere.

Broerne i dag

Den vestlige ø`s to broer til fastlandet blev ødelagt under et britisk bombardement af Königsberg under 2. verdenskrig, mens russerne senere erstattede de to vestlige med en moderne højgade. De tre andre broer eksisterer stadig, om end den ene blev genbygget af tyskerne i 1935. I alt er der nu fem broer i Königsberg.

Omsat grafisk har to af punkterne (flodbredderne) nu valensen 2 og de to andre (øerne) valensen 3. Det er nu muligt at gå en tur, hvor man betræder hver bro præcis én gang. Imidlertid vil den uanset hvad altid begynde på den ene ø og slutte på den anden. En rundtur er stadig ikke mulig. ^[1]