История теории графов

 

 Первая работа по теории графов принадлежит Леонарду Эйлеру. Она появилась в 1736 году в публикациях Петербургской Академии Наук и начиналась с рассмотрения задачи о кенигсбергских мостах.

 Через город протекает река Преголя. Она делится на два рукава и огибает остров. В 17 веке в городе было семь мостов, расположенных так, как показано на рисунке.

 Рассказывают, что однажды житель города спросил у своего знакомого, сможет ли он пройти по всем мостам так, чтобы на каждом из них побывать только один раз и вернуться к тому месту, откуда началась прогулка. Многие горожане заинтересовались этой задачей, однако придумать решение никто не смог. Этот вопрос привлек внимание ученых из многих стран. Разрешить проблему удалось известному математику Леонарду Эйлеру. Леонард Эйлер, уроженец города Базеля родился 15 апреля, 1707 года. Научные заслуги Эйлера огромны. Он оказал влияние на развитие почти всех разделов математики и механики как в области фундаментальных исследований, так и в их приложениях. Леонард Эйлер не только решил эту конкретную задачу, но и придумал общий метод решения этих задач. Эйлер поступил следующим образом: он «сжал» сушу в точки, а мосты «вытянул» в линии. В результате получилась фигура, изображенная на рисунке.