Задача о Кенингсбергских мостах

А знаете ли вы, что мосты города Калининграда (Кенингсберга) стали «виновниками» создания Леонардом Эйлером теории графов (граф – это определенное количество вершин (узлов), соединённых рёбрами). Два острова на реке Прегель, на которой стоял Кенингсберг, были соединены семью мостами. К XVIII веку у жителей города сформировалась традиция: гуляя, пройти по всем мостам всего по одному разу. Сделать это никому не удавалось. В 1736 году эта задачка заинтересовала Леонарда Эйлера, выдающегося математика и члена Петербургской академии наук.

Он нашел правило, пользуясь которым можно было легко получить ответ на подобный вопрос. В случае с Кенингсбергом это оказалось невозможно. Правило заключалось в том, что части города на графе (рисунке) Эйлера обозначались вершинами, а мосты – ребрами, соединяющими эти вершины. Вершины, от которых отходит нечетное количество ребер, называются нечетными вершинами. Граф с более чем двумя нечетными вершинами оказалось невозможными нарисовать одним росчерком.

Казалось бы у такого странного открытия не может быть никакой практической пользы. Однако же польза нашлась, и еще какая. Теория графов, созданная Леонардом Эйлером, легла в основу проектирования транспортных и коммуникационных систем, она используется в информатике и программировании, в химии, физике и многих других областях.