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

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

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

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


Похожие записи:

  1. Самый длинный подвесной мост
  2. Такие разные мы
  3. Хлеб «по-сэндвичски»
  4. Памятник любви
  5. НВ2009: вопросы викторины 11-12


Рубрики: Науки

2 комментариев на “Задача о кенингсбергских мостах”

  1. Так есть все-таки решение задачи или так и не нашли?


©2009-2017 znaeteli.ru Использование материалов этого сайта разрешается только с согласия владельца.
Информер PR ТИЦ