Siedem mostów Królewca i narodziny teorii grafów w jednej historii

Królewiec, siedem mostów i jedna uparta zagadka

Historia siedmiu mostów Królewca zaczyna się jak lokalna anegdota, a kończy jako jeden z najważniejszych momentów w dziejach matematyki. W XVIII wieku mieszkańcy Królewca (dzisiejszego Kaliningradu) zastanawiali się nad z pozoru prostym problemem spacerowym: czy da się przejść przez wszystkie mosty w mieście dokładnie raz i wrócić do punktu wyjścia? Nikt jeszcze wtedy nie używał słów takich jak teoria grafów czy ścieżka Eulera. Było miasto, rzeka, wyspy i mosty. I była ciekawość.

To pytanie, zadawane z nudów w niedzielne popołudnia, okazało się na tyle uporczywe, że trafiło w końcu na biurko jednego z najbłyskotliwszych umysłów epoki – Leonharda Eulera. Zderzenie zwyczajnego miejskiego problemu z abstrakcyjnym myśleniem matematycznym dało początek nowej dziedzinie: teorii grafów. Droga od drewnianych mostów do czystych rysunków z kropkami i kreskami zmieniła nie tylko matematykę, ale także to, jak planuje się drogi, projektuje sieci komputerowe czy optymalizuje logistykę.

Siedem mostów Królewca i narodziny teorii grafów to jedna historia, w której bardzo wyraźnie widać, jak konkretne, namacalne pytanie może wywołać lawinę abstrakcyjnych idei. Zanim pojawią się skomplikowane pojęcia, warto prześledzić, jak wyglądał sam Królewiec, gdzie leżały mosty i co dokładnie próbowano osiągnąć, wędrując po nich tam i z powrotem.

Miasto nad Pregołą: jak wyglądał Królewiec i jego siedem mostów

Geografia Królewca i rola rzeki Pregoły

Królewiec był położony nad rzeką Pregołą, która w obrębie miasta rozdzielała się na odnogi, tworząc układ wysp i lądów połączonych mostami. Dla mieszkańców rzeka była jednocześnie błogosławieństwem i ograniczeniem: zapewniała handel i obronność, ale wymuszała budowę przepraw, aby swobodnie przemieszczać się między częściami miasta.

W klasycznym ujęciu zagadki siedmiu mostów Królewca wyróżnia się cztery obszary lądu:

• dwa brzegi rzeki (części „stałego” lądu),
• dużą wyspę na środku (Kneiphof),
• mniejszą wyspę (Lomse), choć w popularnych rysunkach bywa przedstawiana różnie lub pomijana, a układ sprowadza się do czterech istotnych obszarów.

Rzeka i jej odnogi tworzyły naturalne granice. Dla przechodnia miało to znaczenie praktyczne: żeby przejść z jednej dzielnicy do drugiej, trzeba było skorzystać z konkretnego mostu. Dla matematyka – te granice stały się węzłami w sieci, a mosty liniami łączącymi te węzły.

Siedem mostów Królewca – co dokładnie je wyróżniało

Mosty w Królewcu nie były symetrycznie rozłożone wokół wysp. Ich liczba i rozmieszczenie sprawiały, że naturalnie rodziło się pytanie, czy istnieje trasa pozwalająca przejść przez wszystkie z nich dokładnie raz. Kluczowe jest tutaj słowo „dokładnie”: ani mniej, ani więcej. Żaden most nie mógł zostać ominięty ani wykorzystany dwukrotnie.

Można sobie wyobrazić mapę Królewca jako zarys rzeki z dwoma wyspami po środku. Mosty łączyły:

• lewą część lądu z wyspą,
• prawą część lądu z wyspą,
• między samymi wyspami,
• oraz dodatkowo tworzyły „nadmiar” połączeń, dzięki czemu powstawał dość gęsty układ przepraw.

W doświadczeniu spacerujących po mieście problem był bardzo konkretny: każdy most jest w zasadzie jedynym punktem przekroczenia rzeki w danym miejscu. Raz przejdziesz – nie ma odwrotu, jeśli chcesz dotrzymać zasady niepowtarzania przejść. Po kilku próbach powstawało poczucie, że trasa idealna albo nie istnieje, albo jest sprytnie ukryta. I właśnie ta trudność przyciągnęła uwagę Eulera.

Dlaczego mieszkańcy w ogóle zastanawiali się nad taką trasą

Współczesnemu czytelnikowi zagadka siedmiu mostów Królewca może wydawać się typową łamigłówką logiczną jak z książki z zadaniami dla uczniów. W tamtych czasach była raczej lokalną ciekawostką, rodzajem miejskiej legendy: „podobno da się przejść wszystkie mosty tylko raz”.

Takie pytania rodzą się zwykle z połączenia nudy i rywalizacji. Ktoś obiecuje, że zna trasę; ktoś inny próbuje ją odtworzyć. Po kilkunastu próbach wyłania się wniosek: trzeba spytać kogoś, kto „zna się na rachunkach”. W ten sposób problem trafił w końcu do Eulera, który początkowo zlekceważył go jako zwykłą zabawę, a później dostrzegł w nim idealny materiał do rozwijania nowego sposobu myślenia.

