Цепи и циклы в графах

Двигаясь по ребрам графа G(X,U), можно переходить из вершины в вершину. Любая последовательность ребер, получаемая при этом, называется маршрутом, то есть последовательность (x₀,x₁)(x₁,x₂)…(x_n,x_n-1), в которой любые два соседних ребра смежные - маршрут.

Цепь– маршрут, в котором все ребра различны.

Простая цепь – цепь, в которой все вершины различны.

Цикл - цепь, в которой совпадают начальная и конечная вершины.

Дерево - связный граф без циклов. В дереве любые две вершины связаны единственной цепью. Дерево, построенное на n вершинах, имеет n-1 ребер.

Лес- совокупность деревьев.

Пример:

В графах выделяют два замечательных цикла: эйлеров и гамильтонов.

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

Задача возникла из следующего примера. В XIII веке жители Кенигсберга, прогуливаясь по мостам реки, Прегель пытались решить задачу: можно ли обойти все мосты, проходя по каждому из них только один раз (рис. 1.8)

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

Эйлеру удалось доказать, что искомого маршрута обхода города не существует.

Ответ может быть получен на основе следующей теоремы.

Теорема. Граф является эйлеровым тогда и только тогда, когда степени всех его вершин четные.

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

Пример графа, имеющего эйлеров, цикл показан на рис. 1.9.

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

В полном графе с числом вершин n»2 всегда существует гамильтонов цикл. Пример такого цикла приведен на рис. 1.10 - (x1,x4) (x4,x2) (x2,x5) (x5,x3) (x3,x1).

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

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