2

我假设我们有 2 个标记图 G 和 T 并且算法确定 G 是否是 T 的子图以及主图 T 中的相应顶点和子图 G 应该具有相同的标签

4

2 回答 2

2

这个问题被称为“子图同构”，它是 NP 完全的（因此可能很难）。您是否需要为此提供通用解决方案，还是仅针对特定图表G？第二种情况要容易得多。这里有一些关于算法的一般信息。Boost Graph Library 中有一种算法的版本（实际上是针对更普遍的问题）（请参阅此处的文档）。

于 2011-03-11T23:42:15.193 回答
1

一般问题的一般答案：您要解决的问题称为“子图同构”。在这里查看更多参考资料：http ://en.wikipedia.org/wiki/Subgraph_isomorphism_problem 。

于 2011-03-11T23:43:14.063 回答