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

Материал из WikiGrapp
Перейти к:навигация, поиск

Задача о кенигсбергских мостах (K\ddot{o}nigsberg's\,\,bridges\,\,problem) — задача обхода всех семи мостов города Кенигсберга (ныне Калининграда) таким образом, что по каждому мосту проходят в точности один раз. Задача была поставлена и решена Эйлером в 1736 г. в виде общей проблемы теории графов: при каких условиях связный граф содержит цикл, проходящий через каждое его ребро?

Литература

  • Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.
  • Харари Ф. Теория графов. — М.: Мир, 1973.