Login lub e-mail Hasło   

Zagadnienie mostów królewieckich

Odnośnik do oryginalnej publikacji: http://www.adamklimowski.tox.pl/zagadnie(...)ch.html
Królewiec (obecnie Kaliningrad) leży nad rzeką Pregołą. Dzielnice leżące w jej pobliżu (z czego dwie leżące na wyspach śródrzecznych) łączyło w XVII wieku siedem mostów. Czy możliwe było takie ich przejście, by żaden z nich nie był „zaliczony” więcej niż raz?
Wyświetlenia: 4.688 Zamieszczono 27/01/2008

Herb KaliningraduKrólewiec (obecnie Kaliningrad) leży nad rzeką Pregołą. Dzielnice leżące w jej pobliżu (z czego dwie leżące na wyspach śródrzecznych) łączyło w XVII wieku siedem mostów. Czy możliwe było takie ich przejście, by żaden z nich nie był "zaliczony" więcej niż raz?

Mosty królewieckie- mapa

Nad tym problemem zastanawiał się słynny szwajcarski matematyk, Leonhard Euler. W dziele Solutio problematis ad geometriam situs pertinetis (skan w formacie .pdf) stwierdza, że przejście mostów w opisany wyżej sposób jest niemożliwe. Nie poprzestał jednak na tym- przeniósł problem na grunt teoretyczny, rozpatrując układ przepraw rzecznych jako swego rodzaju graf. Pytanie przybrało wówczas następującą postać: jakie warunki muszą być spełnione, żeby dany graf spójny można było opisać linią ciągłą w taki sposób, by każda krawędź tego grafu była obwiedziona tylko raz?

Mosty królewieckie jako graf

Powyższy rysunek przedstawia mosty królewieckie w formie grafu spójnego. Lewy wierzchołek to pierwsza wyspa, prawy- to druga wyspa, a wierzchołek górny i dolny reprezentują oba brzegi rzeki. Euler udowodnił, że takiego grafu nie można opisać linią ciągłą w sposób opisany wyżej. Dlaczego?

W lewym wierzchołku spotyka się pięć krawędzi. W prawym, górnym i dolnym- po trzy. W ten sposób uzyskujemy 4 wierzchołki, w których spotyka się nieparzysta liczba krawędzi. Tymczasem Euler pokazał, że takich wierzchołków musi być 0 lub 2, by graf (zwany wówczas eulerowskim) można było obwieść linią bez kilkukrotnego "zaliczania" poszczególnych krawędzi.

Te warunki spełnia graf, który powstałby po dobudowaniu jeszcze jednego, dwóch lub trzech mostów.

Ciekawostką jest, że obecna liczba mostów w Kaliningradzie (jest ich 5, z czego już tylko dwa pochodzą z czasów Eulera) pozwala na ich przejście zgodnie z warunkami założonymi przez Szwajcara. Jest to jednak wędrówka bardzo niepraktyczna dla turystów, ponieważ zaczynają podróż na jednej wyspie, a kończą na drugiej.

Zagadnienie mostów królewieckich wykorzystano także w mapie do gry komputerowej N, której główny bohater- ninja- musi, pokonując różne przeszkody, znaleźć drogę do wyjścia. Oczywiście w tym wypadku jest to niemożliwe.

The Bridges of Konigsberg- mapa do N

Hymn teorii grafów

Na odbywającej się w 1981 w czechosłowackim Jabłońcu nad Nysą Konferencji z Teorii Grafów kilku prelegentów zaproponowało stworzenie hymnu, poświęconego teorii grafów. Wiosną 1982 prof. Bohdan Zelinka przygotował tekst, poświęcony głównie zagadnieniu mostów królewieckich, jako słynnemu problemowi rozwiązanemu z pomocą teorii grafów. Został on zaprezentowany światu w maju 1983, na odbywającej się w Zemplínskiej Šíravie Konferencji z Teorii Grafów. Bardzo szybko pojawiły się liczne tłumaczenia (polskie- autorstwa Mariusza Meszki and Joanny Nowak- zostało zaprezentowane w Krakowie w 1995 roku)- od angielskich po japońskie. Melodię hymnu (posłuchaj w formacie .mp3) przygotował Zdenek Ryjacek. Polski tekst hymnu:

 