Istotna jest tu jedna rzecz: zagadka zrodziła się z praktycznej sytuacji – z mapy realnego miasta. Matematyka zaczęła się pojawiać dopiero wtedy, gdy ktoś spróbował opisać tę sytuację w sposób pozbawiony szczegółów topograficznych, odrzucając kształt rzeki, odległości, ulice i budynki, a zostawiając jedynie strukturę połączeń.

Od mapy do schematu: jak Euler „zobaczył” Królewiec jako graf

Rezygnacja z geometrii: kształt nie ma znaczenia

Kluczowy przełom w historii siedmiu mostów Królewca polegał na tym, że Euler zrozumiał: dla rozwiązania zadania nie ma znaczenia dokładny kształt miasta. Nie liczą się metry, kąty, ani rozmiar wysp. Istotne jest wyłącznie to, które obszary są połączone mostami oraz ile mostów prowadzi między poszczególnymi obszarami.

W praktyce oznaczało to coś niezwykle radykalnego: można „pognieść” mapę, skrócić rzekę, wyprostować brzegi, a nawet zupełnie zmienić ułożenie wysp na kartce papieru, dopóki zachowuje się relacje: gdzie jest wyspa, gdzie stały ląd i ile mostów łączy jedne z drugimi. Z perspektywy współczesnej to oczywiste – stosujemy schematy metra, w których odległości są symboliczne, ale połączenia zachowane. Dla matematyki tamtego czasu było to jednak jakościowo nowe spojrzenie.

Euler wykonał mentalne „spłaszczenie” sytuacji: mapa Królewca zamieniła się w rysunek z kilkoma punktami i kilkoma liniami. Od tej chwili można było mówić nie o konkretnych mostach, ale o krawędziach łączących wierzchołki. Zniknęły rzeki i wyspy; pojawił się prosty schemat – zalążek grafu.

Abstrakcyjny model: wyspy jako wierzchołki, mosty jako krawędzie

Aby uchwycić istotę zagadki, Euler zaproponował zastąpienie:

• każdego obszaru lądu – jednym punktem (dziś nazwalibyśmy go wierzchołkiem),
• każdego mostu – jedną linią łączącą odpowiednie punkty (dzisiejszą krawędzią grafu).

W ten sposób Królewiec stał się grafem o czterech wierzchołkach, połączonych siedmioma krawędziami. Nieistotne były już odległości między mostami ani to, czy biegną one po łuku, czy prosto. Liczyło się jedynie tyle: które punkty są ze sobą połączone i ile razy.

Taki model ma ogromną zaletę: można całkowicie odciąć się od detali, które nie mają wpływu na odpowiedź. Jeżeli pytanie dotyczy tylko tego, czy da się przejść przez wszystkie mosty dokładnie raz, to nie jest ważne, czy spacer długo trwa, czy mosty są blisko siebie, ani czy jeden z nich jest drewniany, a drugi kamienny. Model wyjęty z geograficznego kontekstu pozwala dostrzec ogólną regułę zamiast przypadkowego kształtu konkretnego miasta.

Jak wyglądał graf Królewca w notacji współczesnej

W zapisie współczesnej teorii grafów układ Królewca można potraktować jako graf nieskierowany (krawędzie nie mają kierunku – przejście z A do B jest tym samym, co z B do A). Wierzchołki reprezentują cztery obszary lądu, a krawędzie siedem mostów. Niech symbolem:

• A – oznaczymy jedną część stałego lądu,
• B – drugą część stałego lądu,
• C – główną wyspę (Kneiphof),
• D – dodatkowy obszar/wyspę lub fragment brzegu, zależnie od wariantu rysunku.

Między wierzchołkami istnieje kilka krawędzi równoległych, tzn. więcej niż jeden most łączy dwie te same części lądu. Matematycznie jest to multigraf: zamiast pojedynczej linii łączącej dwa punkty może ich być kilka, każda odpowiada innemu mostowi.

Rysunek jest prosty: cztery punkty w przybliżeniu w kształcie krzyża i między nimi siedem linii. To właśnie w liczbie i układzie tych linii ukryta była odpowiedź na pytanie, które dręczyło spacerowiczów nad Pregołą.

Od spaceru do dowodu: sformułowanie problemu w języku grafów

Jak dokładnie brzmiała matematyczna wersja zagadki

Po przejściu z mapy do modelu grafowego problem można zapisać bardzo precyzyjnie. Zamiast mówić o mieście i mostach, mówi się o grafie G, którego:

• wierzchołki reprezentują obszary lądu,
• krawędzie reprezentują mosty,
• graf jest nieskierowany – przejścia nie mają kierunku.

Matematyczna wersja pytania brzmi wtedy:

Czy w grafie G istnieje taka trasa, która przechodzi przez każdą krawędź dokładnie raz, zaczyna się i kończy w tym samym wierzchołku?

Taka trasa to właśnie cykl Eulera, chociaż sama nazwa powstała dopiero później na cześć Eulera. W wariancie mniej restrykcyjnym można zadać pytanie ogólniejsze: czy istnieje dowolna trasa, która przechodzi przez każdą krawędź dokładnie raz, ale niekoniecznie wraca do punktu wyjścia (tzw. ścieżka Eulera).

Formalne pojęcia: ścieżka, cykl, stopień wierzchołka

Aby móc precyzyjnie rozmawiać o tym, czy trasa przez wszystkie mosty istnieje, Euler potrzebował kilku pojęć, które dziś są podstawą teorii grafów.

