私は無向グラフを持っています。そのグラフの1つのエッジは特殊です。私は最初のエッジを含む偶数サイクルの一部である他のすべてのエッジを探したい。偶数サイクルを検出するグラフアルゴリズム
私はすべてのサイクルを列挙する必要はありませんが、それは本質的にNPだと思います。私はちょうどそれが上記の条件を満たすかどうか、それぞれのエッジについて知る必要があります。
ブルートフォース検索はもちろん機能しますが、遅すぎます。私は何か良いものを思いつくために苦労しています。どんな助けもありがたい。
私は答えがあると思います（私の同僚にその考えを信じる必要があります）。本質的に彼のアイデアは、偶数サイクルの空間を通してフラッドフィルアルゴリズムを行うことです。これは、2つの小さなサイクルをマージすることによって大きな偶数サイクルが形成された場合、小さいサイクルは偶数または両方とも奇数でなければならないためです。同様に、奇数と偶数のサイクルをマージすることは、常により大きな奇数サイクルを形成する。
これは、偶数サイクルと奇数サイクルを交互に繰り返す病理学的なケースを想像できるので、実際的な選択肢です。この場合、2つの隣接する偶数サイクルが決して見つからないので、アルゴリズムは遅くなります。しかし、私はそのような事例は実際の化学においては起こらないと確信しています。少なくとも化学的には現在知られているように、30年前にフラーレンについて聞いたことはありませんでした。
あなたのグラフが小さなノードの学位を持っている場合、あなたは別のグラフ表現を使用して検討するかもしれない：
は3個の原子u,v,wと2つの化学結合e=(u,v)とk=(v,w)をしてみましょう。そのようなデータを表現する典型的な方法は、u,v,wをノードとして、e,kをエッジとしてグラフに格納することです。
しかし、一つはfがwからu、f=(e,k)又はf=(u,v,w)から2段階のリンクを表すf=(e,k)ようなエッジを有する、グラフのノードとしてeとkを表すことができます。このようなグラフ上のサイクルを見つけるアルゴリズムを実行すると、元のグラフのすべての偶数サイクルが返されます。
もちろん、元のグラフのノード次数が小さい場合にのみ効率的です。ユーザーが編集を実行すると、代替表現を簡単に編集することができます。
ここでは、探している品質の答えを示すための情報が不十分です。特別なエッジがどれだけ早いか分かりますか？データの前処理が許可されていますか？どのくらい前にデータに触れているか（たとえばロードしていますか？）、データの前処理方法を変更できますか？ – ninjagecko
さらに、前処理の乱用が許されない場合には、すべてのサイクル**を見なければならないかもしれませんが、私はそのアサーションの証拠を何とか考えることはできません。 – ninjagecko
@ninjageckoグラフは化学構造を表します。つまり、頂点は原子であり、エッジはそれらの原子間の化学結合です。化学構造はユーザーによって継続的に編集されており、このアルゴリズムはユーザーが編集を実行するとリアルタイムで実行されることが期待されます。グラフには単純な隣接リスト構造を使用しますが、他のいくつかの構造も維持しています（たとえば、エッジがサイクルの一部であるかどうかは常にわかります）。私があなたのことを正しく理解していれば、グラフ（と特別なエッジ）は常に変化しているので、前処理はオプションではありません。 – john