Обнаружение всех простых циклов в сильно связанных компонентах (сложность)

Question

Я работаю с определенной графической структурой, представляющей игры для нормальных форм для двух игроков (теория игр).Я знаю, что могу вычислить все сильно связные компоненты ориентированного графа в O (V + E) через Таржана, но мне было интересно, какова сложность вычисления всех простых циклов сильно связного компонента?И, если существует известная верхняя граница для числа таких простых циклов, учитывая количество вершин, определяющих сильно связную компоненту?

Я ищу любую литературу / алгоритмы, связанные с обеими этими проблемами.СПАСИБО!

Answer 1

Является ли график направленным или ненаправленным?В любом случае число циклов, очевидно, может быть экспоненциальным по количеству узлов / ребер.Например, в полном графе каждая перестановка каждого возможного размера от 2 до n приведет к циклу.

алгоритм Джонсона для перечисления циклов (вориентированные графы), кажется, один из наиболее эффективных.Учитывая, что вас интересуют циклы сильно связанного компонента, реализация даже немного проще, чем описано в статье.Псевдокод в газете немного сложен для чтения;эта реализация Ocaml может быть немного проще в обработке.Алгоритм имеет сложность O (n + e) ​​(c + 1) , где c - количество циклов в графе.