Ścieżka i cykl w grafie

Ścieżka w grafie to sekwencja wierzchołków, w której każdy kolejny wierzchołek jest połączony krawędzią z poprzednim. Jeżeli ścieżka nie powtarza żadnej krawędzi, można ją nazwać ścieżką prostą względem krawędzi. Eulerowi chodziło dokładnie o takie ścieżki: przechodzimy każdą krawędź najwyżej raz.

Cykl to ścieżka, która zaczyna się i kończy w tym samym wierzchołku. Cykl Eulera to szczególny cykl – przechodzący przez wszystkie krawędzie grafu dokładnie raz. W kontekście siedmiu mostów Królewca cykl Eulera byłby idealnym „spacerem po mostach”: startujesz np. na wyspie, przechodzisz każdy most jeden raz i wracasz na wyspę.

Stopień wierzchołka – kluczowa liczba dla Eulera

Stopień wierzchołka w grafie to liczba krawędzi, które do niego przylegają. Jeśli dana część lądu ma trzy mosty, które do niej prowadzą, to odpowiadający jej wierzchołek ma stopień równy 3. To pojęcie okazało się fundamentalne. Euler odkrył, że odpowiedź na pytanie o istnienie ścieżki przez wszystkie mosty można wyczytać właśnie z parzystości stopni wierzchołków.

Myśl jest prosta: za każdym razem, gdy wchodzisz do jakiegoś wierzchołka po krawędzi, zwykle będziesz z niego wychodzić inną krawędzią (chyba że zaczynasz lub kończysz trasę w tym punkcie). Oznacza to, że wierzchołki, które są „wewnątrz” trasy, muszą mieć parzystą liczbę incydentnych krawędzi – każdemu wejściu odpowiada wyjście. Ta intuicja doprowadziła Eulera do uogólnienia daleko wykraczającego poza Królewiec.

Przepisanie miejskiego problemu na problem o parzystości

Gdy tylko wprowadzi się pojęcie stopnia wierzchołka, zagadka siedmiu mostów Królewca zaczyna przypominać zadanie z rachunków modulo 2 (parzystość). Można zadać sobie pytanie: jaka musi być liczba mostów wychodzących z każdej części lądu, aby idealny spacer po wszystkich mostach był możliwy?

Warunek parzystości: intuicja, którą da się narysować na serwetce

Rozumowanie, do którego doszedł Euler, można przeprowadzić bez wzorów – wystarczy wyobraźnia i kilka kresek. Wyobraźmy sobie dowolny wierzchołek, do którego dochodzą krawędzie. Jeśli przechodzimy przez wszystkie te krawędzie dokładnie raz, to:

• za każdym razem, gdy wchodzimy do wierzchołka pewną krawędzią, musimy z niego wyjść inną krawędzią,
• te wejścia i wyjścia „parują się” w pary: wejście–wyjście, wejście–wyjście, i tak dalej.

Żeby takie parowanie było możliwe, liczba krawędzi incydentnych z danym wierzchołkiem musi być parzysta. Inaczej zostanie „wystająca” krawędź, której nie da się sparować z żadnym przejściem. Wyjątkiem są co najwyżej dwa wierzchołki: punkt startu i punkt końcowy ścieżki. W nich możemy mieć o jedną krawędź „za dużo” – zaczynamy w jednym, kończymy w drugim, więc do jednego wchodzimy o raz mniej, niż wychodzimy, do drugiego odwrotnie.

Z tej prostej obserwacji rodzi się reguła, którą dziś formułuje się następująco:

• jeśli w grafie istnieje cykl Eulera (trasa zaczyna się i kończy w tym samym wierzchołku), to każdy wierzchołek ma stopień parzysty,
• jeśli istnieje ścieżka Eulera (trasa nie musi wracać do punktu wyjścia), to dokładnie 0 lub 2 wierzchołki mogą mieć stopień nieparzysty.

Wszystko rozgrywa się więc nie w geografii, ale w parzystości liczb: 2, 4, 6 kontra 1, 3, 5. Zagadkę miejskiego spaceru da się sprowadzić do zliczenia, ile „kresek” wychodzi z każdego punktu na rysunku.

Graf Królewca pod lupą: dlaczego odpowiedź brzmi „nie”

Gdy tylko policzymy stopnie wierzchołków w grafie odpowiadającym Królewcowi, obraz staje się jasny. Każdy obszar lądu ma nieparzystą liczbę mostów: jeden ma ich trzy, inny trzy, kolejne cztery – w sumie cztery wierzchołki o nieparzystych stopniach. To natychmiast narusza warunek Eulera.

Skoro ścieżka Eulera może mieć co najwyżej dwa wierzchołki o nieparzystym stopniu, a tutaj są cztery, żadna trasa przechodząca przez każdy most dokładnie raz nie istnieje. Nie trzeba próbować wszystkich możliwych kombinacji spaceru, rysować dziesiątek wariantów, zastanawiać się, czy „da się jakoś sprytniej zacząć”. Wystarczy jedno spojrzenie na stopnie wierzchołków i prosta reguła parzystości.

To właśnie ten moment jest w historii najciekawszy: problem, który przez lata był źródłem zabaw i walki na sprytne pomysły, został jednym ruchem odcięty od intuicji i zastąpiony krótkim, ogólnym argumentem. Liczy się nie to, jak próbujesz przejść mosty, lecz to, jakie są konieczne warunki istnienia takiej ścieżki.

