Zagadnienie mostów królewieckich
Zagadnienie mostów królewieckich − problem, nad którym rzekomo głowili się mieszkańcy Królewca, a który rozwiązał w XVIII wieku Leonhard Euler[1][2][3][4].
Przez Królewiec przepływała rzeka Pregoła, w której rozwidleniach znajdowały się dwie wyspy. Ponad rzeką przerzucono siedem mostów, z których jeden łączył obie wyspy, a pozostałe mosty łączyły wyspy z brzegami rzeki. Problem, którym zainteresował się Euler, był następujący: czy można przejść kolejno przez wszystkie mosty tak, żeby każdy przekroczyć tylko raz[1][2][3][4].
Opis zagadnienia opublikowany przez Eulera w 1741 roku w pracy Solutio problematis ad geometriam situs pertinentis w Commentarii academiae scientiarum Petropolitanae (wolumen 8, strony 128-140)[5] jest uznawany za pierwszą pracę na temat teorii grafów.
Euler wykazał, że jest to niemożliwe, a decyduje o tym nieparzysta liczba wylotów mostów zarówno na każdą z wysp, jak i na oba brzegi rzeki. Rozważył przy tym także ogólniejszy problem, starając się ustalić warunki, które 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 (patrz graf eulerowski)[3][4]. Euler pokazał, że jest to możliwe wtedy i tylko wtedy, gdy liczba wierzchołków tego grafu, w których spotyka się nieparzysta liczba krawędzi, wynosi 0 lub 2. Doszedł także do wniosku, że aby przejść wszystkie krawędzie grafu i wrócić do punktu wyjścia, nie może on zawierać żadnych węzłów, w których spotyka się nieparzysta liczba krawędzi.
Przekształcenie schematu mostów w graf[edytuj | edytuj kod]
→
→
Lewy wierzchołek reprezentuje małą wyspę ze środka obrazka, prawy to wyspa z prawej (na rysunku widać tylko jej fragment), a górny i dolny wierzchołek, to brzegi rzeki.
Przypisy[edytuj | edytuj kod]
- ↑ a b Jerzy MIODUSZEWSKI. MOSTY KRÓLEWIECKIE: DWIEŚCIE LAT PÓŹNIEJ. „Delta”. 4 (1981).
- ↑ a b Mariusz Śliwiński: Mosty królewieckie. math.edu.pl. [dostęp 2014-09-11].
- ↑ a b c Iwo, Iwona Białynicki-Birula, Białynicka-Birula: Modelowanie rzeczywistości. Warszawa: Prószyński i S-ka SA, 2002, s. 14-18. ISBN 83-7255-103-0.
- ↑ a b c Grafy II, smurf.mimuw.edu.pl [dostęp 2017-06-18] (pol.).
- ↑ E53 -- Solutio problematis ad geometriam situs pertinentis (ang.). Euler Archive. [dostęp 2014-09-11].
Bibliografia[edytuj | edytuj kod]
Linki zewnętrzne[edytuj | edytuj kod]
- Eric W. Weisstein, Königsberg Bridge Problem, [w:] MathWorld [online], Wolfram Research [dostęp 2020-12-12] (ang.).
- Solutio problematis ad geometriam situs pertinentis – oryginalny artykuł Eulera (łac.)