Zagadka spaceru po mostach zapoczątkowała nowy dział matematyki

Nie mogąc uporać się z problemem, miejscowi „mędrcy” napisali list z prośbą o pomoc do znanego szwajcarskiego matematyka Leonharda Eulera. Euler zlekceważył sprawę, twierdząc, że ma ona „niewiele wspólnego z matematyką”. Miał poniekąd rację, bo odpowiedni dział matematyki wówczas jeszcze nie istniał. Jednak mimo tych wątpliwości w końcu Euler zagadkę siedmiu królewieckich mostów rozwiązał, nie zdając sobie sprawy, że w ten sposób zapoczątkował dwa nowe działy królowej nauk.

Czy gdybyś był mieszkańcem Królewca, to, patrząc na plan miasta (u góry na sąsiedniej stronie), zaprojektowałbyś ścieżkę przechodzącą raz przez każdy most? Powinieneś myśleć jak matematyk. Pierwszym krokiem w rozwiązaniu każdego problemu matematycznego jest usunięcie zbędnych informacji i pozostawienie tylko istotnych – to proces zwany abstrakcją. Cechami mapy nieistotnymi dla problemu są na przykład długości i kierunki mostów lub powierzchnie lądów – wszystko to można pominąć. Liczy się tylko to, które lądy łączą się z innymi i ile razy. Możemy więc stworzyć znacznie prostszy diagram, składający się jedynie z kółek i linii, reprezentujących lądy i mosty (u dołu sąsiedniej strony).

We współczesnym języku matematycznym nazywa się taki schemat grafem. Kółka są „wierzchołkami”, a linie „krawędziami”. Teoria grafów jest dziś ważną, szeroko stosowaną dziedziną matematyki i informatyki. Grafy nie muszą dotyczyć lądów i mostów. Mogą reprezentować sieci społeczne, reakcje chemiczne, sieci neuronowe, sieć WWW lub dowolne inne dane obejmujące relacje między parami elementów.

Abstrakcja pozwala przełożyć konkretny problem układu mostów w mieście na problem ogólny, dotyczący wszystkich grafów: czy dla grafu z dowolną liczbą wierzchołków i krawędzi istnieje ścieżka, która przechodzi przez każdą krawędź dokładnie raz. Okazuje się, że zaskakująco prosty test umożliwia odpowiedź na to pytanie dla dowolnego grafu: policz, ile krawędzi (mostów) wychodzi z każdego wierzchołka (lądu). Jeśli wszystkie te liczby są parzyste lub nieparzyste są tylko dwie, to taka ścieżka istnieje; w przeciwnym razie ścieżki nie da się wytyczyć.

Aby to wyjaśnić, wyobraźmy sobie ścieżkę w grafie, która przechodzi każdą krawędzią tylko raz, i rozważmy wierzchołek przechodni na tej ścieżce (nie początkowy i nie końcowy). Jeśli z takiego wierzchołka wychodzi wiele krawędzi, to ścieżka będzie go „odwiedzać” wielokrotnie, ale po każdym wejściu będzie musiała z niego wyjść inną krawędzią. Zatem przy każdym „zaliczeniu” przechodniego wierzchołka, zostaną „zaliczone” dwie krawędzie, a tak będzie tylko wtedy, gdy każdy przechodni wierzchołek będzie połączony z innymi parzystą liczbą krawędzi. Wyjątkami mogą być tylko początek i koniec ścieżki, ponieważ nie trzeba wchodzić do wierzchołka początkowego, ani wychodzić z końcowego. Jeśli zatem mamy dokładnie dwa wierzchołki z nieparzystą liczbą krawędzi, to nasza ścieżka jest możliwa wtedy, gdy w jednym z tych wierzchołków zaczniemy, a w drugim skończymy. Jeżeli zaś każdy wierzchołek obsługuje parzystą liczbę krawędzi, to ścieżka zaczyna się i kończy w tym samym wierzchołku, tworząc pętlę.

