有没有简单的例子来解释ullmann算法

Question

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

我读过Ullmann的论文:Subgraph Isomorphism 的算法.我也谷歌搜索它和谷歌给了我很多应用程序,但我无法理解算法的程序.

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

Answer 1

对相关问题的这个答案给出了Ullmann算法的源代码.

这些幻灯片给出了一个例子,但算法的主要成分仅在幻灯片"Ullmann算法V2"中没有提及.

我将在下面举例说明.我们想知道GB是否有与GA同构的子图.也就是说,我们将尝试将GA的顶点映射到GB的顶点,以便GA的边缘映射到GB的边缘.

请注意,原始纸张和幻灯片都使用称为M的矩阵,但代码不是.那是因为矩阵代表的是might_assignments [i]在代码中所代表的相同.如果第i个顶点可以映射到GB的第j个顶点,则M [i] [j]是1 .我将使用候选(u)等作为GB的顶点集,其中可以映射GB的顶点u.

首先观察到GA的顶点只能映射到GB的顶点至少具有较大程度.因此,最初,候选者(u)=候选者(v)= {a,b,e,f,g},候选者(w)= {f}并且z的候选者是GB的所有顶点.

现在是我们第一次进行"精制M"程序,这是Ullmann算法的主要成分.也就是说,我们检查每当GB的顶点x是GA的顶点y的候选者之中时,y的每个邻居在x的邻居中具有至少一个候选者.如果此检查失败,那么我们从y的候选中删除x.我们会检查这些清除,直到无法进一步清除为止.

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

现在我们开始回溯.

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

现在,我们尝试将u映射到e.候选人(v)将最终为空.

最后,我们尝试将u映射到g,结果相同.

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

我忘了Ullmann最初按照度数递减的顺序排列GA的顶点.但它不会有太大的区别 - 我们只会首先发现w只能映射到f然后我们将继续使用与我们得到的结果完全相同的分支.