サブグラフインスタンスのカウント

Question

私は大きな（数千ノード）監督されたグラフを持っているとしましょう g そして、はるかに小さい（3-5ノード）監督グラフ g. 。私はいくつの同型を数えたいです g にあります g. 。言い換えれば、私は一意のノードのセットの数を知りたい g マッチ g. 。これは、サブグラフ同型の問題の例であり、したがってNP不完全であることを理解しています。ただし、あなたがそれを想定するかもしれないことを考えると g 小さいですが、これを行うための合理的な効率的なアルゴリズムはありますか？

Answer 1

グラフの同型は一般にNP完全ですが、現実の世界で出会う問題は非常に簡単です。単純なブルートフォースで十分でなければなりません M_i Gの最初のiノードからGのノードまでのマップのセットになります。 m_0 空のマップを含むと、一度に1つのノードを拡張し、制約に違反するマップを破棄します x->y iff m(x)->m(y).

多くの剪定が早期に発生するように、Gでノードを注文することをお勧めします。グラフがかなりまばらであると仮定すると、できるだけ早く多くのエッジを完了する注文、おそらく最高のノードからのDFSが必要です。