Dowód Eulera w wersji „bez straszenia”

Formalna wersja rozumowania, którą Euler zapisał w swoim artykule, jest dla współczesnego czytelnika zaskakująco przystępna. Można ją streścić w kilku krokach:

1. Załóżmy, że istnieje ścieżka (lub cykl) przechodząca przez każdą krawędź dokładnie raz.
2. Rozważmy dowolny wierzchołek „wewnętrzny” tej ścieżki, czyli taki, który nie jest ani początkiem, ani końcem.
3. Za każdym razem, gdy wchodzimy do tego wierzchołka po jakiejś krawędzi, musimy go opuścić inną krawędzią, bo nie możemy utknąć (chcemy przejść wszystkie krawędzie).
4. Wejścia i wyjścia z tego wierzchołka tworzą pary, więc liczba użytych tam krawędzi jest parzysta.
5. Jeśli ścieżka jest cyklem (start = koniec), to nawet w punkcie startu/końca każde wejście ma odpowiadające mu wyjście, więc wszystkie wierzchołki muszą mieć stopień parzysty.
6. Jeśli start i koniec są różne, to w tych dwóch punktach jedna krawędź pozostaje „nie sparowana”, więc tam stopień może być nieparzysty.

Euler odwrócił następnie to rozumowanie: pokazał, że jeśli graf spełnia te warunki na parzystość stopni, to ścieżkę Eulera rzeczywiście da się skonstruować. Nie podał jednego, konkretnego algorytmu (to pojawiło się później), ale wystarczyło mu przekonanie, że parzystość nie jest tylko wskazówką – jest pełną charakterystyką problemu.

Narodziny nowego sposobu myślenia: od zadania do teorii

Dlaczego to było coś więcej niż rozwiązanie jednej zagadki

Matematycy rozwiązywali wcześniej konkretnie sformułowane problemy: policz pole, oblicz trajektorię, znajdź maksimum funkcji. Euler w sprawie mostów Królewca zrobił coś innego. Zamiast zatrzymać się na odpowiedzi „nie da się przejść wszystkich mostów tylko raz”, zapytał: jaką ogólniejszą własność mają wszystkie możliwe miasta, w których da się to zrobić?

To przejście od szczegółu do ogólności jest esencją narodzin nowej teorii. Nagle nie chodzi już o Królewiec, ani nawet o mosty. Chodzi o dowolny układ połączeń: sieć dróg, rur, kabli, korytarzy, po których chcemy „przejść” w określony sposób. Problem zyskał status uniwersalnego: stał się wzorem dla całej klasy zadań.

W tę samą szufladkę można dziś włożyć pytania typu:

• czy da się tak zaplanować odśnieżanie ulic, żeby żadnej nie przejeżdżać dwa razy (znany problem listonosza, wersja dla pługów śnieżnych),
• czy można zorganizować inspekcję mostów w mieście tak, aby każdy most sprawdzić raz, nie marnując przejazdów,
• czy robot sprzątający magazyn może odwiedzić wszystkie korytarze tylko jeden raz, startując i kończąc w bazie.

Za każdym takim pytaniem stoi ten sam szkielet: graf, ścieżki, stopnie, parzystość. Mosty Królewca są więc pierwszym „case study” teorii grafów – konkretnym scenariuszem, z którego wyrasta cała gałąź matematyki dyskretnej.

Od geometrii do kombinatoryki: zerwanie z „ciągłością”

Do XVIII wieku matematyka wyższa była przede wszystkim geometrią i analizą – pracowała na liniach ciągłych, funkcjach, wielkościach, które można dzielić bez końca. Euler, zajmując się mostami, zrobił krok w bok: zajął się obiektami dyskretnymi, policzalnymi. Nie mierzył długości mostów, nie liczył pól i objętości, tylko liczbę krawędzi dochodzących do wierzchołka.

To przejście od „ile metrów” do „ile połączeń” jest typowe dla współczesnej informatyki i teorii sieci, ale w czasach Eulera było świeże. W tle rodziła się matematyka kombinatoryczna: liczenie konfiguracji, badanie własności struktur, które można opisać w kategoriach „ile”, „które z którymi”, „jak są połączone”.

Co ważne, ta zmiana nie polegała tylko na dodaniu nowego działu obok istniejących. Wymusiła też nowe narzędzia: dowody oparte na policzalności, na inwariantach (wielkościach, które nie zmieniają się przy pewnych przekształceniach), na sprytnym grupowaniu elementów. Parzystość stopni wierzchołków to właśnie inwariant: można dowolnie rysować graf, przesuwać punkty, wyginać linie, a liczba krawędzi dochodzących do danego wierzchołka się nie zmieni.

Jak Euler opisał swoje odkrycie (i jak długo ma ten tekst)

Artykuł Eulera o mostach Królewca ukazał się w 1736 roku pod łacińskim tytułem mówiącym o „probleme geometricum”. Co ciekawe, sam Euler twierdził, że zagadki nie można nazwać geometryczną w tradycyjnym sensie, bo nie odwołuje się ona do miar, kątów ani proporcji, lecz do czegoś bardziej elementarnego: samego istnienia połączeń.

