graph-theory - クエリ グラフと一致するサブグラフを見つける

Question

無向グラフがありますG。は頂点と辺の集合なのでG「データベース」として持っておきたい。

Hこれで、 のサブグラフであることが保証されGているクエリ グラフができました。Hのどの部分に対応するかをどのように把握できGますか?

Hこの質問は、ここにある既存のものとは異なりGます。

Answer 1

これがサブグラフ同型問題です。クエリ グラフを制限しない場合、それは NP 完全です (H をハミルトン サイクルにすることができるため)。グラフ H が非常に小さい (固定) 場合、多項式時間で G 内の H のコピーを見つけることができます (単純な力ずくで、またはウィキペディアのページで言及されているアルゴリズムによって)。