algorithm - マルチグラフでのサイクル検出

Question

無向マルチグラフのすべてのサイクルをリストしたいと思います。

Tarjan の強連結成分アルゴリズムは、有向グラフ用に作成されました。マルチグラフでも機能しますか？そうでない場合、無向マルチグラフのサイクル リスト アルゴリズムはありますか?

Answer 1

サイクルをカウントする方法に応じて、問題を Tarjan に減らす方法がいくつかあります。

まず、グラフに 2 つの変換を適用します。

1. 各無向辺を向かい合う有向辺のペアで置き換えることにより、有向グラフに変換します。
2. ノードのペアごとに、同じ方向を指すエッジを 1 つのエッジに集約します。

有向グラフが残ります。Tarjan のアルゴリズムを適用します。

さて、あなたがサイクルを何と見なすかに応じて、あなたは終わっているかもしれませんし、終わっていないかもしれません. サイクルがノードのセットである場合 (必要なエッジをたまたま所有している場合)、変換されたグラフからサイクルを直接読み取ることができます。

サイクルが一連のエッジ (必要なノードを共有する) である場合、上記の手順 2 で導入されたエッジを「展開」する必要があります。折りたたまれたエッジごとに、置き換えられた実際のエッジのセットに沿って列挙します。折りたたまれた各サイクルの各エッジに対してこれを行うと、組み合わせ爆発で実際のすべてのサイクルが生成されます。これにより、プルーニングが必要な誤った 2 サイクルが生成されることに注意してください。

説明のために、元のグラフに と の間に 2 つのエッジ、との間に 1 つ、との間に 1 つの 3 つのノードA、B、があるとします。折りたたまれたグラフは、1 つのサイクルを持つ三角形になります。CABBCAC

3 つのノード間のサイクルを見つけたら、エッジの各組み合わせをウォークして、サイクルの完全なセットを回復します。ここでは、2 つのサイクルがあります。どちらもtoエッジとAtoエッジを含みます。どちらを選択するかが異なります。CBCAB

元のグラフにもBとの間に 2 つのエッジがある場合、C展開されたグラフは 4 つになります。展開されたサイクルの総数は、エッジ カウントの積です4 == 2 * 2 * 1。