4

各ノードが原子であり、各エッジが原子間の接続であるグラフで分子を表現したいとします。2 つのグラフ (分子を表す) が等しいかどうかを判断するアルゴリズムは何でしょうか。分子が表現されているため、各ノードにはそれがどの分子であるかを定義する属性が必要です (炭素、窒素、酸素など)。

簡単にするために、各グラフが、アルゴリズムの開始ノードとして使用できる同じルート原子である窒素から分岐するとします。

例えば。NX、NY、NZ。ここで、N はルートの窒素ノードで、X、Y、Z はグラフの残りの部分です。

4

3 に答える 3

10

それがグラフ同型問題です。

グラフ同型問題は、NP に属する計算複雑性理論の数少ない標準問題の 1 つですが、よく知られている (そして、P ≠ NP の場合は互いに素な) 部分集合である P および NP-完全のいずれにも属していないことが知られています。これは、Garey & Johnson (1979) にリストされている複雑さが未解決のままである 12 の合計問題のうちの 2 つだけの問題の 1 つであり、もう 1 つは整数因数分解です。

つまり、一般論で解くのは難しい。

于 2012-10-06T19:59:40.187 に答える
5

私は、一般的なケース（一般的ではないケースでさえ）を解決するのは難しいというヨアヒム・イサクソンの答えに同意します。しかし、私は、指定された開始要素を持つ分子ツリーグラフの比較的狭いケースを解決するための戦略を提案したいと思います。[これは、私がこの回答に取り組んでいる間に投稿されたPeterdeRivazの回答に相当することに注意してください。]

まず、そのグラフに固有の分子グラフを記述するためのフォームまたは言語を定義しましょう。グラフで形成できる文字列は1つだけです。これにより、2つの文字列を比較して、2つのグラフが同じであるかどうかを判断できるため、問題を軽減して、比較する2つの正しい文字列を作成できます。（このアプローチには、完全なグラフ比較アルゴリズムよりも視覚的にデバッグしやすいという利点もあります。）私は通常、H2OやH2SO 4のような形で記述された分子を目にしますが、このアプローチはグラフィネスを維持しません。分子の数が多いため、比較には使用できません（H 2Oは水またはその要素の他の非常に奇妙な配置である可能性があります）。それでは、Lispのようなものを使用して、次のルールに従って分子を記述しましょう。

  1. 各グラフ（サブグラフを含む）はで始まり、(で終わります)
  2. 子を持つノードAは、新しいグラフにリストされる最初のノードであり、このグラフは、特定の順序で親グラフにリストされます（後で決定されます）。
  3. 子を持たないノードAは、その親グラフに特定の順序でリストされます（後で決定されます）。

これらの開始ルールを使用して、H2Oをよりグラフのような用語で説明できるようになりました。

  1. Oはグラフのルートであるため、新しいグラフが開始されます。(O)
  2. Hはの最初の子ですがO、子がないため、サブグラフの先頭としてではなく、そのまま親にリストされます。(OH)
  3. Hはの2番目の子ですがO、には子がないため、サブグラフの先頭としてではなく、そのまま親にリストされます。(OHH)

それで

H2Oのグラフ

になり(OHH)ます。

この場合の順序は重要ではありません。2つHのは子供がなく、要素的に同等だからです。

このアプローチをテストするために、奇妙で不合理な形のH2Oを試してみましょう。

OHHのグラフ

  1. Oはグラフのルートであるため、新しいグラフが開始されます。(O)
  2. Hの最初の子ですO。子があるため、新しいグラフが開始されます。(O(H))
  3. Hはの最初の子ですがH、には子がないため、サブグラフの先頭としてではなく、そのまま親にリストされます。(O(HH))

これまでのアプローチでは、順序付けが問題にならないH 2 Oのような単純なケースを処理できることはわかっていますが、H 2 SO 4Oは、から外れる要素を一貫して順序付けしないと機能しませんS。サブグラフ（サブグラフがある場合）が計算されるまで、子に意味のある順序を与えることはできないため、実行する最終ルールを追加します。

  1. 各グラフ（サブグラフを含む）はで始まり、(で終わります)
  2. 子を持つノードAは、新しいグラフにリストされる最初のノードであり、このグラフは特定の順序で親グラフにリストされます（ステップ4を参照）。
  3. 子を持たないノードAは、その親グラフに特定の順序でリストされます（ステップ4を参照）。
  4. すべての子ノードにアクセスし、それらのサブグラフ（存在する場合）を作成したら、親ノードの子ノード/子サブグラフをアルファベット順に並べます

