2 つのラベル付きグラフ G と T があり、アルゴリズムは、G が T のサブグラフであり、メイン グラフ T とサブグラフ G の対応する頂点が同じラベルを持つべきかどうかを判断すると仮定します。
4460 次
2 に答える
2
その問題は「部分グラフ同形性」と呼ばれ、NP 完全です (そして難しい可能性があります)。これに対する一般的な解決策が必要ですか、それとも特定のグラフだけGですか? 2 番目のケースははるかに簡単です。ここには、アルゴリズムに関する一般的な情報がいくつかあります。アルゴリズムの 1 つのバージョン (実際には、より一般的な問題用) がブースト グラフ ライブラリにあります (こちらのドキュメントを参照してください)。
于 2011-03-11T23:42:15.193 に答える
1
一般的な質問に対する一般的な回答: 解決したい問題は、「サブグラフ同型」として知られています。詳細については、http: //en.wikipedia.org/wiki/Subgraph_isomorphism_problemを参照してください。
于 2011-03-11T23:43:14.063 に答える