Гамильтоновы и эйлеровы графы

Предположим, что имеем объект, функционирование которого описывается орграфом.

Предположим также, что неисправности объекта можно разделить на два типа:

- неисправность типа 1: приводит к потере вершины,

- неисправность типа 2: приводит к потере дуги.

При контроле работоспособности объекта с неисправностями типа 1 необходимо обойти все вершины.

При контроле работоспособности объекта с неисправностями типа 2 необходимо обойти все дуги (при этом будут пройдены и все вершины).

Очевидно, что время на проверку объекта в обоих случаях минимально, если вершины или дуги будут пройдены по одному разу.

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

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

Для неорграфа существует признак наличия гамильтонова цикла:

Если сумма степеней двух любых вершин графа больше или равна n, т.е. deg a + deg b ³ n, то в графе можно построить гамильтонов цикл.

Следствие: Если у любой вершины графа deg v_i ³ n /2, то в таком графе можно построить гамильтонов цикл.

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

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

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

Граф, который удовлетворяет условиям Эйлера, называется эйлеровым графом. Пример такого графа показан на рис. 2.32. У этого графа каждая вершина имеет четную степень, равную 2.

Цикл в этом графе a–e ₁ –b–e ₃ –c–e ₂ –a называется эйлеровым, так как он проходит через все ребра по одному разу.

Рисунок 2.32