Problem mostów królewieckich

Problem mostów królewieckich

Co to takiego?

• Problem dotyczył 7 mostów na rzece Pergoła, która przepływa przez Królewiec ( dzisiejszy Kaliningrad)

• Mosty powstały jako połączenie między dwoma wyspami i miastem (ich układ można zobaczyć na obrazku obok)

• Problem brzmiał następująco: czy można przejść wszystkie mosty używając każdego mostu tylko raz?

Rozwiązanie problemu

• Nad rozwiązaniem problemu mostów królewieckich głowił się Leonhard Euler (widoczny na obrazie)

• w 1736r. odkrył on rozwiązanie

• jego rozwiązanie dało początek teorii grafów

• Na obrazku przedstawiony jest graf ilustrujący rozwiązanie opracowane przez L. Eulera
• Litery oznaczają części miasta, do których prowadzą mosty i są wierzchołkami grafu, a cyfry oznaczają mostyi są krawędziami grafu.
• Taki graf jest przykładem grafu spójnego, czyli takiego w którym między dwoma dowolnymi punktami jest droga wiodąca po jego krawędziach.

• Euler dowiódł, że w takim grafie przejście po wszystkich jego krawędziach zaczynając i kończąc w tym samym punkcie, a także korzystając z każdej krawędzi tylko raz jest możliwe jedynie wtedy, gdy każdy stopień wierzchołka (czyli liczby krawędzi wychodzących z tego wierzchołka) tego grafu jest parzysty. Taki graf nazywamy grafem Eulerowskim.

• Graf przedstawiający przejście po mostach nie spełnia wyżej opisywanego warunku, więc nie jest grafem Eulerowskim. W związku z tym spacer po wszystkich mostach królewieckich przechodząc każdy tylko raz nie jest możliwy

Dziękuję za uwagę

Opracowanie: Joanna Sajkowska kl.2B