Broene i Königsberg
Fra Wikipedia, den frie encyklopedi
Broene i Königsberg er et matematisk problem som ble løst av Leonhard Euler i 1736. Løsningen hans blir ofte regnet som begynnelsen på den matematiske grenen grafteori.
Königsberg (nå Kaliningrad) ligger ved elva Pregel, som deler byen i fire deler: den nordlige og sørlige elvebredden, samt to øyer. De fire delene var forbundet med hverandre ved hjelp av sju broer, som vist på kartet. Historien forteller at innbyggerne på sine søndagsturer prøvde å legge veien slik at de krysset hver bro nøyaktig en gang, og endte opp på den samme elvebredden hvor de begynte.
Ingen lyktes i dette, og i 1736 beviste den sveitsiske matematikeren Euler i artikkelen Solutio problematis ad geometriam situs pertinentis at det var umulig. Det er faktisk heller ikke mulig om man tillater at turen begynner og slutter på forskjellige steder.
At det er umulig kan man se på følgende måte: Hver gang man kommer til en elvebredde eller øy og så forlater den, bruker man opp to av broene som fører til dette landområdet. Det betyr at om et landområde har et odde antall broer, må dette være enten begynnelsen eller slutten på turen. Siden det bare kan være én begynnelse og én slutt, vil en rute som krysser hver bro nøyaktig en gang kun finnes hvis høyst to av landområdene har et odde antall broer. Som man ser av kartet, tilfredsstiller ikke Königsberg dette kravet, så, uheldigvis for byens borgere, var det ikke mulig å gå søndagsturen på den måten de ønsket.


