subgraph - 有没有简单的例子来解释乌尔曼算法

Question

我是学习图论的大一新生。我现在正在学习(子)图同构。有两个重要的算法:Ullmann 算法和 vf2。

我已经阅读了 Ullmann 的论文:一种子图同构算法。我也用谷歌搜索过，谷歌给了我很多它的应用程序，但我无法理解算法的过程。

你能给我一个简单的解释吗？

Answer 1

This answer到一个相关的问题给出了乌尔曼算法的源代码。

These slides举个例子，但是在幻灯片“Ullmann’s Algorithm V2”上只提到了算法的主要成分，没有一个例子。

所以下面我举个例子。我们想知道 GB 是否有一个与 GA 同构的子图。也就是说，我们将尝试将 GA 的顶点映射到 GB 的顶点，以便 GA 的边映射到 GB 的边上。



请注意，原始论文和幻灯片都使用称为 M 的矩阵，但代码没有。那是因为矩阵表示的与代码中的 possible_assignments[i] 相同。如果第 i 个顶点可以映射到 GB 的第 j 个顶点，则 M[i][j] 正好为 1。对于 GB 的顶点集，我将使用候选 (u) 等，其中可以映射 GB 的顶点 u。

第一个观察结果是 GA 的顶点只能映射到 GB 的顶点，其度数至少相同。所以最初，候选者(u)=候选者(v)={a，b，e，f，g}，候选者(w)={f}和z的候选者都是GB的顶点。

现在是我们第一次进行“refine M”过程，这是乌尔曼算法的主要成分。也就是说，我们检查每当 GB 的顶点 x 是 GA 的顶点 y 的候选者时，那么 y 的每个邻居在 x 的邻居中至少有一个候选者。如果此检查失败，则我们从 y 的候选中删除 x。我们会检查这些删除，直到无法再删除为止。

例如，h 是 z 的候选者之一。但是，w 是 z 的邻居，但 h 的邻居(即 g)都不在 cadidates(w)={f} 中。因此我们永远无法将 z 映射到 h，因为边 {w,z} 将映射到非边。所以我们可以安全地从候选项(z)中删除 h。细化的结果是:候选人(u)=候选人(v)=候选人(z)={a，e，g}和候选人(w)={f}。

现在我们开始回溯。

我们首先尝试将 u 映射到 a。也就是说，我们设置了Candidates(u) = {a} 并从其他候选集中删除了a。 Refine 发现 e 和 g 都不是 a 的邻居，因此我们从候选 (v) 中删除 e 和 g。这使得候选人(v)为空，所以我们从这个分支返回；撤消对候选人所做的更改。

现在，我们尝试将 u 映射到 e。同样，候选人(v)最终将是空的。

最后，我们尝试以相同的结果将 u 映射到 g。

我们得出结论，GA 不是 GB 的子图。无需尝试所有 8*7*6*5 分配。

我忘记了 Ullmann 最初是按照度数递减的顺序对 GA 的顶点进行排序的。但这不会有太大区别——我们只会首先发现 w 只能映射到 f，然后我们将继续在 u 上进行分支，结果与我们得到的结果完全相同。