Loading AI tools
problem matematyczny rozwiązany przez teorię grafów Z Wikipedii, wolnej encyklopedii
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 rzeka Pregoła, w której rozwidleniach znajdują 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.
→
→
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.