Определение. Начало теории графов, как раздела математики, связывают с так называемой задачей о кенингсбергских мостах

Эйлеровы графы

Начало теории графов, как раздела математики, связывают с так называемой задачей о кенингсбергских мостах. Эта задача состоит в следующем. Семь мостов города Кенингсберга были расположены на реке Прегель.

В задаче спрашивается, можно ли выйдя из дома, вернутся обратно, пройдя в точности один раз по каждому мосту. Нарисуем граф, соответствующий этому рисунку.

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

Определение

Цепь, содержащую все ребра графа, называют Эйлеровой цепью.

Определение

Цикл в графе называют Эйлеровым, если он содержит все ребра графа.

Определение

Связный граф, в котором есть Эйлеров цикл, называется Эйлеровым графом.

Такой граф можно нарисовать, не отрывая руки от бумаги.