Zagadnienie mostów królewieckich

Mieszkańcy Królewca w XVIII wieku przez długi czas głowili się nad pewną łamigłówką: przez miasto płynie rzeka Pregoła, która tworzy dwie wyspy. Przez tę rzekę prowadzi na wyspy w sumie siedem mostów. Czy podczas jednego niedzielnego spaceru można przejść wszystkie mosty, ale każdy dokładnie raz? Zobaczmy, jak mosty były rozmieszczone nad rzeką:

Czy możemy zacząć spacer w jakimś miejscu i przejść wszystkie mosty dokładnie raz? Możemy spróbować: zaczniemy w lewym dolnym rogu i pójdziemy w górę, a potem kolejno w prawo, tak:

Widzimy, że przeszliśmy sześć z siedmiu mostów, jeden most ominęliśmy. Możemy spróbować innej drogi…

Znów przeszliśmy tylko sześć z siedmiu mostów naszego Królewca. Wygląda na to, że jednym spacerem nie da się przejść każdego mostu dokładnie raz. Pewnego dnia na ten problem trafił znany matematyk Leonhard Euler. Co tam znany – Euler był prawdziwą legendą matematyki, od jego nazwiska pochodzi nawet nazwa liczby Eulera. Euler postanowił, że rozgryzie tę łamigłówkę. Zaczął od oznaczenia poszczególnych wysp i części miasta, do których i z których prowadziły mosty:

Euler przeprowadził teraz następujące rozumowanie: jeśli na jakąś wyspę prowadzi parzysta liczba mostów, możemy te mosty przejść podczas jednego spaceru, niezależnie od tego, gdzie zaczniemy. Krótko mówiąc, jednym mostem przychodzimy na wyspę, drugim wychodzimy – liczba mostów, których jeszcze nie przeszliśmy, zmniejszyła się o dwa. Aby przyjść na wyspę jednym mostem i wyjść drugim, potrzebujemy dwóch mostów. Jeśli na wyspę prowadzi sześć mostów, odwiedzimy tę wyspę trzy razy. Wyobraźmy sobie na przykład, że na wyspę B prowadziłyby cztery mosty w ten sposób:

Wtedy jednym niedzielnym spacerem możemy przejść wszystkie mosty, niezależnie od tego, gdzie zaczniemy. Spróbuj sam! Na rysunku zaznaczyłem jedną drogę. Wyobraźmy sobie teraz, że na wyspę B prowadziłby jeszcze jeden most z wyspy D:

Widzimy, że droga, którą wybraliśmy, nie pozwala nam przejść wszystkich mostów dokładnie raz. Musielibyśmy którymś z mostów wrócić na wyspę B, a potem przejść na wyspę D. Ale możemy wybrać inną drogę. Możemy zacząć spacer na wyspie B i wtedy jesteśmy w stanie przejść wszystkie mosty dokładnie raz:

Spacer zaczęliśmy na wyspie B, poszliśmy w górę na teren A, potem mostem z powrotem na B, na teren C, potem znów na wyspę B i na końcu na wyspę D. Jeśli więc zaczniemy na wyspie, do której prowadzi nieparzysta liczba mostów, jesteśmy w stanie przejść wszystkie jej mosty dokładnie raz. Albo możemy pójść zupełnie odwrotnie – zacząć na wyspie D, a skończyć na wyspie B.

Euler zauważył więc, że aby można było przejść wszystkie mosty dokładnie raz, musi być spełniony jeden z dwóch warunków: albo na każdą wyspę prowadzi parzysta liczba mostów, albo mogą być dwie wyspy, do których prowadzi nieparzysta liczba mostów – na jednej wyspie z nieparzystą liczbą mostów zaczynamy, a na drugiej kończymy. Wszystkie pozostałe wyspy muszą mieć parzystą liczbę mostów. Jeśli spojrzymy na pierwotne siedem mostów w Królewcu:

to widzimy, że do każdej wyspy prowadzi nieparzysta liczba mostów! Do wyspy A prowadzą 3, do B 5, do C 3 i do D też 3. Dlatego łamigłówka nie ma rozwiązania – nie da się przejść wszystkich siedmiu mostów dokładnie raz podczas jednego niedzielnego spaceru. Gdybyśmy zburzyli którykolwiek z mostów, nagle łamigłówka miałaby rozwiązanie. Zburzmy na przykład jeden z mostów między wyspami B i C:

Widzimy, że od razu do wyspy B prowadzą 4 mosty, a do wyspy C dwa mosty. W przypadku wysp A i D liczba mostów się nie zmieniła. Mamy więc nagle dwie wyspy z parzystą liczbą mostów i dwie wyspy z nieparzystą liczbą mostów. Jeśli zaczniemy spacer na jednej z wysp, do których prowadzi nieparzysta liczba mostów, możemy przejść wszystkie mosty dokładnie raz. Na rysunku zaczęliśmy na wyspie A, a skończyliśmy na wyspie D.

Leonhard Euler rozwiązał więc kolejny słynny problem matematyczny i mniej więcej położył podwaliny pod to, co dziś nazywamy teorią grafów, a na jego cześć graf, w którym można przejść wszystkie krawędzie dokładnie raz, nazywa się w języku teorii grafów grafem eulerowskim.