Euler wykazał, że jest to niemożliwe, a decyduje o tym nieparzysta liczba wylotów mostów zarówno na każdą z wysp, jak i na oba brzegi rzeki. Rozważył przy tym także ogólniejszy problem, starając się ustalić warunki, które muszą być spełnione, żeby dany graf spójny można było opisać linią ciągłą w taki sposób, by każda krawędź tego grafu była obwiedziona tylko raz (patrz graf eulerowski). Euler pokazał, że jest to możliwe wtedy i tylko wtedy, gdy liczba wierzchołków tego grafu, w których spotyka się nieparzysta liczba krawędzi, wynosi 0 lub 2. Doszedł także do wniosku, że aby przejść wszystkie krawędzie grafu i wrócić do punktu wyjścia, nie może on zawierać węzłów, w których spotyka się nieparzysta liczba krawędzi.
Przekształcenie schematu mostów w graf 150px → 150px → 150px Lewy wierzchołek reprezentuje małą wyspę ze środka obrazka, prawy to wyspa z prawej (na rysunku widać tylko jej fragment), a górny i dolny wierzchołek, to brzegi rzeki.
Przypisy
Bibliografia
Linki zewnętrzne
Dan Van der Vieren, How the Königsberg bridge problem changed mathematics, kanał TED-Ed na YouTube, 1 września 2016 [dostęp 2024-08-22].
Kategoria:Teoria grafów Kategoria:Problemy matematyczne Kategoria:Królewiec