algorithm - 偶数サイクルを検出するグラフアルゴリズム

Question

無向グラフがあります。そのグラフの 1 つのエッジは特別です。最初のエッジを含む偶数サイクルの一部である他のすべてのエッジを見つけたいです。

すべてのサイクルを列挙する必要はありません。それは本質的に NP だと思います。各エッジについて、上記の条件を満たすかどうかを知る必要があるだけです。

ブルートフォース検索はもちろん機能しますが、遅すぎるため、より良いものを見つけるのに苦労しています. どんな助けでも感謝します。

Answer 1

私たちは答えを持っていると思います (私の同僚のアイデアを信用しなければなりません)。本質的に彼のアイデアは、偶数サイクルの空間を通してフラッド フィル アルゴリズムを実行することです。これが機能するのは、2 つの小さいサイクルをマージして形成された大きな偶数サイクルがある場合、小さいサイクルは両方とも偶数または両方とも奇数でなければならないからです。同様に、奇数サイクルと偶数サイクルをマージすると、常により大きな奇数サイクルが形成されます。

これは、偶数サイクルと奇数サイクルが交互に繰り返される病的なケースを想像できるため、実用的なオプションです。この場合、隣接する 2 つの偶数サイクルは決して見つからないため、アルゴリズムは遅くなります。しかし、そのようなケースは実際の化学では起こらないと確信しています。少なくとも現在知られている化学では、30 年前にはフラーレンについて聞いたことがありませんでした。

Answer 2

グラフのノード次数が小さい場合は、別のグラフ表現の使用を検討できます。

3 つの原子u,v,wと 2 つの化学結合e=(u,v)と とするk=(v,w)。このようなデータを表現する一般的な方法は、グラフにu,v,wノードおよびエッジとして格納することです。e,k

ただし、グラフ内のノードとしてeとを表すことができ、 からへの 2 ステップ リンクを表す、またはのようなエッジを持ちます。このようなグラフでサイクルを見つけるアルゴリズムを実行すると、元のグラフのすべての偶数サイクルが返されます。kf=(e,k)fuwf=(e,k)f=(u,v,w)

もちろん、これは元のグラフのノード次数が小さい場合にのみ有効です。ユーザーが編集を実行すると、それに応じて代替表現を簡単に編集できます。