強く接続されたコンポーネントですべての単純サイクルを検出する（複雑さ）

Question

私は、2人のプレーヤの通常のフォームゲーム（ゲーム理論）を表す特定のグラフィカルな構造で作業しています。私はTarjansを介してO（V + E）の有向グラフのすべての強連結成分を計算することができることを知っていますが、強く連結された成分のすべての単純サイクルを計算する複雑さは何ですか？そして、もし強連結成分を定義する頂点の数が与えられていれば、そのような単純サイクルの数には既知の上限があるでしょうか？

私はこれらの問題に関連する文献やアルゴリズムを探しています。ありがとうございました！

Answer 1

グラフの方向は無向ですか？ いずれの場合でも、サイクル数は明らかにノード/エッジの数で指数関数的である可能性があります。たとえば、完全なグラフでは、2から nまでのすべての可能なサイズのすべての順列が1サイクルになります。

Johnson's algorithm（有向グラフの）サイクルを列挙するのが効率的なもののようです。強く接続されたコンポーネントのサイクルに興味があるとすれば、実装はこのペーパーで説明されているものよりわずかに簡単です。論文の疑似コードは読みにくいです。このOcaml implementationは少し処理する方が簡単かもしれません。アルゴリズムは、 O（n + e）（c + 1）を持ちます。ここで、 cはグラフのサイクル数です。