Siedem mostów w Królewcu

Mieszkańcy XVIII-wiecznego Królewca od dawna rozwiązują zagadkę: rzeka Pregoła przepływa przez miasto, tworząc dwie wyspy. Przez rzekę prowadzi siedem mostów na wyspy. Czy możliwe jest przejście przez wszystkie mosty podczas jednego niedzielnego spaceru, ale tylko raz przez każdy z nich? Przyjrzyjmy się, jak zbudowano mosty nad rzeką:

Czy jest możliwe, abyśmy rozpoczęli nasz spacer w pewnym miejscu i przeszli przez wszystkie mosty tylko raz? Możemy spróbować, zaczynając od lewego dolnego rogu i idąc w górę, a następnie stopniowo w prawo, w ten sposób:

Widzimy, że przeszliśmy przez sześć z siedmiu mostów i ominęliśmy jeden z nich. Możemy spróbować inaczej...

Ponownie, minęliśmy tylko sześć z siedmiu mostów naszego Mostu Króla. Przejście przez każdy most tylko raz wydaje się prawie niemożliwe. Pewnego dnia słynny matematyk Leonhard Euler natknął się na ten problem. Jaki słynny - Euler był matematyczną legendą, od którego nazwiska pochodzi nawet nazwa liczby Eulera. Euler pomyślał, że rozwiąże tę zagadkę. Zaczął od zaznaczenia wysp lub części miasta, do i z których prowadziły mosty:

Euler przeprowadził teraz następujące rozumowanie: jeśli wyspa ma parzystą liczbę mostów prowadzących do niej, możemy przejść przez te mosty w jednym spacerze, gdziekolwiek zaczniemy. Krótko mówiąc, przybywamy na wyspę jednym mostem i opuszczamy ją innym - liczba mostów, których nie możemy już przekroczyć, została zmniejszona o dwa. Aby użyć jednego mostu do dotarcia na wyspę, a drugiego do jej opuszczenia, potrzebujemy dwóch mostów. Jeśli na wyspę prowadzi sześć mostów, odwiedzamy ją trzy razy. Załóżmy na przykład, że na wyspę B prowadzą cztery mosty:

Wtedy możemy przejść przez wszystkie mosty podczas jednego niedzielnego spaceru, niezależnie od tego, gdzie zaczynamy. Spróbuj! Na obrazku zaznaczyłem jedną ścieżkę. Załóżmy jednak, że z wyspy D na wyspę B prowadzi jeszcze jeden most:

Widzimy, że wybrana przez nas ścieżka nie pozwoli nam przejść przez wszystkie mosty tylko raz. Musielibyśmy wrócić na wyspę B przez jeden z mostów, a następnie udać się na wyspę D. Możemy jednak wybrać inną drogę. Możemy rozpocząć naszą wędrówkę na wyspie B i wtedy będziemy mogli przejść przez wszystkie mosty tylko raz:

Zaczęliśmy naszą wędrówkę na wyspie B, udaliśmy się na terytorium A, następnie przeszliśmy mostem z powrotem na wyspę B, na terytorium C, następnie z powrotem na wyspę B, a na końcu na wyspę D. W ten sposób, jeśli zaczniemy na moście, który ma nieparzystą liczbę mostów, jesteśmy w stanie przejść przez wszystkie mosty tylko raz. Możemy też zrobić odwrotnie - zacząć na wyspie D, a skończyć na wyspie B.

Euler zauważył więc, że aby móc przejść przez wszystkie mosty tylko raz, wszystkie wyspy muszą mieć parzystą liczbę mostów lub mogą istnieć dwie wyspy, które mają nieparzystą liczbę mostów - zaczynamy na jednej wyspie z nieparzystą liczbą mostów i kończymy na drugiej. Wszystkie pozostałe wyspy muszą mieć parzystą liczbę mostów. Jeśli spojrzymy na oryginalne siedem mostów w King:

zobaczymy, że każda wyspa ma nieparzystą liczbę mostów! Wyspa A ma 3 mosty, B ma 5 mostów, V ma 3 mosty, a D również ma 3 mosty. Dlatego łamigłówka nie ma rozwiązania - nie ma możliwości, abyśmy przeszli przez wszystkie siedem mostów tylko raz podczas jednego niedzielnego spaceru. Gdybyśmy zburzyli którykolwiek z mostów, nagle zagadka miałaby rozwiązanie. Na przykład, zburzmy jeden z mostów między wyspami B i C:

Widzimy, że nagle wyspa B ma cztery mosty, a wyspa C ma dwa mosty. Wyspy A i D mają taką samą liczbę mostów. Nagle mamy dwie wyspy z parzystą liczbą mostów i dwie wyspy z nieparzystą liczbą mostów. Jeśli zaczniemy spacer na jednej z wysp o nieparzystej liczbie mostów, możemy przejść przez wszystkie mosty tylko raz. Na rysunku zaczęliśmy na wyspie A, a skończyliśmy na wyspie D.

Tak więc Leonhard Euler rozwiązał kolejny słynny problem matematyczny i mniej więcej położył podwaliny pod to, co dziś nazywamy teorią graf ów, a według jego obliczeń "spacer, w którym przechodzimy przez wszystkie mosty tylko raz" nazywany jest grafem eulerowskim w języku teorii grafów.