Tekst jest z dzisiejszej perspektywy dość krótki. Główne idee – wprowadzenie modelu, policzenie stopni, stwierdzenie warunku koniecznego i wystarczającego – zajmują zaledwie kilkanaście stron. A jednak to właśnie tam pojawia się pierwszy raz w tak wyraźnej formie spojrzenie grafowe: obiekty jako punkty, relacje jako linie, własności globalne wynikające z lokalnych liczb.

Euler nie mówił jeszcze o „teorii grafów”, nie używał też dzisiejszej terminologii. Mimo to jego analiza Królewca jest często wskazywana jako moment symboliczny: od tej chwili wiadomo, że zadając pytania o sieci połączeń, można dojść do silnych, ogólnych wniosków – i to przy użyciu bardzo prostego aparatu.

Od rzeki Pregoły do współczesnych sieci: echa Królewca dzisiaj

Mosty, kable, połączenia: gdzie wszędzie „mieszka” graf

Współczesne zastosowania idei grafów idą nieporównanie dalej niż planowanie spaceru. Gdziekolwiek pojawia się pytanie „co jest połączone z czym”, można spróbować zastosować tę samą abstrakcję, która kiedyś zamieniła Królewiec w cztery punkty i siedem linii.

Najbardziej namacalne przykłady to:

• sieci transportowe – lotniska jako wierzchołki, połączenia lotnicze jako krawędzie; podobnie z liniami kolejowymi czy liniami autobusowymi,
• sieci energetyczne i wodociągowe – stacje transformatorowe jako wierzchołki, linie wysokiego napięcia jako krawędzie; ujęcia wody i rurociągi opisywane podobnie,
• sieci komputerowe – routery, serwery i urządzenia końcowe jako wierzchołki, kable i łącza bezprzewodowe jako krawędzie,
• sieci społeczne – ludzie jako wierzchołki, znajomości, relacje zawodowe czy powiązania rodzinne jako krawędzie.

W każdym z tych kontekstów można zadawać pytania w stylu królewieckim: czy da się przejść każdą krawędź raz, odwiedzić każdy wierzchołek, znaleźć najkrótszą trasę łączącą zadane punkty. To już inny zestaw problemów (ścieżki Hamiltona, najkrótsze ścieżki, spójność grafu), ale wspólny rdzeń pozostaje ten sam: uproszczenie rzeczywistości do struktury połączeń.

Ścieżki Eulera w praktyce: od listonosza do inspektora mostów

Choć klasyczny problem z Królewca nie ma rozwiązania, idea drzemie dziś w wielu praktycznych zastosowaniach. Typowy scenariusz wygląda tak: mamy sieć połączeń (ulice, rurociągi, linie kontrolne), a zadaniem jest tak zaplanować trasę, by każdą krawędź odwiedzić co najmniej raz, minimalizując powtórki.

Jeżeli stopnie wszystkich wierzchołków są parzyste, sytuacja jest idealna – istnieje cykl Eulera: wystarczy raz przejść każdą ulicę lub odcinek rurociągu. Jeśli nie, projektanci infrastruktury czasem świadomie dodają „sztuczne” połączenia (np. krótkie łączniki, drogi techniczne), by doprowadzić stopnie do parzystości i uzyskać graf eulerowski. To dokładne odwrócenie królewieckiej historii: zamiast pytać, czy ktoś przypadkiem już stworzył sprzyjający układ, projektuje się taki układ z góry.

W praktyce miejskiej robi się coś bardzo podobnego przy planowaniu tras śmieciarek, odśnieżarek czy pojazdów sprzątających. Wariant idealny – raz każdą ulicą, bez nawrotów – odpowiada istnieniu cyklu Eulera w grafie ulic. Gdy warunek parzystości nie jest spełniony, trzeba liczyć się z dodatkowymi przejazdami. Każda nieparzystość ma swoją cenę w paliwie, czasie i logistyce.

Od Eulera do algorytmów: jak faktycznie znaleźć ścieżkę

Reguła Eulera mówi, kiedy ścieżka lub cykl istnieją. Nie mówi jednak wprost, jak taką trasę znaleźć. Współczesna teoria grafów dorzuca do tego algorytmy, które można zaimplementować w programach komputerowych.

Najbardziej znany dla ścieżek Eulera jest algorytm Hierholzera. Działa według prostej intuicji:

1. zaczynamy w dowolnym wierzchołku o nieparzystym stopniu (jeśli wszystkie są parzyste – w dowolnym),
2. idziemy „na ślepo”, każdą napotkaną jeszcze nieużytą krawędzią, aż wrócimy do punktu startu i utworzymy cykl,
3. jeśli są jeszcze krawędzie nieodwiedzone, wpinamy dodatkowe cykle w już istniejącą trasę, aż pokryjemy cały graf.

Ten schemat można zaimplementować w kilku linijkach kodu i zastosować w systemach wspierających np. planowanie tras pojazdów technicznych. Gdzieś pod spodem tych systemów działa ta sama logika, która kazała Eulerowi policzyć stopnie wierzchołków Królewca.

Mosty, których już nie ma, i teoria, która została

Punkty zwrotne Królewca: co zostało z oryginalnych mostów

Paradoksalnie, samo „laboratorium”, w którym narodziła się teoria grafów, praktycznie przestało istnieć. Wojna, przebudowy i zmiana granic sprawiły, że dzisiejszy Kaliningrad jest innym miastem niż pruski Królewiec. Część mostów zniknęła, inne zostały zastąpione nowymi konstrukcjami, przebieg rzeki uregulowano. Gdyby teraz narysować graf „mostów Kaliningradu”, miałby inną strukturę niż historyczny pierwowzór.

Nie przeszkadza to jednak w jednym: warunek Eulera da się zastosować tak samo jak kiedyś. Można wziąć aktualną mapę, zaznaczyć wyspy i brzegi jako wierzchołki, mosty jako krawędzie i policzyć stopnie. Współczesna konfiguracja jest już inna – w niektórych wersjach „nowego Królewca” graf da się nawet „naprawić” jednym dodatkowym łącznikiem, by osiągnąć eulerowsko idealny układ. Problem jest więc tym samym typem zagadki, choć na innym materiale.

To dobry przykład, jak matematyka odkleja się od konkretu: mosty mogą zostać wysadzone, przebudowane, zasypane, ale abstrakcyjna struktura – graf z czterema wierzchołkami i siedmioma krawędziami – pozostaje takim samym obiektem, jak w 1736 roku. Można go przerysować, skopiować, przeanalizować tysiąc razy, w różnych podręcznikach i programach komputerowych, bez potrzeby odwiedzania Pregoły.

Od łamigłówki do języka: jak mówimy o grafach

Euler nie znał dzisiejszego słowa „graf”, nie miał pojęcia o „stopniu wierzchołka” ani „ścieżce Eulera” w sensie formalnym. Te określenia narodziły się dużo później, gdy potrzeba języka dorównała bogactwu zastosowań. W XIX wieku pojawiły się badania nad drzewami (strukturami bez cykli), sieciami elektrycznymi, permutacjami; w XX wieku – eksplozja teorii grafów wraz z rozwojem informatyki.

Dzisiaj podstawowe słownictwo grafowe stało się czymś w rodzaju wspólnej „gwary” inżynierów, informatyków i matematyków. Kilka słów wystarcza, by zarysować cały problem:

• wierzchołki – obiekty, które chcemy ze sobą powiązać (skrzyżowania, serwery, osoby),
• krawędzie – połączenia między wierzchołkami (ulice, kable, relacje),
• stopień – ile krawędzi „wchodzi” do wierzchołka,
• ścieżka – ciąg krawędzi, którym da się przejść, bez przeskakiwania po mapie,
• cykl – ścieżka zamknięta, która wraca do punktu wyjścia.

Na takim szkielecie można zbudować bardzo różne teorie szczegółowe: o przepływach w sieciach, kolorowaniu wierzchołków, rozkładach na ścieżki czy cykle. Ale fundament został położony właśnie wtedy, gdy ktoś podzielił Królewiec na kilka „wysp” i narysował między nimi kreski.

Mosty a problem „przejścia wszystkich miejsc”: Euler kontra Hamilton

Wokół mostów Królewca łatwo pomylić dwa klasyczne typy zadań. W wersji eulerowskiej chcemy przejść każdą krawędź dokładnie raz. Można więc kilka razy wpaść na tę samą wyspę, byle tylko nie powtarzać mostu. W wersji hamiltonowskiej interesuje nas co innego: odwiedzić każdy wierzchołek dokładnie raz, przejścia mogą się powtarzać lub nie – to szczegół drugiego rzędu.

Oba podejścia opisują zupełnie różne światy. Ścieżki Eulera naturalnie pasują do zadań typu „obsłużyć wszystkie połączenia” (ulice, rurociągi, kable). Ścieżki Hamiltona są bliższe problemom „odwiedzić wszystkie punkty”: zaplanować trasę podróżnego, który chce zahaczyć o każde miasto; wyznaczyć kolejność odwiedzania magazynów przez samochód dostawczy; uporządkować zadania lub etapy w procesie.

Kontrast jest ostry również od strony obliczeniowej. Warunek na istnienie ścieżki Eulera jest prosty, sprawdzalny w czasie liniowym względem liczby krawędzi i wierzchołków. Dla ścieżki Hamiltona nie ma porównywalnie eleganckiego kryterium – ich wyszukiwanie to typowy przykład problemu trudnego obliczeniowo. Ten rozdźwięk często zaskakuje: dwie zagadki brzmią podobnie, ale za kulisami dzieli je przepaść w złożoności.

Euler w świecie danych: grafy w informatyce i analizie sieci

Współczesne systemy komputerowe są przesycone strukturami grafowymi, choć użytkownik zwykle ich nie widzi. Graf pojawia się zawsze, gdy program musi ogarnąć powiązania pomiędzy wieloma obiektami.

Kilka typowych scenariuszy z codziennej praktyki:

• systemy zależności w projektach IT – moduły programu jako wierzchołki, zależności „ten moduł wymaga tamtego” jako krawędzie; graf pomaga ocenić, co zepsuje się po zmianie danego fragmentu,
• analiza sieci społecznościowych – użytkownicy jako wierzchołki, relacje obserwowania lub znajomości jako krawędzie; algorytmy grafowe wyłuskują „węzły wpływu”, gęste grupy, mosty informacyjne między społecznościami,
• wyszukiwarki internetowe – strony jako wierzchołki, linki jako krawędzie; badanie struktury grafu sieci (PageRank i jego warianty) pozwala szacować znaczenie poszczególnych węzłów,
• planowanie przepływów – grafy przepływów (flow networks) opisują, jak może płynąć towar, prąd czy dane; na nich działają algorytmy maksymalnego przepływu, wyznaczania wąskich gardeł i planowania rozbudowy.

