• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Zagadnienie mostów królewieckich

    Przeczytaj także...
    Teoria grafów to dział matematyki i informatyki zajmujący się badaniem własności grafów. Informatyka rozwija także algorytmy wyznaczające pewne właściwości grafów. Algorytmy te stosuje się do rozwiązywania wielu zadań praktycznych, często w dziedzinach na pozór nie związanych z grafami.Kaliningrad (ros. Калининград, do 4 czerwca 1946 Królewiec (do XVI w. także Królówgród), ros. Кёнигсберг, niem. Königsberg, łac. Regiomontium, prus. Kunnegsgarbs, lit. Karaliaučius) – stolica obwodu kaliningradzkiego – eksklawy Federacji Rosyjskiej, u ujścia Pregoły do Bałtyku, w historycznej krainie Sambii. Liczba ludności Kaliningradu w 2006 wynosiła 434,9 tys.
    Delta – matematyczno-fizyczno-informatyczno-astronomiczny miesięcznik popularny wydawany przez Uniwersytet Warszawski przy współpracy towarzystw naukowych: Polskiego Towarzystwa Matematycznego, Polskiego Towarzystwa Fizycznego, Polskiego Towarzystwa Astronomicznego i Polskiego Towarzystwa Informatycznego.
    Mapa królewieckich mostów z czasów Eulera. Dodatkowo wyróżniona jest rzeka i mosty.

    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.

    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.

    Pregoła (ros. Преголя, Priegola, niem. Pregel, lit. Prieglius, łac. Vatrulia) – rzeka w rosyjskim obwodzie kaliningradzkim. Długość Pregoły wynosi 123 km, licząc wraz z rzeką Węgorapa - 292 km, powierzchnia zlewni - 15 500 km².<|||||||||| |||||||||| |||||||||| |||||||||| |||||||||| |||||||||| |||||||||| |||||||||| |||||||||| |||||||||| - |||||||||| |||||||||| ||||||||||>

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

    Leonhard Euler (ur. 15 kwietnia 1707 w Bazylei, zm. 18 września 1783 w Petersburgu) – szwajcarski matematyk i fizyk; był pionierem w wielu obszarach obu tych nauk. Większą część życia spędził w Rosji i Prusach. Jest uważany za jednego z najbardziej produktywnych matematyków w historii.Krawędź grafu jest to para (zbiór dwuelementowy) wyróżnionych wierzchołków grafu, czyli takich, które są ze sobą połączone (sąsiednie). W reprezentacji graficznej jest to linia łącząca te wierzchołki. W szczególności krawędź może łączyć dwa te same wierzchołki i jest wówczas nazywana pętlą. Krawędź skierowaną, czyli będącą parą uporządkowanych wierzchołków, nazywamy łukiem.

    Przekształcenie schematu mostów w graf[]

    Konigsberg bridges.png7 bridges.svgKönigsberg graph.png
    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.


    Łacina, język łaciński (łac. lingua Latina, Latinus sermo) – język indoeuropejski z podgrupy latynofaliskiej języków italskich, wywodzący się z Lacjum (łac. Latium), krainy w starożytnej Italii, na północnym skraju której znajduje się Rzym.

    Przypisy

    1. Jerzy MIODUSZEWSKI. MOSTY KRÓLEWIECKIE: DWIEŚCIE LAT PÓŹNIEJ. „Delta”. 4 (1981). 
    2. Mariusz Śliwiński: Mosty królewieckie. math.edu.pl. [dostęp 2014-09-11].
    3. E53 -- Solutio problematis ad geometriam situs pertinentis (ang.). Euler Archive. [dostęp 2014-09-11].

    Bibliografia[]

  • O mostach królewieckich na Cut-the-knot (ang.)
  • Linki zewnętrzne[]

  • Solutio problematis ad geometriam situs pertinentis - oryginalny artykuł Eulera (łac.)



  • w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Reklama

    Czas generowania strony: 0.035 sek.