Problem siedmiu mostów w Królewcu.
Centrum Królewca leży na wyspie.
Po ominięciu wyspy rzeka rozdziela się na dwa koryta.
Powstałe cztery lądu obszary łączy siedem mostów.
Szkic mapy centrum Królewca z rozmieszczeniem mostów znajduje się na sąsiednim rysunku.
Pytanie które nurtowało mieszkańców Królewca w pierwszej połowie XVIII wieku brzmiało:czy można odbyć taką wycieczkę, aby przejść przez każdy most dokładnie jeden raz?
Problemem tym zajął się około roku 1735 Leonard Euler, mieszkający właśnie w Królewcu.
Rozwiązanie tego problemu było dosyć brzemienne dla matematyki w skutki -
przyczyniło do powstania kilku nowych działów matematyki: geometrii kombinatorycznej, topologii i teorii grafów.
Krok 1: ręczne próby rozwiązania
Oto dwie nie udane próby rozwiązania tego zadania:
Krok 2: formalizacja problemu
| L. Euler zauważył, że problem ten, podobnie jak wiele mu podobnych, można przedstawić zastępując
obszary przez punkty (które nazywamy wierzchołkami) a mosty przez łuki (nazywane krawędziami).
Strukturę składającą się z wierzchołków i łączących je łuków nazywa się grafem. To przetłumaczenie oryginalnego zadania na język grafów umożliwia bardziej wyraźne ujrzenie analizowanego problemu - widzimy tylko strukturę kombinatoryczną rozważanego problemu. Zabieg ten jest często stosowany w nauce:jeśli nie wiesz jak rozwiązać pewne zagadnienie, to spróbuj je przetłumaczyć na inny język. Jeśli będziesz miał szczęście, to jego rozwiązanie w nowym języku może być prostsze od oryginalnego. |
Krok 3: analiza
| Oto problem mostów Królewca po przetłumaczeniu:czy można narysować powyższy rysunek bez odrywania ołówka od kartki papieru tak, aby każda linia narywana była dokładnie jeden raz? Zauważmy teraz, że do każdego z czterech wierzchołków tego grafu dochodzi nieparzysta liczba krawędzi. Rozważmy teraz dowolną trasę w tym grafie, w której przechodzimy przez każdą krawędź najwyżej jeden raz. Za każdym razem kiedy przechodzimy przez pewien wierzchołek, to wykorzystujemy dwa łuki. Z obserwacji tej wynika, że poza punktami początkowymi i końcowymi potencjalnej, do każdego wierzchołka dochodzić musi parzysta ilość łuków. Problem mostów w Królewcu ma więc negatywne rozwiązanie, gdyż ilość wierzchołków o nieparzystej liczbie krawędzi jest większa od dwóch. |
Prawdziwy jest również wynik odwrotny - jeśli w skończonym grafie istnieją co najwyżej dwa wierzchołki z nieparzystą liczbą krawędzi, to istnieje droga, która przechodzi przez każdą krawędź dokładnie jeden raz.