算法检查给定图是否是另一个图的子图

我假设我们有2个标记图G和T,并且该算法确定G是否是T的子图以及主graphT和子图G中的对应顶点应该具有相同的标签     
已邀请:
这个问题被称为“子图同构”,它是NP完全的(很可能很难)。您是否需要针对此的一般解决方案,或仅针对特定图表
G
?第二种情况要容易得多。这里有一些关于算法的一般信息。在Boost Graph Library中有一个算法版本(实际上,对于更一般的问题)(参见此处的文档)。     
一般问题的一般答案:您要解决的问题称为“子图同构”。在这里查看更多参考资料:http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem。     

要回复问题请先登录注册