Siedem mostów w Królewcu to historycznie znany problem matematyczny. Leonhard Euler rozwiązał ten problem w 1735 roku, w pracy zwykle cytowanej pod łacińskim tytułem "Solutio problematis ad geometriam situs pertinentis". Jego rozumowanie zapoczątkowało powstanie teorii grafów, której metody mają dziś zastosowania w wielu dziedzinach (informatyka, logistyka, sieci). Wyniki Eulera przyczyniły się także do rozwoju topologii, zwłaszcza topologii kombinatorycznej.

Miasto Królewiec w Prusach (obecnie Kaliningrad, Rosja) leżało 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 sformułowano w następujący sposób: czy da się odbyć spacer przez miasto, przechodząc po każdym moście dokładnie raz (można zaczynać i kończyć w różnych miejscach)?

Formalizacja problemu

Eulera interesowało nie samo geometryczne położenie mostów, lecz wzajemne połączenia między obszarami lądowymi. Zamiast rysować mapę zrealizował abstrakcję: obszary lądowe traktuje się jako wierzchołki, a mosty jako krawędzie łączące te wierzchołki. Tak powstaje graf — struktura składająca się z wierzchołków i krawędzi, która oddaje istotę zadania bez zbędnych szczegółów geograficznych.

Warunek istnienia ścieżki przechodzącej każdą krawędź raz

Euler zauważył prosty, lecz fundamentalny warunek oparty na parzystości liczby mostów łączących każdy obszar (tzn. stopnia wierzchołka w grafie). Kluczowa obserwacja:

  • podczas przechodzenia przez miasto, jeśli zaczynasz lub kończysz spacer w danym obszarze, to liczba razy, kiedy wchodzisz na ten obszar i wychodzisz z niego, jest parzysta — każdorazowe wejście (poza ewentualnym startem) wymaga wyjścia;
  • to oznacza, że dla wszystkich wierzchołków poza co najwyżej dwoma (start i meta) liczba incydentnych krawędzi musi być parzysta.

Wniosek (warunek konieczny i wystarczający): W spójnym grafie istnieje ścieżka przechodząca każdą krawędź dokładnie raz (tzw. ścieżka Eulera) wtedy i tylko wtedy, gdy liczba wierzchołków o nieparzystym stopniu wynosi dokładnie 0 lub 2. Gdy każdy wierzchołek ma parzysty stopień, istnieje cykl Eulera (ścieżka zaczyna i kończy się w tym samym wierzchołku). Gdy dokładnie dwa wierzchołki mają nieparzysty stopień, istnieje ścieżka Eulera zaczynająca się w jednym z nich i kończąca w drugim.

Rozwiązanie problemu królewieckiego

Po zastosowaniu tej analizy do ówczesnego rozkładu mostów w Królewcu, Euler wykazał, że cztery obszary lądowe miały nieparzystą liczbę mostów. Ponieważ liczba wierzchołków o nieparzystym stopniu wynosiła więcej niż 2, warunek istnienia ścieżki spełniającej zadanie nie był spełniony. Stąd problem „Siedmiu mostów w Królewcu” nie ma rozwiązania — nie można przejść przez miasto przechodząc każdy most raz i tylko raz.

Krótka idea dowodu

Dowód Eulera opiera się na prostym rachunku parzystości: każdorazowe przejście przez most łączy dwa wierzchołki i zmienia liczbę użyć krawędzi przy każdym z nich o jeden. Po przejściu wszystkich krawędzi tylko w co najwyżej dwóch wierzchołkach suma użyć krawędzi może być nieparzysta (to będą końce trasy), wszystkie pozostałe muszą mieć parzystą liczbę użyć. Stąd wynik o maksymalnie dwóch wierzchołkach nieparzystych.

Znaczenie historyczne i dzisiejsze zastosowania

Rozwiązanie Eulera jest uważane za początek teorii grafów i jedną z pierwszych prac w topologii kombinatorycznej. Idea sprowadzenia problemu do grafu i badania parzystości stopni wierzchołków rozwinęła się w potężny aparat matematyczny wykorzystywany obecnie w:

  • projektowaniu tras (np. wywozu śmieci, planowaniu tras dostaw),
  • analizie sieci komputerowych i telekomunikacyjnych,
  • badaniu struktur molekularnych i biologicznych,
  • algorytmice i teorii złożoności — wiele problemów sieciowych formułuje się jako zagadnienia na grafach.

Problem siedmiu mostów w Królewcu pozostaje popularną ilustracją, jak prosta obserwacja może zainicjować nową gałąź matematyki i zmienić sposób myślenia o problemach praktycznych i teoretycznych.