Zagadnienie mostów królewieckich.pdf

Zagadnienie mostów królewieckich

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?

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?

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?

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.

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).

Autor: adamklimowski

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: