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

Задачи, связанные с эйлеровыми, а, особенно, с гамильтоновыми графами часто встречаются и в головоломках, в игровых задачах, на практике, в частности, когда для выполнения некоторого комплекса операций необходимо провести их в таком порядке, чтобы эффективность их выполнения была максимальной. К этому же классу задач относится и известная задач о кенигсберских мостах, которая на языке теории графов формулируется так: есть ли в мультиграфе Gцикл, соединяющий все рёбра мультиграфа?В 1736 году Эйлер доказал, что эта задача неразрешима, но при этом сформулировал важное условие, при котором связный граф содержит эйлеров цикл.

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

Существует также понятие эйлеровой цепи, то есть цепи, содержащей все рёбра графа.

Эйлер в 1736 году сформулировал теорему:

Теорема Эйлера: Связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин чётны. (Докозательство тривиально)

Естествено, возникает вопрос об отыскании в любом графе эйлерова цикла, то есть о такой нумерации рёбер G, чтобы номер указывал, каким по счёту это ребро входит в эйлеров цикл.

Один из алгоритмов нумерации называется алгоритмом Флёри:

1. Начиная с произвольной вершины v_i присваивается произвольному ребру (v_i v_i+1) номер 1, затем это ребро вычёркивается и переходят в вершину v_i+1.

На рис. 1.28 показана нумерация ребер, выполненная по алгоритму Флёри.

Следует отметить, что эйлеровы графы на практике достаточно редки.