6. Обходы графов: гамильтоновы цепи и циклы, достаточные условия их существования.

Графом G называется пара (V, E), где – непустое множество вершин графа, а– множество ребер графа, причем каждое ребро – это неупорядоченная пара различных вершин.

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

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

Утверждение. Достаточное условие существования гамильтонова цикла - если в связном n-вершинном графе, где n ≥ 3, степень каждой вершины deg(v) ≥ n/2, то в этом графе имеется гамильтонов цикл.

Утверждение. Если в связном n-вершинном графе, где n ≥ 3, степень каждой вершины deg(v) ≥ n/2, то в этом графе имеется гамильтонов цикл.

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