W teorii grafów są to elementarne wnioski, a ścieżki, przechodzące raz przez każdą krawędź, zwane są ścieżkami Eulera. Ściśle rzecz biorąc, powyższe warunki dotyczą tylko niemożliwości wyznaczenia ścieżki Eulera. Dowód, że przy tych warunkach ścieżka zawsze istnieje, pojawił się później. Wracając do mostów w Królewcu: jak widać, każdy z czterech wierzchołków obsługuje nieparzystą liczbę krawędzi, co oznacza, niestety, że pruscy spacerowicze szukali na próżno.

Przy okazji warto zauważyć, że znalezienie ścieżki w grafie, która przechodziłaby dokładnie raz przez każdy wierzchołek (w Królewcu przez lądy, a nie mosty), co wydaje się pokrewnym problemem, to w istocie całkiem inne zagadnienie. Prostym testem można wykluczyć ścieżkę Eulera, ale nie znamy żadnej ogólnej, wydajnej procedury dla analogicznego wariantu dotyczącego wierzchołków. Stanowi to zagadkę zwaną problemem hamiltonowskim, należącym do klasy problemów powszechnie uważanych za obliczeniowo nierozwiązywalne.

Chociaż Euler początkowo lekceważył problem mostów, jednak w końcu wciągnęła go niemożność uporania się z nim za pomocą znanych wówczas narzędzi. Napisał do przyjaciela: „To banalne pytanie, ale wydało mi się warte uwagi, ponieważ ani geometria, ani algebra, ani obliczenia nie wystarczają do jego rozwiązania”. W czasach Eulera geometria dotyczyła pojęć ilościowych, jak odległość, kąt i pole. Problem mostów wydawał się geometryczny, ale nie operował żadnymi wymiarami. Chodziło o nową abstrakcję, która ignoruje tradycyjną geometrię, a respektuje jako najistotniejsze połączenia parami.

Pomysł zredukowania mapy Królewca do prostego grafu może wydawać się oczywisty z perspektywy czasu, ale do tego sprowadza się większość abstrakcji. Historia matematyki stanowi właściwie historię potęgi abstrakcji. Gdyby starożytni matematycy stawali przed problemami ilościowymi dotyczącymi na przykład pomarańczy, pereł lub Ziemi, mogliby opracować własny język i techniki radzenia sobie z każdym nowym wyzwaniem. Przedsięwzięcie staje się jednak o wiele łatwiejsze i bardziej zrozumiałe wtedy, gdy uświadomimy sobie, że wszystkie te pozornie różne obiekty reprezentują ten sam obiekt wyższego rzędu: sferę. Po nazwaniu i zdefiniowaniu abstrakcji ludzie, którzy nigdy nie mieli ze sobą kontaktu, mogą ze sobą współpracować i nie wyważać otwartych drzwi.

Praca Eulera nie tylko zapoczątkowała teorię grafów, ale także stanowiła zalążek innej gałęzi matematyki – topologii. To nauka badająca własności geometryczne obiektów niezmieniające się przy ich odkształcaniu – jakby obiekty te były wykonane z gumy. Mamy zatem jeden poziom abstrakcji, który przenosi nas od obiektów świata rzeczywistego – takich jak pomarańcze, góry lub kostki do gry – do brył (kule, piramidy, sześciany). Natomiast topologia wprowadza inny poziom abstrakcji, na którym postrzegamy kule, piramidy i sześciany jako obiekty wyższego rzędu. Topolodzy uznają te bryły za równoważne, ponieważ każdą z nich można przekształcić w inną w elastycznym świecie – w przeciwieństwie na przykład do nierównoważnego im obwarzanka, bo zachowuje on otwór bez względu na to, jak go zdeformujemy.

Pomijając dane ilościowe na mapie Królewca, Euler zapoczątkował nowy rodzaj myślenia geometrycznego, oderwanego od liczb określających odległości i kąty, które dominowały w tej dziedzinie przez tysiąclecia. Teoria grafów i topologia wciąż się rozwijają i znajdują praktyczne zastosowanie, a zawdzięczamy to w pewnym stopniu także spacerowiczom sprzed trzech wieków.