W tych zastosowaniach rzadko szuka się dosłownie ścieżek Eulera. Częściej pracuje się na idei spójności, minimalnych cięć, najkrótszych ścieżek czy centralności wierzchołków. Jednak punkt wyjścia jest ten sam: model „punkty i połączenia” okazał się zaskakująco pojemną metaforą dla świata danych.

Gdzie jeszcze wracają inwarianty: kolorowanie, parzystość, niezmienniki

Argument Eulera z parzystością stopni jest pierwszym spotkaniem z potężnym narzędziem: inwariantem. Zamiast śledzić każdy możliwy ruch, szuka się wielkości, która nie zmienia się w dozwolonych operacjach. Jeśli na końcu wymagałaby ona innej wartości niż na początku – wiadomo, że taki scenariusz jest niemożliwy.

Ten sposób myślenia powtarza się w wielu zagadkach grafowych. Klasyczny przykład to kolorowanie map i grafów: pytanie, ile kolorów potrzeba, aby pokolorować wierzchołki tak, by żadne dwa sąsiednie nie miały tego samego koloru. Słynne twierdzenie o czterech barwach mówi, że dla map planar­nych (takich, które można narysować na płaszczyźnie bez przecinających się krawędzi) wystarczą cztery kolory. Za kulisami dowodu stoją m.in. rozważania o niezmiennikach i redukcjach lokalnych konfiguracji.

W innych zadaniach inwariantem bywa liczba składowych spójności, suma stopni określonej klasy wierzchołków albo bardziej wyrafinowane wielkości algebraiczne (np. rangi pewnych macierzy związanych z grafem). Idąc tropem Eulera, wielu badaczy szukało właśnie takich „twardych” wielkości, których nie oszuka się żadnym sprytnym rysunkiem ani trikiem z przebiegiem ścieżki.

Eksperyment myślowy: jak samodzielnie „odkryć” regułę Eulera

Dla osób uczących się teorii grafów ciekawym ćwiczeniem jest przejście symbolicznie tej samej drogi, co Euler. Zamiast od razu pokazywać regułę o parzystości, można spróbować zachęcić do jej samodzielnego „odkrycia” na prostych przykładach.

W praktyce wygląda to tak: bierze się kilka małych sieci – np. kwadrat, kwadrat z przekątnymi, prosty układ ulic z trzema skrzyżowaniami – i zadaje pytanie: czy da się przejść każdą krawędź raz? Uczniowie lub studenci próbują rysować trasy, zaznaczać strzałkami przejścia, zliczać wejścia i wyjścia z wierzchołków. Po kilku nieudanych próbach często sami zauważają, że problemem są „dziwne” skrzyżowania, do których trzeba wchodzić i wychodzić nieparzystą liczbę razy.

Z takiego doświadczenia znacznie łatwiej zaakceptować formalne stwierdzenie: wierzchołek o nieparzystym stopniu nie może być „zwykłym” punktem pośrednim na ścieżce Eulera, bo każde wejście musi być sparowane z wyjściem. To, co w tekście Eulera jest krótkim rachunkiem, staje się czytelnym obrazem, kiedy spróbuje się faktycznie przejść po liniach.

Teoria grafów jako sposób patrzenia, nie tylko jako dział matematyki

Historia siedmiu mostów dobrze pokazuje, że istota teorii grafów nie tkwi wyłącznie w formalnych twierdzeniach. Chodzi o pewien nawyk: gdy widzimy skomplikowaną sytuację z wieloma powiązaniami, próbujemy najpierw wyłuskać z niej strukturalny szkielet. Zamiast grzęznąć w detalach – jedna rzeka, jeden most, konkretne miasto – pytamy, jakie są węzły, jakie połączenia, jakie liczby stoją za lokalnymi zjawiskami.

Ten sposób myślenia przekłada się na bardzo praktyczne decyzje. Projektant sieci drogowej może tak planować skrzyżowania, aby nadmiar węzłów o nieparzystym stopniu nie komplikował tras służb miejskich. Architekt systemu IT dba, by moduły nie tworzyły twardych cykli zależności, które utrudniają wdrażanie zmian. Analiza grafowa staje się narzędziem porządkowania, nie tylko rozwiązywania zagadek.

Dziedzictwo Eulera: od prostego rysunku do całej gałęzi nauki

Kiedy spojrzy się na współczesne podręczniki teorii grafów, łatwo zapomnieć, jak skromny był początek: mapa jednego miasta i pytanie o spacer. Dzisiaj obok ścieżek Eulera stoją rozbudowane teorie spektralne (badające własności macierzy sąsiedztwa), przypadkowe grafy modelujące zachowanie dużych sieci, zaawansowane algorytmy optymalizacji sieci przemysłowych. W tle, czasem tylko w przypisie, przewijają się jednak te same słowa: Euler, Królewiec, siedem mostów.

Ta historia bywa przypominana nie tylko z szacunku dla klasyka. Pokazuje, że potężne idee potrafią wyrosnąć z pozornie błahych zadań, jeśli potraktuje się je z powagą i odwagą abstrakcji. W tym sensie każdy nowy problem sieciowy – od projektowania tras po modelowanie internetu rzeczy – jest kolejną odsłoną tej samej opowieści, w której rzeka Pregoła zamieniła się w graf, a mosty stały się krawędziami w globalnym języku połączeń.

