Главная | Обратная связь

Критерий эйлеровости графа

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

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

Формула Эйлера: Для всякого плоского представления связного плоского графа без перегородок число вершин (V), число ребер (E) и число граней[2] с учетом бесконечной (R) связаны соотношением V – E + R = 2.

Связный орграф содержит эйлеров контур тогда и только тогда, когда для каждой вершины число входящих дуг равно числу выходящих.

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

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

Теорема Дирака: если в простом графе с n ³ 3 вершинами степень каждой вершины не меньше n/2, то такой граф обязательно будет гамильтоновым
(см. рис. 10).

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

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

Рис.10. Гамильтонов Рис.11. Полугамильтонов Рис.12. Не гамильтонов граф граф граф

Рассмотрим несколько достаточных условий существования гамильтоновых циклов в графе.

1) всякий полный граф является гамильтоновым. Действительно, он содержит такой простой цикл, которому принадлежат все вершины данного графа.

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

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

Не является гамильтоновым и граф, представляющий собой простой цикл с "перекладиной", на которой расположены одна или несколько вершин

Примеры выполнения заданий