В ряде практических приложений возникает необходимость поиска простых циклов на графах, в связи с чем встаёт вопрос об оценке количества вычислительных операций, необходимых для этого, т.е. вычислительной сложности задачи.

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

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

Уяснив стартовые данные, я впал в лёгкое уныние. Больше всего в тот момент мне хотелось сослаться на обстоятельства непреодолимой силы, перегруженность, невменяемость, сезонное обострение ящура – короче говоря, найти любой повод и – на волю, в пампасы! Но сакраментальное “ты ж программист!” и осторожное “буду должен… ” уже прозвучали, вздохи химика становились все тяжелее, размеренно падая на и без того узкую тропку к отступлению, химиковы глаза за толстыми стёклами очков давали изрядную фору фирменному взгляду Кота-в-сапогах из “Шрека”...

Пути назад не было. Квест начался.