当我们使用Ulmann和VF2算法时，有人可以描述我吗？

Question

当我们将使用Ulmann和VF2算法？ 在图论中使用这些算法的目的究竟是什么？

它是用来描述主Graph内的子图吗？

Answer 1

这些算法对于图同构和子图同构是有用的。

假设有一个图形G =（V，E）和另一个图形G '=（V'，E'）。

如果G = G '（这意味着在的每个顶点和边缘ģ之间的相关G'），那么你是在一个graph-isomorphism problem

如果ģ“G存在“（这意味着在的G ģ子图的每个顶点和边缘之间的相关性”）那么你在一个subgraph-isomorphism problem

存在210

VF2是known to be faster than Ullmann。

这里有学术论文其描述他们：

• Ullmann

• [VF2]：http://59.108.48.5/intro/leizou/teaching/2012-autumn/papers/part2/VF2%20A%20(sub)Graph%20Isomorphism%20Algorithm%20For%20Matching%20Large%20Graphs.pdf