В чем заключается задача о кенигсбергских мостах и как она связана с теорией графов?

Задача о кенигсбергских мостах — старинная математическая задача, в которой требовалось придумать прогулку по городу Кенигсберг (ныне Калининград), чтобы пересекать каждый из семи мостов один и только один раз. en.wikipedia.org nsportal.ru

Решение задачи было найдено Леонардом Эйлером в 1736 году. en.wikipedia.org nsportal.ru Учёный доказал, что проблема не имеет решения. en.wikipedia.org Он указал, что выбор маршрута внутри каждого массива суши не имеет значения, а единственной важной особенностью маршрута является последовательность пересечённых мостов. en.wikipedia.org

Связь с теорией графов заключается в том, что Эйлер переформулировал проблему в абстрактных терминах, заложив основы теории графов. en.wikipedia.org В современных терминах каждый массив суши заменяется абстрактной «вершиной» или узлом, а каждый мост — абстрактным соединением, «ребром». en.wikipedia.org

Эйлер также вывел критерий существования обхода у графа: граф должен быть связным и каждая его вершина должна быть инцидентна чётному числу рёбер. zaytsev.net Поскольку в графе кенигсбергских мостов все вершины были нечётными, то невозможно пройти по всем мостам, не проходя ни по одному из них дважды. www.techinsider.ru

Пользователь

Время добавления