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

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

Примеры.

Задачи с эйлеровыми графами часто встречаются в книгах по занимательной математике — например, можно ли нарисовать какую-нибудь диаграмму, не отрывая карандаша от бумаги и не проходя никакую линию дважды. Название "эйлеров" возникло в связи с тем, что Эйлер первым решил знаменитую задачу о Кенигсбергских мостах, в которой нужно было узнать, имеет ли граф, изображенный на рисунке, эйлерову цепь (не имеет!).

В 1736 г. великий Леонард Эйлер (1707-1783), свыше 30 лет работавший в Петербургской Академии наук (1727-1741, 1766-1783) нашел решение головоломки о кенигсбергских мостах. Дело в том, что в Кенигсберге было два острова, соединенных семью мостами с берегами реки Прегель и между собой (рис.15). Жители города мечтали найти замкнутый маршрут прогулки по всем мостам, но их попытки были безуспешны.

Рис.15

Для того, чтобы отвлечься от красот природы и зодчества, Эйлер рисует мультиграф (рис.16) и, наряду с поставленной задачей, ставит вопрос о возможности нарисовать эту фигуру, не отрывая пера от бумаги и не проводя линий дважды.

Рис.16