Mosty królewieckie — narodziny teorii grafów

Co się właśnie stało?

W XVIII-wiecznym Królewcu (dziś Kaliningrad) rzeka Pregoła dzieliła miasto na 4 części — dwa brzegi (A, B) i dwie wyspy (C, D — Kneiphof i sąsiednia wyspa) — połączone 7 mostami. Mieszkańcy zastanawiali się, czy da się przejść przez każdy most dokładnie raz. Leonhard Euler w 1736 r. udowodnił, że to niemożliwe — i przy okazji założył nową dziedzinę matematyki: teorię grafów.

Model: graf zamiast mapy

Euler zredukował mapę do grafu: lądy stają się wierzchołkami, a mosty — krawędziami. Liczbę mostów przy danym lądzie nazywamy stopniem wierzchołka:

Każdy most ma dwa końce, więc suma wszystkich stopni to zawsze dwukrotność liczby mostów — to lemat o uściskach dłoni (handshaking lemma):

Twierdzenie Eulera

Trasę przechodzącą przez każdą krawędź dokładnie raz (drogę lub cykl Eulera) da się poprowadzić wtedy i tylko wtedy, gdy liczba wierzchołków o nieparzystym stopniu wynosi:

0 nieparzystych → istnieje cykl Eulera (start = koniec, w dowolnym wierzchołku). 2 nieparzyste → istnieje droga Eulera (musisz zacząć i skończyć dokładnie w tych dwóch wierzchołkach). Każda inna liczba nieparzystych — niemożliwe, bez wyjątków.

Dlaczego Królewiec się nie udał

W oryginalnym układzie wszystkie 4 lądy mają nieparzysty stopień (3, 3, 5, 3) — cztery nieparzyste, nie 0 ani 2. Dlatego żaden spacer po wszystkich 7 mostach bez powtórzeń nie istnieje — i to nie przez brak pomysłowości mieszkańców, tylko przez samą strukturę grafu. Wystarczy dobudować jeden most (np. A–B), by dwa z lądów zmieniły parzystość na parzystą i zostały dokładnie 2 nieparzyste — wtedy droga Eulera od razu się pojawia.

Co to znaczy w praktyce?

Ten sam warunek parzystości rządzi dziś trasami listonoszy i śmieciarek (problem chińskiego listonosza), projektowaniem obwodów drukowanych, sekwencjonowaniem DNA (składanie fragmentów w grafie de Bruijna) i planowaniem tras w sieciach — wszędzie tam, gdzie trzeba przejść każde połączenie dokładnie raz.

Po co Ci to na maturze:

Formalnie teoria grafów nie jest osobnym działem matury, ale rozumowanie Eulera to wzorcowy przykład dowodu przez niezmiennik — policz coś, co się nie zmienia (tu: parzystość stopni), i pokaż, że warunek zadania mu przeczy. Ten sam chwyt („uzasadnij, że nie da się…") pojawia się w zadaniach kombinatorycznych z rozszerzenia i w zadaniach olimpijskich.

Zapamiętaj: droga lub cykl Eulera istnieje wtedy i tylko wtedy, gdy liczba wierzchołków o nieparzystym stopniu wynosi 0 (cykl) lub 2 (droga) — każda inna liczba oznacza, że to niemożliwe. To pierwszy wynik teorii grafów w historii matematyki.