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

Question

大きな (数千ノード) 有向グラフGと、はるかに小さい (3-5 ノード) 有向グラフgがあるとします。Gにgの同型がいくつあるかを数えたいと思います。言い換えれば、G内の一意のノード セットがgに一致する数を知りたいのです。これはサブグラフ同型問題のインスタンスであり、したがって NP 完全であることを認識しています。ただし、 gが小さいと仮定すると、これを行うための合理的に効率的なアルゴリズムはありますか?

Answer 1

グラフ同型は一般に NP 完全ですが、現実の世界で遭遇する問題は多くの場合非常に簡単です。単純な力ずくで十分です: M_ig の最初の i ノードから G のノードまでのマップのセットを とします。空のマップを含むことから始めて、一度に 1 ノードずつ拡張し、制約iffm_0に違反するマップを破棄します。x->ym(x)->m(y)

多くの剪定が早期に行われるように、ノードを g で順序付けする必要があります。グラフがかなりまばらであると仮定すると、できるだけ多くのエッジをできるだけ早く完了する順序が必要になります。おそらく、最高度のノードからの dfs です。