Алгоритм нахождения эйлерова цикла. Оценка вычислительной сложности алгоритма.

Исходные данные: связный граф G = < V, E > без вершин нечетной степени, представленный списками ЗАПИСЬ [v], v Î V. Результаты: Эйлеров цикл, представленный последовательностью вершин в стеке СЕ. Принцип действия этого алгоритма можно объяснить следующим образом: пусть v₀ - вершина, выбранная в третьей строке. Цикл начинает строить путь с началом в v₀, причем вершины этого пути помещаются в CTEK, а ребра удаляются из графа. Эти действия продолжаются вплоть до того момента, когда путь нельзя удлинить, включив в него новую вершину, т.е. когда ЗАПИСЬ [v] = Æ. Отметим, что тогда должно быть v = v₀, так как в любом другом случае это означало бы, что степень вершины v нечетная. Таким образом, из нашего графа был удален цикл, а вершины этого цикла находятся в стеке CTEK. Отметим, что в графе, модифицированным таким способом, степень произвольной вершины останется четной. Вершина v =v₀ переносится теперь из стека CTEK в стек CE, а очередной вершиной v становится верхний элемент стека CTEK. Процесс повторяется, начиная с этой вершины (если ЗАПИСЬ [v]<>Æ), в результате чего вследствие четности степени всех вершин находится и помещается в стек CTEK некоторый цикл, проходящий через вершину v. Это продолжается до того момента, пока CTEK не станет пустым. Очевидно, что вершины, помещаемые в стек CE, образуют некоторый путь, причем вершина v переносится в стек CE только тогда, когда ЗАПИСЬ [v] = Æ, т.е. когда все ребра, инцидентные с этой вершиной, представлены (парами соседних вершин) в одном из стеков. Отсюда легко следует, что по окончании алгоритма стек CE содержит эйлеров цикл. Оценим теперь вычислительную сложность этого алгоритма. Для этого отметим, что каждая итерация главного цикла либо помещает вершину в стек CTEK и удаляет ребро из графа, либо переносит вершину из стека CTEK в стек CE. Таким образом, число итераций этого цикла - О(m). В свою очередь число шагов в каждой итерации ограничено константой. Здесь предполагаем, что каждый из списков инцидентности ЗАПИСЬ [v], v Î V, реализован таким образом, что каждая вершина в этом списке содержит указатели на предыдущую и последующую вершины, и вершина u в списке ЗАПИСЬ [v] содержит указатель на вершину v в списке ЗАПИСЬ [u]. Это дает возможность устранить ребро {u, v} за время, ограниченное константой. Из приведенных выше рассуждений можно сделать вывод, что общая сложность алгоритма есть О(m). Очевидно, что этот алгоритм оптимальный, так как уже одно выписывание эйлерова цикла требует W (m) шагов.

 

39. Гамильтонов путь в графе, гамильтонов цикл. NP- полные задачи. Алгоритм с возвратом для поиска всех гамильтоновых циклов в графе. Его вычислительная сложность.

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

Алгоритм. Данные: Граф G = < V, E>, представленный списками инцидентности ЗАПИСЬ[ v ], v Î V. Результаты: Список всех гамильтоновых циклов графа G. Работу этого алгоритма, так же как и произвольного алгоритма с возвратом, можно проиллюстрировать процессом поиска в некотором дереве. Каждая вершина дерева естественным образом соответствует некоторой последовательности (x ₁,..., x_kñ, причем вершины, соответствующие последовательностям вида (x ₁,..., x_k, yñ являются сыновьями этой вершины (корень соответствует пустой последовательности e). Рассмотрим полное дерево D, состоящее из всех возможных последовательностей вида (x ₁,..., x_kñ, где 0 < k < n и x_i Î A_i для 1 < i < k, и временно допустим, что каждый элемент y Î A_k является допустимым для (x ₁,..., x_k -1), если k < n, и ни один элемент не является допустимым для (x ₁,..., x_k -1), если k > n; другими словами, P (x ₁,..., x_k-1, x_k) = истина, если k < n, и P (x ₁,..., x_k-1, x_k) = ложь, если k > n (x_i Î A_i для 1 < i < k). Тогда нетрудно отметить, что вызов AP (1) вызывает поиск в глубину во всем дереве D (начиная от корня e). Для случая менее тривиальной функции P, определяющей допустимость вершин, процесс поиска опускает рассмотрение вершин поддерева с корнем в каждой встреченной недопустимой вершине, т.е. вершине, соответствующей последовательности (x ₁,..., x_kñ, для которой P (x ₁,..., x_k) = ложь). В этом, собственно говоря, заключается эффективность алгоритма с возвратом в отношении полного перебора всех возможностей. Следует отметить, что для большинства приложений число шагов алгоритма с возвратом хотя и будет меньше, чем в случае полного перебора, однако же в наихудшем случае растет по экспоненте с возрастанием размерности задачи. Это справедливо и для случая, если мы ищем только одно, а не все решения (тогда мы просто прерываем выполнение алгоритма после получения первого решения; отметим, что когда задача не имеет решения, эта модификация не влияет на ход выполнения алгоритма).