Najczęściej zadawane pytania (FAQ)

Na czym polega zagadka siedmiu mostów Królewca?

Zagadka siedmiu mostów Królewca polega na pytaniu, czy da się odbyć spacer po mieście tak, aby przejść przez każdy z siedmiu mostów dokładnie raz i wrócić do punktu wyjścia. Nie wolno żadnego mostu pominąć ani przejść dwa razy.

Problem wydaje się prosty i „spacerowy”, ale w praktyce okazał się na tyle trudny, że przez lata stanowił lokalną łamigłówkę dla mieszkańców Królewca, zanim zajął się nim Leonhard Euler.

Dlaczego zagadkę siedmiu mostów uważa się za początek teorii grafów?

Euler, rozwiązując zagadkę, jako pierwszy świadomie zrezygnował z dokładnego kształtu miasta, odległości i geometrii. Zastąpił realny plan Królewca abstrakcyjnym rysunkiem z punktami (obszary lądu) i liniami (mosty) – czyli grafem.

To przejście od konkretnej mapy do schematu połączeń uznaje się za narodziny teorii grafów: nowej dziedziny matematyki, która bada strukturę sieci, a nie ich dokładne położenie w przestrzeni.

Jak Euler zamienił plan Królewca na graf?

Euler przyporządkował każdemu obszarowi lądu jeden punkt (wierzchołek), a każdemu mostowi jedną linię (krawędź) łączącą odpowiednie punkty. W efekcie otrzymał graf o czterech wierzchołkach i siedmiu krawędziach.

Nie było ważne, jak krzywo biegnie rzeka ani jak daleko od siebie leżą mosty. Liczyło się wyłącznie to, które obszary są połączone i ile mostów między nimi istnieje. To właśnie jest istota modelowania problemu w postaci grafu.

Czy istnieje trasa przechodząca wszystkie mosty Królewca dokładnie raz?

Nie, taka trasa nie istnieje. Euler udowodnił, że przy danym rozmieszczeniu siedmiu mostów w Królewcu nie ma możliwości przejść przez każdy z nich dokładnie raz, niezależnie od tego, w którym miejscu zaczniemy spacer i w którym chcemy skończyć.

Wynika to z ogólnego warunku istnienia tzw. ścieżki Eulera w grafie: liczba wierzchołków o nieparzystym stopniu (z nieparzystą liczbą mostów wychodzących z danego obszaru) jest w Królewcu zbyt duża, aby taka trasa mogła istnieć.

Co to jest ścieżka Eulera w teorii grafów?

Ścieżka Eulera to taka trasa w grafie, która przechodzi po każdej krawędzi dokładnie raz. Jeśli ścieżka zaczyna się i kończy w tym samym wierzchołku, nazywamy ją cyklem Eulera.

W kontekście mostów Królewca ścieżka Eulera oznaczałaby właśnie poszukiwany „idealny spacer” po wszystkich mostach bez powtórek. Euler pokazał, kiedy taka ścieżka istnieje, a kiedy jest to niemożliwe – i Królewiec należy do tych drugich przypadków.

Jakie znaczenie ma zagadka siedmiu mostów dzisiaj?

Z pozoru lokalna łamigłówka stała się punktem wyjścia do badań nad grafami, które są dziś podstawowym narzędziem m.in. w informatyce, logistyce, teorii sieci i projektowaniu infrastruktury. Te same idee stoją za schematami metra, algorytmami wyszukiwania najkrótszej trasy czy optymalizacją sieci komputerowych.

Historia siedmiu mostów pokazuje też, jak z bardzo konkretnego, miejskiego problemu może narodzić się cała abstrakcyjna dziedzina matematyki, mająca ogromny wpływ na współczesną technologię.

Najważniejsze lekcje

• Z pozoru błaha, lokalna zagadka o przejściu przez wszystkie mosty Królewca dokładnie raz stała się punktem wyjścia do jednego z przełomowych odkryć w matematyce.
• Problem spacerowy mieszkańców dotyczył układu czterech obszarów lądu (dwa brzegi rzeki i dwie wyspy) połączonych siedmioma niesymetrycznie rozmieszczonymi mostami.
• Kluczowe w zagadce było wymaganie przejścia przez każdy most dokładnie jeden raz, co intuicyjnie okazywało się niewykonalne, ale brakowało formalnego uzasadnienia.
• Zainteresowanie Eulera pokazało, jak rzeczywisty, praktyczny problem miejski może stać się impulsem do narodzin całkowicie nowej dziedziny – teorii grafów.
• Przełomem było zrezygnowanie z geometrii miasta (kształtu rzeki, odległości, planu ulic) na rzecz czystej struktury połączeń między obszarami, przedstawionej jako punkty i linie.
• Euler wykazał, że dla tego typu problemów liczy się wyłącznie to, które obszary są ze sobą połączone i ile mostów je łączy – a nie ich układ przestrzenny.
• Historia siedmiu mostów pokazuje, jak przejście od konkretnej mapy do abstrakcyjnego schematu stało się fundamentem myślenia o sieciach, trasach i połączeniach w wielu współczesnych dziedzinach (transport, logistyka, sieci komputerowe).