我是学习图论的大一新生。我现在正在学习（子）图同构。有两个重要的算法：Ullmann 算法和vf2。
我读过 Ullmann`s: An algorithm for Subgraph Isomorphism 的论文。我也google了一下，google给了我很多应用，但是我看不懂算法的过程。
你能给我一个简单的解释吗？
问问题
7478 次
1 回答
18
This answer to a related question给出了乌尔曼算法的源代码。
这些幻灯片给出了一个例子，但是在幻灯片“Ullmann's Algorithm V2”上只提到了算法的主要成分，没有一个例子。
所以我将在下面举一个例子。我们想知道 GB 是否有一个与 GA 同构的子图。也就是说，我们将尝试将 GA 的顶点映射到 GB 的顶点，以便将 GA 的边映射到 GB 的边上。
请注意，原始论文和幻灯片都使用称为 M 的矩阵，但代码没有。这是因为矩阵代表的可能与代码中的 possible_assignments[i] 相同。如果第i个顶点可以映射到GB的第j个顶点，则 M[i][j] 正好为 1 。我将使用候选（u）等作为GB的顶点集，其中可以映射GB的顶点u。
第一个观察是 GA 的顶点只能映射到 GB 的顶点，其度数至少相同。所以最初，candidate(u) = Candidate(v) = {a,b,e,f,g}，candidate(w) = {f}和z的候选都是GB的顶点。
现在是我们第一次执行“refine M”过程，这是 Ullmann 算法的主要成分。也就是说，我们检查当 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。也就是说，我们设置 Candidate(u) = {a} 并从其他候选集中删除 a。Refine 发现 e 和 g 都不是 a 的邻居，因此我们从候选 (v) 中删除 e 和 g。这使得 Candidate(v) 为空，所以我们从这个分支返回；撤消对候选人所做的更改。
现在，我们尝试将 u 映射到 e。同样，候选人（v）最终将是空的。
最后，我们尝试将 u 映射到 g，结果相同。
我们得出结论，GA 不是 GB 的子图。无需尝试所有 8*7*6*5 的作业。
我忘记了 Ullmann 最初是按度数递减的顺序对 GA 的顶点进行排序的。但这不会有太大区别——我们只会首先发现 w 只能映射到 f，然后我们会继续在 u 上进行分支，结果与我们得到的结果完全相同。
于 2013-09-06T19:55:35.343 回答