1. Na Pregole siedem mostów stało, w tamtych czasach było to niemało. W Królewcu się radni radowali, że aż tyle mostów zbudowali.

2. Jak co wieczór tłumy wyruszyły, bo nad rzeką spacer bardzo miły. Wciąż myśl jedna im zaprząta głowę, jak tu wybrać tę właściwą drogę.

3. Przez most każdy raz przejść nie wracając, znów się w domu znaleźć nie zbaczając. Jakoś im to wcale nie wychodzi, most zostaje lub brakuje w drodze.

Ref. Eulera graf, to fakt oczywisty, wszystkie węzły są stopni parzystych. Doskonale znana jest o grafach to pierwsza z tez.

4. Aż nareszcie przypomnieli sobie o człowieku żyjącym w ich grodzie, Mistrzu geometrii i rachunków, On podpowie w którym iść kierunku.

5. Ale Euler smutnie kręci głową, bo odpowiedź na to ma gotową: “Jedna ścieżka nie wystarczy, aby pokryć mosty - nie ma na to rady.”

Ref. Eulera graf . . .

6. Nie pomogą tutaj dobre chęci, nic w nauce nie da się pokręcić. Mostów nowych nikt nie wybuduje, wodny żywioł tym co są – daruje.

7. Kiedy wojna przez Pregołę gnała, mosty wszystkie z ziemią wyrównała. Jednak imię Mistrza nad tą rzeką przeżyło już wiele długich wieków.

Ref. Eulera graf . . .

8. Nowej wiedzy Euler dał podstawy, przez co zyskał całe wieki sławy. My śladami Mistrza podążamy i naukę Jego rozwijamy.

9. Więc, Koledzy, na koniec powstańmy. Wznosząc toast głośno tak śpiewajmy: Niechaj żyje nam Teoria Grafów, obwieszczajmy ją całemu światu.

Tekst oryginalny, tłumaczenia (angielskie, niemieckie, polskie, węgierskie, afrikaans, esperanto, ukraińskie, indonezyjskie, francuskie) i nuty są dostępne w pliku .pdf (pochodzącym z strony Brief history of the Graph Theory Hymn, przygotowanej przez Zdenka Ryjacka).

Podobne artykuły


16
komentarze: 4 | wyświetlenia: 1695
14
komentarze: 5 | wyświetlenia: 1701
13
komentarze: 5 | wyświetlenia: 3145
12
komentarze: 1 | wyświetlenia: 6534
12
komentarze: 15 | wyświetlenia: 1145
34
komentarze: 17 | wyświetlenia: 4721
21
komentarze: 14 | wyświetlenia: 66614
21
komentarze: 23 | wyświetlenia: 27163
19
komentarze: 8 | wyświetlenia: 2851
16
komentarze: 7 | wyświetlenia: 54534
15
komentarze: 7 | wyświetlenia: 8333
6
komentarze: 4 | wyświetlenia: 14235
58
komentarze: 20 | wyświetlenia: 81130
 
Autor
Artykuł

Powiązane tematy





  oldml,  27/01/2008

Bardzo ciekawi artykuł, dobry do kategorii rozrywka, ale matematyka też może być. Ode mnie 5.

  Paweł,  14/07/2008

problem mostów królewieckich to podstawa algorytmiki :) choć może i dla niektórych być dobrą rozrywką ;)

  MrMath  (www),  05/04/2016

Szkoda tylko, że wizy do Kaliningradu są potrzebne.
PS. Teoria grafów, tak myślę, posiada niezwykłe możliwości.



Dodaj swoją opinię
W trosce o jakość komentarzy wymagamy od użytkowników, aby zalogowali się przed dodaniem komentarza. Jeżeli nie posiadasz jeszcze swojego konta, zarejestruj się. To tylko chwila, a uzyskasz dostęp do dodatkowych możliwości!
 

© 2005-2018 grupa EIOBA. Wrocław, Polska