10. Эйлеровы графы. Условия существования цепи и цикла. Гамильтоновы цепи и циклы.

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

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

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

Эйлеров путь (эйлерова цепь) в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу.

Условия существования цепи и цикла.

Лемма 1. Если степень каждой вершины графа G не меньше двух, то граф G содержит цикл.

Теорема Эйлера 2. Связный граф G является эйлеровым тогда и только тогда, когда каждая вершина в G имеет четная степень.

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

Следствие 2.2. Связный граф является полуэйлеровым тогда и только тогда, когда в нем не более двух вершин имеют нечетные степени.

Теорема 3 (алгоритм Флёри). Пусть G – эйлеров граф, тогда следующая процедура всегда возможна и приводит к эйлеровой цепи графа G. Выходя из произвольной вершины, идем по ребрам графа произвольным образом, соблюдая лишь следующие правила:

1. стираем ребра по мере их прохождения. И стираем также изолированные вершины, которые при этом образуются;
2. на каждом этапе идем по мосту только тогда, когда нет других возможностей.

Любой простой полный граф с нечетным количеством вершин является эйлеровым.

Любой циклический граф является эйлеровым.

Гамильтоновы цепи и циклы.

Гамильтонов цикл - цикл, проходящий ровно один раз через каждую вершину графа G.

Тогда граф G называется гамильтоновым графом.

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

Теорема 4 (Дирарк, 1952).

Если в простом графе G с n>=3 вершинами степень любой вершины v scr37 , то граф G является гамильтоновым.

Любой простой полный граф является гамильтоновым.

Любой циклический граф является гамильтоновым.

Граф, являющийся колесом, является гамильтоновым.