Начало теории графов было положено Леонардом Эйлером в его знаменитом решении задачи о Кенигсбергских мостах в 1736 году. Бывший Кенигсберг (Калининград) расположен на реке Прегель. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Жители предлагали приезжим пройти по всем мостам и вернуться в начальный пункт, причём на каждом мосту следовало побывать только один раз.

И решена она была, как вы уже догадались, немецким и русским математиком Леонардом Эйлером.
Эйлер нашёл правило, пользуясь которым, легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них. Ответ был…. 
Для наглядности заменим рисунок расположения речных рукавов упрощенной схемой (см ... Читать дальше »