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

[inek82]

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

[_Swetlana]

Здравствуйте.
1. Есть, конечно. Переборный алгоритм с возвратом, т.н. бэктрекинг (backtracking). У меня есть реализация (на паскале) для поиска всех гамильтоновых циклов. Описание алгоритма взято из книги Витольда Липского "Комбинаторика для программиста". Алгоритм с возвратом генерирует повторяющиеся решения, каждый цикл печатается два раза, по часовой и против часовой стрелки.
Ну можно его переделать под поиск всех циклов. Всё это будет работать, если в графе не больше 20 вершин, потом наступит экспоненциальный взрыв.

2. Для большей размерности вам знать все циклы ни к чему, вы запрашиваете информацию большую, чем сумеете переработать в течение всей жизни. Ну давайте подсчитаем, сколько гамильтоновых циклов в полном графе: любая перестановка вершин будет циклом. $n!$ - большое число, например, при $n=250$ это больше, чем число атомов в видимой нами части Вселенной.

3. Обычно все циклы в графе хотят узнать люди, которые не умеют делать корректные математические постановки. Например, для того, чтобы разомкнуть все циклы в неориентированном графе достаточно найти поиском в глубину все хорды и удалить их из графа. Или просто построить каркас графа глубиной или шириной.
Если что-то нужно сделать для всех циклов неориентированного графа, можно сделать это для фундаментального множества циклов. Ф-циклы находятся всё тем же поиском в глубину кубическим (от числа вершин) алгоритмом (Витольд Липский "Комбинаторика для программиста").

[realeugene]

inek82 в сообщении #1525261 писал(а):

эффективный

Циклов в общем случае экспоненциально много.

[inek82]

_Swetlana в сообщении #1525275 писал(а):

Для большей размерности вам знать все циклы ни к чему, вы запрашиваете информацию большую, чем сумеете переработать в течение всей жизни.
...
Если что-то нужно сделать для всех циклов неориентированного графа, можно сделать это для фундаментального множества циклов. Ф-циклы находятся всё тем же поиском в глубину кубическим (от числа вершин) алгоритмом (Витольд Липский "Комбинаторика для программиста").

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

[mihaild]

inek82 в сообщении #1536208 писал(а):

задача поиска Гамильтонова цикла (циклов) относится к нерешенным задачам или даже к задачам класса np

Задача проверки наличия в графе гамильтонова цикла - классический пример np-полной задачи.

inek82 в сообщении #1536208 писал(а):

как и задача поиска всех циклов графа

А вот задача поиска всех циклов графа - не является np-полной, не принадлежит np и вообще не является задачей распознавания (а np принадлежат только задачи с отвтеом "да/нет").
Для задачи поиска всех циклов разумно думать об алгоритмах с полиномиальной задержкой, и такой алгоритм придумывается несложно (если я нигде не ошибся): берем ребро $AB$, перебираем все ребра вида $AC$, если есть путь $C \to A$, не проходящий через эти два ребра - перечисляем все такие пути (перебираем всех кандидатов в очередное ребро и проверяем, есть ли хоть один нужный путь).

inek82 в сообщении #1536208 писал(а):

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

К ним сводится очень много всего (правда часто с квадратичным или хуже ростом в размере задачи), да и сами проблемы с графами вроде бы нужны для каких-то схем или построения маршрутов.

[inek82]

mihaild в сообщении #1536217 писал(а):

inek82 в сообщении #1536208 писал(а):

...берем ребро $AB$, перебираем все ребра вида $AC$, если есть путь $C \to A$, не проходящий через эти два ребра - перечисляем все такие пути (перебираем всех кандидатов в очередное ребро и проверяем, есть ли хоть один нужный путь).

да, если перебирать так, то результат будет, но, как показали выше - при росте входа получим резкий рост сложности...
а что касается сведения к задачам с получением алгоритмов квадратичной точности - алгоритмы сложности до n^6 в некоторых случаях, думаю, будут приемлемыми, так как сильно увеличивают возможности по сравнению с полным перебором, который дает для плотного графа почти n! или e^n...

[_Swetlana]

1. Набираем в яндексе Витольд Липский Комбинаторика для программиста и по первой же ссылке скачиваем книгу
https://vk.com/wall-101965347_180259

2. Очень рекомендую почитать уже Липского, многое разъяснится.
а) Открываете Липского, читаете главу Поиск в глубину.
б) Не закрывая Липского, находите и читаете главу Алгоритм с возвратом (это и есть бектрекинг).
в) После прочтения задаёте себе вопрос:
А чем, собственно, линейный (от числа вершин и числа рёбер) поиск в глубину, который находит на графе ровно один путь (если мы его используем для поиска пути между двумя вершинами), отличается от экспоненциального алгоритма с возвратом, который генерирует все пути пути между двумя вершинами?

И отвечаете: Они (эти два алгоритма, глубина и алгоритм с возвратом) отличаются ровно одной строчкой. В глубине, когда мы возвратом уходим из просмотренной вершины, вершина остаётся просмотренной.
В алгоритме с возвратом, когда мы уходим из вершины, она становится снова новой и пригодной для дальнейшего использования.

3. Если речь идёт о реальных задачах, то во многих из них среди прочего есть и коммивояжер. Например, при планировании очередности изготовления чего-либо очень часто возникает коммивояжер. Разные последовательности имеют разные технологические нарушения, вариантов - n!