Zagadnienie mostów królewieckich
Z Wikipedii
Zagadnienie mostów królewieckich - problem nad którym rzekomo głowili się mieszkańcy Królewca (wówczas Königsberg), a który rozwiązał w XVIII wieku Leonhard Euler.
Przez Królewiec przepływała rzeka, w której rozwidleniach znajdowały się dwie wyspy. Ponad rzeką przerzucono siedem mostów, z których jeden łączył obie wyspy, a pozostałe mosty łączyły wyspy z brzegami rzeki. Problem, którym zainteresował się Euler, był następujący: czy można przejść kolejno przez wszystkie mosty tak, żeby każdy przekroczyć tylko raz i wrócić do miejsca, z którego się wyruszyło.
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 w każdym wierzchołku tego grafu spotyka się parzysta liczba krawędzi.
Opis zagadanienia opublikowany przez Eulera w 1736 roku było pierwszą pracą na temat teorii grafów.
[edytuj] Przekształcenie schematu mostów w graf
→ 
→ 
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.
