Гамильтоновы циклы

Определение

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

Не найдено ни одного необходимого и достаточного условия существования гамильтонового цикла

Постановка задачи

Дан связный неориентированный граф.
Найти все гамильтоновы циклы
(если они есть).

“Простой” способ поиска:

Сгенерируем все перестановки вершин графа.
Дальше можно просто проверить

Рассмотрим пример:

Пусть у графа, скажем, 20 вершин. Сколько существует перестановок вершин?

20!=2432902008176640000

А если вершин 100?

Число перестановок будет равно:
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
≈ 9.3•10157

Это не все…

Чтобы проверить каждую из этих перестановок на “гамильтоновость” нужно

Конечно, “лобовое” решение крайне нерационально. Ведь при построении всех перестановок вершин

Структуры данных:

Будем использовать два массива целых:
Arr[N] – в этом массиве будет

Алгоритм

Будем предполагать, что поиск циклов мы ведем c вершины 1.
На очередном

Алгоритм

Центральной процедурой алгоритма является рекурсивная функция Step.
Эта функция принимает один целый

Алгоритм

1. Функция берет последнюю добавленную в массив Arr вершину, делает ее

Алгоритм

3. Если найдена вершина, связанная с текущей и еще непосещенная, то:
Эта

На каждом шаге к массиву Arr добавляется еще не посещенная вершина.

for (j=1; j <= gN; j++)
{
if (isBound(j,v))
{
…
if (Nnew[j]==0)

Рассмотрим граф:

Этот граф имеет два гамильтоновых цикла:
(1,2,3,4,5)
и
(1,5,4,2,1)

Посмотрим, как будет работать

На желтом поле показывается массив Arr, на зеленом – признаки прохождения

В прямых скобках показан параметр цикла в соответствующем вызове при поиске

Параметр вызова=N+1 и из последней вершины достижима первая – выполнено условие

Какую вершину будем добавлять?

Какую вершину будем добавлять?

Какую вершину будем добавлять?

Следующей будет добавлена 5-я вершина

Кратчайшие пути в графах

Постановка задачи

Дан ориентированный граф;
Каждой дуге приписана “длина” – вес дуги;
Веса дуг

Пример:

Каков будет кратчайший путь из 1 в 4?

Путь (1-3-2-4). Его

Контуры отрицательного веса

Если граф содержит контуры отрицательного веса, то поиск минимальной

Если мы ищем кратчайший путь из 1 в 5, то проходя

Соглашение:

Мы далее будем рассматривать только графы без контуров отрицательного веса.
(но дуги

Обозначим длину минимального пути между i-й и j-й вершинами через D(i,j).
К

Для некоторой вершины p обозначим массив кратчайших расстояний до всех остальных

Алгоритм определения пути

Ищем кратчайший путь из i-й вершины в j-ю.
Можно найти

На каждом шаге мы приближаемся к исходной вершине, и, в конце

Таким образом, если для каждой вершины известен массив кратчайших расстояний до

Общая схема такова:

Пусть зафиксирована i-я вершина, для которой мы ищем массив

Если для вершины k нашли вершину q, такую, что:
Di(k) > Di(q)+A[k,q],
то

Описанной схеме не хватает существенного момента – порядка выбора вершин k

Алгоритм Форда-Беллмана

Этот алгоритм применим к любому ориентированному графу без контуров отрицательной

Первоначально присваиваем всем элементам массива Di[k] значения A[i,k]; Элементу Di[i] присваиваем

Если веса всех дуг графа неотрицательны, то алгоритм Форда-Беллмана можно улучшить

Алгоритм Дейкстры

Исходные данные алгоритма:
Орграф с дугами неотрицательной длины;
Матрица весов дуг;
Фиксированная

Первоначально присваиваем всем элементам массива Di[k] значения A[i,k]; Элементу Di[i] присваиваем

Алгоритм Дейкстры имеет сложность
O(N2)

Имеется еще один частный вид графов, для

Является ли этот граф бесконтурным?

Нет. Контур выделен.

А этот?

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

У нашего графа есть “неправильная” дуга (2-1):

Если сделать вершину 1 вершиной

Cуществует эффективный алгоритм, позволяющий перенумеровать вершины бесконтурного графа и превратить его