Известен ли эффективный алгоритм поиска всех элементарных циклов в неориентированном графе?

Question

[inek]

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

Answer 1

[Wataru]

Что вы подразумеваете под словом "эффективный"?

Проблема в том, что циклов в графе из n вершин может быть O(n!) (n-факториал): представьте клику - граф, где есть ребра между всеми парами вершин. Любое подмножество вершин, да еще и в любом порядке, задает элементарный цикл.

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

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

Comments

[inek]

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

[Wataru]

inek, Все-равно, таких циклов O(n^n), где n - количество вершин. Алгоритм, который ищет все циклы в графе за такую сложность существует - полный перебор. Я вам его расписал уже выше.

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

[Руслан .]

Wataru, Объясните плиз откуда появляется n^n?

Я так рассуждаю:
Есть n вершин и каждая из них связана с остальными - полносвязный граф.
Чтобы образовался цикл нужно минимум 3 вершины.
Значит для n вершин есть вот такое количество неповторяющихся циклов:
C(n,3)+C(n,4)+..+C(n,n), где C(n, k) - это количество сочетаний из n по k.
В данном случае сочетания по вершинам.

Т.е. для n = 5 например получаем
С(5,3) = 10
С(5,4) = 5
C(5,5) = 1
Общее = 10+5+1 = 16 циклов, при этом 5^5= 3125, т.е. намного больше.

Что я не учитываю?

[Wataru]

Руслан ., В графе может быть n! циклов длины n. Порядок же важен. Плюс еще циклы длин n-1,n-2...3.

По формуле Стирлинга n! ~ sqrt(2 pi n)(n/e)^n

Ну не прям n^n, конечно, а на самом деле O((n/e)^n), но это не сильно лучше.

[Wataru]

Руслан ., Кстати, по если не учитывать порядок вершин, то там что-то порядка 2^n получается циклов. Тоже дофига на самом деле.

[Руслан .]

Wataru, вот у меня как раз и вышло что порядок около 2^n, это конечно тоже много, но значительно меньше n^n если перебор затевать.
Спасибо!

[inek]

Спасибо всем, если я правильно понял эта задача относится к задачам класса np (поиск всех циклов в графе и поиск гамильтонова цикла). По поводу гамильтоновых циклов была информация, что есть алгоритм их поиска в книге Липского В. "Комбинаторика для программистов", но книгу найти пока не удалось... Вообще если такой алгоритм есть, то как быть с утверждением из источников по сложности алгоритмов о том, что если найдено решение одной np сложной задачи, то все остальные задачи этого класса тоже решаемы...?
И кроме того, интересно насколько решение этих задач практически значимо именно с прикладной точки зрения? Где они используются кроме непосредственно математики и прикладной логистики? Я имею ввиду прикладные химию, физику, ИТ, производство, проектирование и пр. Или всем вполне хватает тех возможностей, которые позволяют найти решения для них при малых числах вершин?

[Wataru]

inek, Поиск Гамильтонового цикла, действительно - NP полная задача и человечеству не известен полиномиальный алгоритм ее решения. Похоже, вы что-то путаете. Может упоминаемый вами алгоритм имеет экспоненциальную сложность и все сходится. Или, скорее всего вы спутали с задачей поиска Эйлерова цикла. Для него действительно есть полиномиальный алгоритм. Вот только он для решения немного другой задачи: поиск ЛЮБОГО ОДНОГО эйлерового цикла. Не всех - их тоже может быть экспоненциально много. Точно так же задача поиска одного любого цикла легко решается обыкновенным DFS за линейную сложность.

Что касается практического применения. Такового у просто задачи найти все циклы - я не вижу. Только как часть полного перебора для какой-то другой задачи, например той же задачи коммивояжера.

[inek]

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