0

我们什么时候使用 Ulmann 和 VF2 算法？在图论中使用这些算法的确切目的是什么？

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

4

1 回答 1

0

这些算法对于图同构和子图同构都很有用。

假设您有一个图G=(V,E)和另一个图G'=(V',E')。

如果G = G' （这意味着 G '中G的每个顶点和边之间存在相关性）那么您就存在图同构问题

如果G > G' （这意味着在G'中G的子图的每个顶点和边之间存在相关性），那么您就存在子图同构问题

已知VF2比 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

于 2014-01-31T18:20:13.030 回答