5.3. Связь между эйлеровыми и гамильтоновыми циклами

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

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

Например, для графа, показанного на рис. граф изображен на рис.

Легко можно показать [15], что верны два следующие утверждения о взаимоотношении между эйлеровыми и гамильтоновыми циклами.

(1) Если имеет эйлеров цикл, то имеет как эйлеров, так и гамильтонов циклы.

(2) Если имеет гамильтонов цикл, то также имеет гамильтонов цикл.

Обращение этих утверждений, как нетрудно продемонстрировать, неверно. Для графа, изображенного на рис. степени всех его вершин четны и поэтому существует эйлеров цикл. Таким образом, граф изображенный на рис. 9.14(6), также имеет эйлеров цикл (поскольку степени всех его вершин опять четны) и, кроме того, имеет гамильтонов цикл, задаваемый последовательностью вершин Если теперь из графа удалить ребро то новый граф не имеет эйлерова цикла, но все еще имеет гамильтонов цикл 1, 2, 6, 5, 4, 3, 1. Реберный граф графа является тогда графом из рис. с удаленной вершиной (и без ребер, инцидентных вершине Этот граф все еще имеет гамильтонов цикл

Рис. 9.14. (см. скан) (а) - граф G. (б) - реберный граф

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

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

6. Задачи

(см. скан)

(см. скан)

7. Список литературы

(см. скан)