Zagadnienie mostów królewieckich
Siedem mostów w Królewcu to historycznie znany problem matematyczny. Leonhard Euler rozwiązał ten problem w 1735 roku. Doprowadziło to do powstania teorii grafów. To z kolei doprowadziło do rozwoju topologii.
Miasto Królewiec w Prusach (obecnie Kaliningrad, Rosja) było położone po obu stronach rzeki Pregel. W jego skład wchodziły dwie duże wyspy, które były połączone ze sobą i z lądem stałym siedmioma mostami.
Problem polegał na tym, aby znaleźć sposób na przejście przez miasto, przechodząc przez każdy most raz i tylko raz. Na wyspy nie można było dotrzeć inną drogą niż przez mosty. Każdy z mostów musiał być pokonany w całości za każdym razem. Spacer nie musi zaczynać się i kończyć w tym samym miejscu. Euler udowodnił, że problem ten nie ma rozwiązania.
Mapa Królewca w czasach Eulera przedstawiająca faktyczny układ siedmiu mostów, z zaznaczeniem rzeki Pregel i mostów
Analiza Eulera
Po pierwsze, Euler zauważył, że wybór trasy wewnątrz każdej masy lądowej nie ma znaczenia. Jedyną ważną własnością trasy jest kolejność, w jakiej mosty są przekraczane. Zmienił więc problem na pojęcia abstrakcyjne. W ten sposób stworzył podstawy teorii grafów. Usunął wszystkie cechy oprócz listy mas lądowych i łączących je mostów. W języku teorii grafów zastąpił każdą masę lądową abstrakcyjnym "wierzchołkiem" lub węzłem. Następnie zastąpił każdy most abstrakcyjnym połączeniem, "krawędzią". Krawędź (droga) zapisywała, które dwa wierzchołki (masy lądowe) były połączone. W ten sposób utworzył graf.
→
→ 
Narysowany graf jest abstrakcyjnym obrazem problemu. Krawędzie można więc łączyć w dowolny sposób. Ważne jest tylko to, czy dwa punkty są połączone, czy nie. Zmiana obrazu grafu nie powoduje zmiany samego grafu.
Następnie Euler zauważył, że (z wyjątkiem punktów końcowych spaceru), ilekroć ktoś wchodzi do wierzchołka przez most, tylekroć opuszcza ten wierzchołek przez most. W dowolnym spacerze grafu liczba wejść do wierzchołka jest równa liczbie wyjść z niego. Jeśli każdy most został przekroczony dokładnie raz, to wynika z tego, że dla każdej masy lądowej (z wyjątkiem tych wybranych na początek i koniec) liczba mostów dotykających tej masy lądowej musi być parzysta. Wynika to z tego, że jeśli jest n mostów, to jest on przecinany dokładnie 2n razy. Jednak wszystkie cztery masy ziemi w oryginalnym problemie są dotykane przez nieparzystą liczbę mostów (jeden jest dotykany przez 5 mostów, a każdy z pozostałych trzech przez 3). Istnieją co najwyżej dwie bryły, które mogą być punktami końcowymi spaceru. Zatem teza, że spacer przechodzi przez każdy most tylko raz, prowadzi do sprzeczności.
W języku współczesnym Euler pokazuje, że to, czy spacer przez graf przecinający każdą krawędź raz jest możliwy, czy nie, zależy od stopni węzłów. Stopień węzła to liczba krawędzi, które go dotykają. Euler pokazuje, że warunkiem koniecznym przejścia jest to, by graf był połączony i miał dokładnie zero lub dwa węzły nieparzystego stopnia. Ten wynik podany przez Eulera został później udowodniony przez Carla Hierholzera. Taki spacer jest obecnie nazywany ścieżką Eulera lub spacerem Eulera. Jeśli istnieją węzły nieparzystego stopnia, to każda ścieżka eulerowska będzie zaczynać się w jednym z nich i kończyć w drugim. Ponieważ graf reprezentujący historyczny Królewiec ma cztery węzły nieparzystego stopnia, nie może mieć ścieżki eulerowskiej.
Praca Eulera została przedstawiona w Akademii Petersburskiej 26 sierpnia 1735 roku. Została ona opublikowana jako Solutio problematis ad geometriam situs pertinentis (Rozwiązanie problemu dotyczącego geometrii położenia) w czasopiśmie Commentarii academiae scientiarum Petropolitanae w 1741 roku. Jest on dostępny w języku angielskim w The World of Mathematics.
Znaczenie w historii matematyki
W historii matematyki, rozwiązanie problemu mostu w Królewcu przez Eulera jest uważane za pierwsze twierdzenie teorii grafów. Teoria grafów jest obecnie powszechnie uważana za gałąź kombinatoryki.
Obecny stan mostów
Dwa z siedmiu oryginalnych mostów zostały zniszczone podczas bombardowania Królewca w czasie II wojny światowej. Dwa kolejne zostały później rozebrane. Na ich miejscu zbudowano nowoczesną autostradę. Trzy pozostałe mosty pozostały, choć tylko dwa z nich pochodzą z czasów Eulera (jeden został przebudowany w 1935 roku). Tak więc w 2000 roku w Kaliningradzie było pięć mostów.
Z punktu widzenia teorii grafów, dwa z węzłów mają teraz stopień 2, a pozostałe dwa stopień 3. Dlatego ścieżka eulerowska jest teraz możliwa, ale ponieważ musi zaczynać się na jednej wyspie i kończyć na drugiej, jest niepraktyczna dla turystów.
Powiązane strony
- Gra ikosjańska
- ścieżka hamiltonowska
- Woda, gaz i energia elektryczna
- Problem wędrownego komiwojażera
Pytania i odpowiedzi
Q: Na czym polega problem Siedmiu Mostów w Królewcu?
O: Siedem mostów w Królewcu to słynny problem matematyczny, który polega na znalezieniu sposobu na przejście przez miasto, przechodząc przez każdy z siedmiu mostów raz i tylko raz.
P: Kto rozwiązał problem Siedmiu Mostów w Królewcu?
O: Leonhard Euler rozwiązał problem Siedmiu Mostów w Królewcu w 1735 roku.
P: Do czego doprowadziło rozwiązanie problemu Siedmiu Mostów w Królewcu?
O: Rozwiązanie problemu Siedmiu Mostów w Królewcu doprowadziło do powstania teorii grafów, która następnie doprowadziła do rozwoju topologii.
P: Gdzie znajduje się Królewiec?
O: Królewiec znajduje się w Prusach, które obecnie są częścią Kaliningradu w Rosji.
P: Jaki był układ Królewca?
O: Królewiec został rozplanowany po obu stronach rzeki Pregel i obejmował dwie duże wyspy, które były połączone ze sobą i lądem siedmioma mostami.
P: Jakie były wymagania dotyczące rozwiązania problemu Siedmiu Mostów Królewca?
O: Problem wymagał znalezienia sposobu na przejście przez miasto, przechodząc przez każdy most raz i tylko raz, przy czym każdy most musiał być za każdym razem całkowicie przekroczony. Na wyspy nie można było dotrzeć inną drogą niż przez mosty, a spacer nie musiał zaczynać się i kończyć w tym samym miejscu.
P: Czy Euler udowodnił, że problem siedmiu mostów w Królewcu ma rozwiązanie?
O: Nie, Euler udowodnił, że problem Siedmiu Mostów w Królewcu nie ma rozwiązania.
