From Wikipedia, the free encyclopedia
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.
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.
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:
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:
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:
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.
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.[1]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
