与えられたグラフが別のグラフのサブグラフであるかどうかをチェックするアルゴリズム

Question

私は2つのラベル付きグラフGとTを持っていると仮定し、アルゴリズムはTのサブグラフとメイングラフTとサブグラフGの対応する頂点同じラベル

Answer 1

この問題は"subgraph isomorphism"と呼ばれています。これはNP完全なので難しくなります。これには一般的な解決法が必要ですか、特定のグラフの場合にのみG？ 2番目のケースははるかに簡単です。アルゴリズムに関する一般的な情報はhereです。 Boost Graph Libraryにはアルゴリズムの1つのバージョンがあります（実際には、より一般的な問題のため）。ドキュメントhereを参照してください。

Answer 2

一般的な質問に対する一般的な答え：解決したい問題は、「サブグラフ同形」として知られています。詳細はこちらを参照してください：http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem。