Problem mostów królewieckich

Kategorie

Przez miasto Królewiec (obecnie Kaliningrad – Rosja) przepływa rzeka Pregoła. Jej wody otaczają wyspę a następnie rozgałęziają się w kilku kierunkach. W XVIII wieku brzegi rzeki i wyspa połączone były siedmioma mostami. Sytuacja ta przedstawiona jest na poniższym rysunku, brązowym kolorem oznaczono mosty, z kolei na zielono oznaczono powierzchnie lądową, a na niebiesko – bieg rzeki.

Legenda mówi, iż mieszkańcy tego miasta uwielbiali spacerować po tej pięknej okolicy, zastanawiając się jednocześnie czy można tak dobrać trasę spaceru, aby po wyjściu z domu przejść przez każdy z mostów dokładnie jeden raz, a następnie powrócić do punktu wyjścia. Problem ten przypadkiem dotarł do znakomitego szwajcarskiego matematyka – Leonharda Eulera.

Mimo iż żył on w XVIII śmiało można go nazwać człowiekiem renesansu, był profesorem fizyki, wykładał matematyką, astronomię, medycynę, grekę oraz język hebrajski. Obecni studenci uczelni technicznych oraz ekonomicznych z pewnością kojarzą tzw. liczbę Eulera w przybliżeniu wynoszącą 2,72.

Wróćmy jednak do problemu mostów królewieckich. Na rysunku poniżej przedstawiono uproszczony schemat naszego problemu, mosty zastąpiono łukami, które ponumerowana cyframi od 1 do 7. Z kolei powierzchnie lądowe oznaczono literami od A do D.

Spróbujmy w takim razie zaczynając wędrówkę od punktu C przejść przez wszystkie mosty wracając do punktu wyjścia. Przyjmijmy, że na początku wybieramy trasę w prawo, przez most numer 1 do punktu A, stamtąd możemy się kierować do punktu B lub D. Wybierzmy punkt D, następnie możemy wybrać mosty 3, 4, 5 lub 6. Wybierzmy most 3, następnie musimy już wrócić mostem 4 do punktu D, gdyż na początku wybraliśmy most nr 1, później z punktu D musimy się już kierować do punktu B przez most 5 lub 6. Wybierzmy most nr 5. Będąc już w punkcie B musimy wybrać most 6 lub 7. Niezależnie który most wybierzemy, z kolejnego punktu nie mamy już drogi ucieczki.

Każdy inny wybór trasy początkowej prowadzi do sprzeczności co udowodnił Euler. Szwajcarski matematyk stwierdził iż podczas naszej wędrówki wchodzimy i opuszczamy każda z lądów tyle samo razy, dlatego każdy z nich musi być połączony z innymi parzystą liczbą mostów. Ten warunek wystarczy, aby przejście po każdym moście dokładnie jeden raz, niezależnie od ich liczby było możliwe

Ta zagadka dała początek tzw. teorii grafów, która ma niebanalne znaczenie we współczesnej informatyce, ale także współcześnie może być rozrywką umysłową.

Ciekawostką jest fakt, iż współcześnie na rzece Pregola problem ten jest możliwy do rozwiązania. Współcześnie mamy tam 5 mostów, z czego tylko dwa zostały zachowane z czasów Eulera. Jednakże taka wędrówka jest mało praktyczna.

Mosty na omawianej rzece cieszą się obecnie dużym powodzeniem wśród zakochanych, którzy wieszają na nich kłódki symbolizujące ich miłość, a klucze do nich rzucają do rzeki.

Dodaj swój komentarz





← Starsze Nowsze →