Zagadnienie mostów królewieckich

Mapa królewieckich mostów z czasów Eulera (mosty oraz rzekę wyróżniono)

Zagadnienie mostów królewieckich, problem mostów królewieckich[1] – kwestia, nad jaką rzekomo głowili się mieszkańcy Królewca, a którą rozwiązał w XVIII wieku Leonhard Euler[2][3][4][5].

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ć raz i tylko raz[2][3][4][5].

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)[6] 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)[4][5]. 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ć węzłów, w których spotyka się nieparzysta liczba krawędzi.

Przekształcenie schematu mostów w graf

→ →
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

Zobacz multimedia związane z tematem: Zagadnienie mostów królewieckich
  1. ↑ Euler Leonhard, [w:] Encyklopedia PWN [dostęp 2022-12-10] .
  2. ↑ a b JerzyJ. Mioduszewski JerzyJ., Mosty królewieckie: dwieście lat później, „Delta”, 4, 1981 [dostęp 2021-03-25] .
  3. ↑ a b MariuszM. Śliwiński MariuszM., Mosty królewieckie [online], math.edu.pl [dostęp 2021-03-25] .
  4. ↑ a b c IwoI. Białynicki-Birula IwoI., IwonaI. Białynicka-Birula IwonaI., Modelowanie rzeczywistości, Warszawa: Prószyński i S-ka SA, 2002, s. 14–18, ISBN 83-7255-103-0 .
  5. ↑ a b c Grafy II [online], Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego [dostęp 2021-03-25] .
  6. ↑ Solutio problematis ad geometriam situs pertinentis [online], Euler Archive [dostęp 2021-03-25]  (ang.).

Bibliografia

  • AlexanderA. Bogomolny AlexanderA., Graphs Fundamentals [online], Cut-the-knot [dostęp 2021-03-25]  (ang.).

Linki zewnętrzne

  • Eric W.E.W. Weisstein Eric W.E.W., Königsberg Bridge Problem, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12]  (ang.).
  • LeonhardL. Euler LeonhardL., Solutio problematis ad geometriam situs pertinentis [online], Euler Archive [dostęp 2021-03-25]  (łac.).
Encyklopedia internetowa (mathematical problem):
  • Britannica: topic/Konigsberg-bridge-problem
  • DSDE: Königsbergs_broproblem