Broene i Königsberg

Fra Wikipedia, den frie encyklopedi
Gå til: navigasjon, søk
Kart over KönigsbergEulers tid, med de sju broene markert med grønt

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.

Bakgrunn[rediger | rediger kilde]

1700-tallet var byen Königsberg (nåværende Kaliningrad) i daværende Østpreussen 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 sju 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 en 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[rediger | rediger kilde]

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

Kønigsberg bykartStilisert problemEulers abstrakte graf

I denne grafen motsvarer prikkene (nodene) posisjoner på noen av øyene eller fastlandet, og linjene (kantene) 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 er nok for å løse problemet med Kønigsbergs broer, enten det kreves at start- og sluttpunktet sammenfaller eller ikke:

Hvis et punkt har et odde antall forbindelser må den være enten start eller sluttpunkt; ellers blir man tvunget til å gå over en bro man allerede har gått over en 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 fire punkter 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 av disse punktene og slutter i det andre.
  • om ingen nod har ett odde antall forbindelser så går det an å finne en tur som passerer hver bro eksakt en gang uansett hvilket punkt som er startpunkt.

Den andre 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 eulersirkel.

Øvrig[rediger | rediger kilde]

Satellittbilde over Kaliningrad, tidigere Königsberg

Noter 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 sju 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 igjen fem broer, 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, noe som dermed gjorde den ønskede turen mulig.

Eksterne lenker[rediger | rediger kilde]

Litteratur[rediger | rediger kilde]

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