Эйлеровы циклы. Гамильтонов контур

Эйлеровы циклы и гамильтоновы циклы (контуры) часто встречаются в практических задачах и поэтому представляют особый интерес.

Возник вопрос: можно ли, выйдя из дома, вернуться обратно, пройдя по каждому мосту ровно один раз. Можно построить граф задачи, в которой каждой части города соответствует вершина, а каждому мосту – ребро, инцидентное вершинам, относящимся к соединяемым им частям (рис. 4.42). Обходу мостов соответствует маршрут графа, который по условию должен быть простым циклом. Эйлер дал отрицательный ответ на поставленный вопрос, так как соответствующий граф не содержал эйлерова цикла.

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

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

Граф, в котором существует эйлеров цикл, называетсяэйлеровым графом.

Путь, проходящий через все вершины графа (в точности по одному разу через каждую), называетсягамильтоновым путем. Если начальная вершина и конечная вершина этого пути совпадают, то такой путь называетсягамильтоновым контуром.

Утверждения.

1. Связный неориентированный граф содержит эйлеров цикл (эйлерову цепь) тогда и только тогда, когда число вершин нечетной степени равно 0 (0 или 2).

2. Длясвязного графа G следующие утверждения эквивалентны:

а) G - эйлеров граф;

б) каждая вершина графа G имеет четную степень;

в) множество ребер графа G можно разбить на простые циклы.

3. Пусть G - данный неорграф, a L(G) - его реберный граф, тогда:

а) если G имеет эйлеров цикл, то L(G) имеет как эйлеров так и гамильтонов циклы;

б) если G имеет гамильтонов цикл, то L(G) также имеет гамильтонов цикл.

4. Сильно связный полный граф гамильтонов.

5. Пусть G - сильно связный граф на n вершинах без параллельных дуг и петель. Если для любой вершины х справедливо неравенство d^-(х)+d⁺(х)³n, то граф G имеет гамильтонов контур.

6. Если орграф G полный, то он имеет ориентированный гамильтонов путь.