Broene i Königsberg

Broene i Königsberg er et matematisk problem innen grafteori og topologi. Den sveitsiske matematikeren Leonhard Euler viste i artikkelen Solutio problematis ad geometriam situs pertinentis i 1736 at problemet ikke lar seg løse. Artikkelen hans blir ofte regnet som begynnelsen på den matematiske grenen grafteori.

Kart over Königsberg på Eulers tid, med de syv broene markert med grønt.

Bakgrunn

På 1700-tallet var byen Königsberg (nåværende Kaliningrad) i daværende Øst-Preussen oppdelt i fire deler: den nordlige og sørlige siden av elven Pregel, som fløt gjennom byen, samt to øyer midt i elven – en mindre vestlig og en større østlig. Den minste av øyene, Kneiphof, var byens sentrum, der blant annet katedralen lå. Fra denne øya gikk det to broer til den nordlige bredden og to broer til den sørlige bredden, samt en bro til den største øya, og fra denne gikk det i sin tur en bro til den nordlige bredden og en bro til den sørlige bredden. Totalt var dermed øyene og fastlandet forbundet med hverandre ved syv broer. Det ble sagt at byens innbyggere på sine søndagsturer forsøkte å finne en måte å gå gjennom byen på en slik måte at man passerte hver bro bare én gang, og når turen var over var man tilbake til utgangspunktet. Ingen hadde dog lyktes med dette. Enkelte hevdet at det var umulig, men ingen visste dette sikkert.

Problemets løsning

Leonhard Euler.

Den sveitsiske matematikeren Leonhard Euler, som da bodde i St. Petersburg, fikk høre om problemet med Königsbergs syv broer og besluttet å løse det. Problemet var å finne en vei som passerer alle bruene eksakt én gang. I 1736 viste han at det ikke finnes noen løsning på problemet; en slik tur er ikke mulig. For å løse problemet omformulerte Euler det til en abstrakt graf med følgende utseende:

→ →

I denne grafen motsvarer prikkene (nodene) posisjoner på øyene og fastlandet, mens linjene (kantene) motsvarer broer. Euler viste at:

• hvis det finnes flere enn to noder som har et odde antall forbindelser så finnes det ingen løsning.

Beviset er trivielt, og det er nok for å løse problemet med Könnigsbergs broer, enten det kreves at start- og sluttpunktet sammenfaller eller ikke:

• hvis et punkt har et odde antall forbindelser må det enten være start- eller sluttpunkt; ellers blir man tvunget til å gå over en bro man allerede har gått over én gang for å komme derifra siste gangen punktet besøkes. En tur kan bare ha ett start- og ett sluttpunkt.

I tilfellet Königsberg har alle de fire punktene et odde antall forbindelser og ingen løsning er derfor mulig i dette tilfellet.

Uten å vise det konstaterte Euler at:

• hvis det finnes eksakt to noder med et odde antall forbindelser så finnes det en løsning der turen begynner i et av disse punktene og slutter i det andre.
• hvis ingen node har et odde antall forbindelser, så går det an å finne en tur som passerer hver bro eksakt én gang uansett hvilket punkt som er startpunkt.
  Denne påstanden ble bevist i 1873 av den tyske matematikeren Carl Hierholzer. Han viste at det finnes en løsning uansett i hvilket punkt man starter, og turen begynner og slutter i samme punkt.

Til minne om Euler kaller man en slik tur som passerer alle broer eksakt en gang for en eulervei. Om turen begynner og slutter i samme punkt kalles den for en eulersyklus.

Øvrig

De syv broene i Köningsberg på et moderne kart over Kaliningrad. Grønn farve viser de fem nåværende broene, mens rød farve viser de to broene som ikke er blitt bygget opp igjen.

Notér forskjellen mellom kart over Königsberg fra Eulers tid, som viser det virkelige utseendet på Königsbergs sentrale deler, og det skjematiske bildet. Forskjellen mellom disse tydeliggjør hvor topologien ser bort fra uvesentlige egenskaper hos de objektene som studeres.

De syv broene hadde under den tyske tiden egne navn. Broene til den nordlige stranden het, regnet fra vest Krämerbrücke, («Handelsmannsbroen»), Schmiedbrücke («Smedbroen»), og Holzbrücke («Trebroen»), broene til den sørlige stranden het, regnet fra vest, Grünbrücke («Grønne broen»), Köttelbrücke («Kråsbroen») og Hohe Brücke («Høybroen»), mens broen mellom de to øyene het Honigbrücke («Honningbroen»). I dagens Kaliningrad finnes det bare fem broer igjen, og av disse er bare to, Holzbrücke og Hohe Brücke, igjen fra Eulers tid. Honigbrücke ble erstattet i 1935 av en ny bro, mens Schmiedbrücke og Köttelbrücke ble ødelagt under andre verdenskrig. De to opprinnelige vestlige broene, Krämerbrücke og Grünbrücke, ble revet av russerne etter krigen og erstattet av en ny bro. Dermed er den ønskede turen blitt mulig, men den må begynne på en av de to øyene og slutte på den andre. I Eulers abstrakte graf kan dette vises ved å fjerne f.eks. de to indre buene.

Eksterne lenker

• (engelsk) Königsberg bridges
• (engelsk) A visit at the bridges of Königsberg

Litteratur

• James R. Newman (Ed.). The World of Mathematics, volume I. Simon and Schuster, New York, 1956.