この新しいルールを使用してH2Oを再検討すると、 2Hつのがアルファベット順に同等であり、子がないため、同じ出力が生成されます。では、H 2SO4を試してみましょう。

h2so4のグラフ

  1. Sはグラフのルートであるため、新しいグラフが開始されます。(S)
  2. Oの最初の子ですS。子があるため、新しいグラフが開始されます。(S[unsorted:](O))

  3. 「H」はの最初の子ですO。子供はいません。処理する子は他にないため、このレベルでの並べ替えは必要ありません。(S[unsorted:](OH))

  4. Oの2番目の子ですS。これには子供がいません：(S[unsorted:](OH)O)

  5. Oの3番目の子ですS。子があるため、新しいグラフが開始されます。(S[unsorted:](OH)O(O))

  6. 「H」はの最初の子ですO。子供はいません。処理する子は他にないため、このレベルでの並べ替えは必要ありません。(S[unsorted:](OH)O(OH))

  7. Oの4番目の子ですS。これには子供がいません：(S[unsorted:](OH)O(OH)O)

  8. 最後に、の子をSアルファベット順に並べ替えます(S(OH)(OH)OO)（アルファベット順の比較では、サブグラフに特別な扱いをしていることに注意してください。ただし、これは必須ではありません）。

最終結果は(S(OH)(OH)OO)

H 2 SO 4のバリエーションを試して、何が生成されるかを見てみましょう。これはアプローチが優れていることを証明するものではなく、グラフの変化がどのように異なる結果を生み出すかを示すだけであることに注意してください。

いくつかの奇妙なH2SO4のグラフ

  1. Sはグラフのルートであるため、新しいグラフが開始されます。(S)
  2. Oの最初の子ですS。子があるため、新しいグラフが開始されます。(S[unsorted:](O))
  3. O最初の子供です。子供はいません。(S[unsorted:](O[unsorted:]O))
  4. Hは2番目の子で、子はありません。(S[unsorted:](O[unsorted:]OH))
  5. 次に、の子を並べ替えますO。(S[unsorted:](OHO)
  6. Oの2番目の子ですS。子があるため、新しいグラフが開始されます。(S[unsorted:](O))
  7. H最初の子供です。子供はいません。(S[unsorted:](OHO)(O[unsorted:]H))
  8. Oは2番目の子で、子はありません。(S[unsorted:](OHO)(O[unsorted:]HO))
  9. 次に、の子を並べ替えますO。(S[unsorted:](OHO)(OHO))
  10. 最後に、の子をSアルファベット順に並べ替えます。(S(OHO)(OHO))

このH2SO 4（）は前のもの（）とは異なります。(S(OHO)(OHO))(S(OH)(OH)OO)

私は、このアプローチが機能することが保証されていることを正式に証明したり、正式に説明したり、結合数などの幅広い分子の特徴を説明したりすることはしませんでした。ただし、少なくとも、グラフ比較の問題を解決してみることをお勧めします。私はそれが実行可能だと思います。

于 2012-10-06T21:32:07.930 に答える
3

あなたの質問には「ツリー」というタグが付けられていますが、これはグラフにループがないことを意味している可能性がありますか?

この場合、分子が同等かどうかを調べる効率的なアルゴリズムがあります。

ルート アトムが与えられたとき、これが下に伸びる木のてっぺんだと想像してください。

アイデアは、どのサブツリーが同等であるかをツリーの最下部から繰り返し作業することです。

一番下から始めて、両方の分子のすべての同等の原子にラベルを付けます。このリストを並べ替えて、両方のリストが一致することを確認します。(一番下のレベルでは、これは単に各タイプの原子の数が同じかどうかを数えているだけです。)

次に、次に低いレベルまで作業します。各アトムには、アトム タイプに基づいたラベルと、接続先のサブツリーの並べ替えられたラベルを付けます。

このリストをもう一度並べ替えて、リストが一致することを確認します。

ルート ノードに到達したときに、すべてのチェックに合格した場合、分子は同形です。

于 2012-10-06T21:26:10.353 に答える