Get best of the week

验证两个图的同构并搜索同构子图：一种基于NB路径分析的方法

大家好。

有一个任务-检查两个图是否彼此同构。也就是说，简单地说，就是要找出这两个图是否都是“相同”的图，但顶点数不同，并且如果以图形方式指定了图，则它们的空间位置也不同。这个问题的解决方案并不像乍看起来的人那么显而易见：即使对于小型图形，看看它们的图形表示也不会总是给出明确的答案。例如，请参见同一Wiki上的图形：en.wikipedia.org/wiki/Graph_isomorphism#Example。

好吧，显然吗？

但是还有一个更艰巨的任务：在“大”图中搜索与其他“小”图同构的所有子图。这是一个更加“黑暗的森林”。当然，这并不是完全黑暗的，但是您看到的任务并不是最简单的。

那我们有什么呢？

1.为什么所有这些都是必要的？


正如我们已经提到的，尽管同构（子）图的问题很复杂，但这是非常必要和有用的。做什么的？然后，例如，通过其结构式在数据库中搜索与给定分子相似的化合物。毕竟，它可以想象成一个图形，对吗？化学信息学做到这一点-有这样的科学。但是，还有与样本进行比较的任务，各种生物信息学任务以及许多其他有趣的事情。

2.如何解决这个问题？


解决这个问题的经典方法是由J. Ullman在1976年提出的[3]，后来他大大改进了他的算法[4]。而且，这种方法在许多其他作者的著作中得到了进一步发展，例如，Cordella和合著者[2]（VF2算法），Bonnitsi和合著者[1]（RI算法）等

。简而言之，该方法的本质是“智能”。列举“样本图B和样本A的顶点在其中进行搜索的可能对应关系”。通过此搜索，可以“聪明地”输入各种条件和限制，这些条件和限制使您可以尽早截断不合适的选项。同样，出于这些目的，可以对源数据进行各种初步处理。

我们不会在这里重述这些作品，但是我们将邀请读者独立地了解它们。但是，“表演胜于顺序”，应该指出的是，网络上有很好的图形示例和这些算法的说明。例如，请参阅以下内容：
coderoad.ru/17480142/Is-or-simple-example-for-explanation-algorithm-Ulman-一个很好而清晰的示例说明，
issue.life / questions / 8176298 -VF2算法的步骤和示例。

但是，问题来了-尽管有一些特殊情况，还有其他可能的方法来解决此问题吗？我想向您介绍这个问题的可能答案之一。

2.图和NB路径的同构


让我们立即达成共识：在NB路径下（不是英文，而是因为它太短了），我们将调用最大的非分支路径，即 一些图的最大无分支路径。

因此，如果我们有两个彼此同构的图，则对于第一个图的任何表示形式，即最大扩展的非分支路径的序列（即我们的NB路径中的那些），始终存在与之对应的第二个图的相同表示形式

  • 对于有向图，彼此对应的路径将对齐，
  • 对于无向图（对于有向图，分别为入站和出站边的数量），彼此对应的顶点度将等于
  • 当结果“组合”这样的表示时，我们将具有第一图和第二图的顶点的对应关系。

一个例子。图A = {1-> 2，1-> 6，4-> 5，5-> 1，3-> 3}。图B = {3-> 4，3->
5，1- > 2，2- > 3，6- > 6} PathsA（A的最大非分支路径）：1-> 2，1- > 6， 4-> 5-> 1，3-> 3 路径B（B的最大非分支路径）：3->
4，4，3- > 5，1- > 2-> 3，6- > 6 顶点匹配 ：1（ A）：3（B），2（A）：4（B），6（A）：5（B），4（A）：1（B），5（A）：2（B），3（ A）：6（B）。


因此，可以通过以下方式解决检查两个图的同构性的任务：找到彼此对应的路径，然后检查基于它们在获得的路径序列中顶点顺序的守恒性而构造的邻接矩阵的相等性（每个顶点一次添加到序列中，首先是“提及”）。在我们的示例中，以下顶点顺序将用于构造邻接矩阵：

A：1、2、6、4、5、3
B：

3、4、5、1、2、6 B：给定顶点顺序的A

图片

邻接矩阵：邻接矩阵对于给定的顶点顺序，对于B：

图片

矩阵相等；因此，图A和B是同构的。

此外，此方法（1）适用于有向图和无向图，（2）适用于包含多个连接/强连接组件的图，（3）适用于包含多个（多个）边和环的图，但是（4）不考虑没有边缘入射的顶点。

3.好，检查图的同构。但是搜索子图呢？


坦率地说，这里的一切都更加复杂。在这里，我们将受到以下限制：基于方法的本质，您不会找到任何子项，而只能找到“内接”子图。和我们称之为“内切”的子图曲线A这样的，可以是子图“粘”曲线A的其它部分仅由于边缘仅入射到其（子图）的边界顶点非分支的最大长度的路径（此外，曲线图A可以包含其他连接的组件）。不用担心，下面将作为示例，并且所有内容都将更加清晰。

此外，在解决此问题时，除了要搜索图A和图B的NB路径的长度对应关系（与上述同构测试相同），还需要分别搜索它们之间的以下可能对应关系：

  • NB路径的对应关系-从图B到NB路径的简单链-图A的简单链/简单周期。此外，图A中的此类路径最初可能会更长-在这种情况下，其段的长度等于从B到所需路径的长度。
  • 图B的NB-“末端”路径与图A的任何NB-路径的对应关系（在这种情况下，来自图A的路径也可以更长-在这种情况下，其段的长度等于从图B到所需路径的长度）。

让我们看一个例子：

图片

当在A列中搜索图B的“内接”同构子图（请参见上图）时，将找到以下对应关系：

  • B列的内部路径2-> 3-> 4：A列的内部路径2-> 3-> 4，
  • B列的末端路径1-> 2和10-> 2：A列的末端路径0-> 2和A列的末端路径7-> 1-> 2的一部分，即1-> 2，
  • 7->8 B: 9->10->11 A, 9->10 10->11, 12->13->14->12 A, 12->13, 13->14, 14->12.

因此，作为与图B同构的图A的“内接”子图，可以找到以下5个选项：

A1 = {0-> 2，1-> 2，2-> 3，3-> 4，4，> 5， 4-> 6，9-> 10}
A2 = {0-> 2，1-> 2，2-> 3，3-> 4，4-> 5，4-> 6，10-> 11}
A3 = {0-> 2，1-> 2，2-> 3，3-> 4，4-> 5，4-> 6，12-> 13}
A4 = {0-> 2，1-> 2，2 ->
3，3-> 4，4-> 5，4-> 6，13-> 14} A5 = {0-> 2，1-> 2，2-> 3，3-> 4，4-> 5，4-> 6，14-> 12}

但是，如果我们向图A添加一个额外的边线3-> 8，我们将得到图A'（在下图中）。并且在A'中，将不再有与图B同构的任何“内接”子图。确实：边线3-> 8将图A的路径2-> 3-> 4分为两部分，因此是内部路径2的候选路径->3->找不到4列B。

4.现在算法本身


现在，我们可以更详细地考虑A列“内接”到B列同构的子图的搜索算法。

因此，该算法将包括4个阶段：

  • 预处理
  • 匹配
  • 细化
  • 结论

第一阶段预处理


在此阶段，我们找到每个图的所有NB路径，并评估枚举期间限制选择空间的因素。那些。我们执行以下操作：

  1. 我们在A列中找到所有NB路径，并将它们放入动态数组（在C ++中-放入向量中）PathsA
  2. 我们在B列中找到所有NB路径，并将它们放入动态数组（向量）中。
  3. A B. II-IV , 1. A- B B: - , B.
  4. A B ( ).
  5. A B: DA DB .
  6. – B00 – B , , .

因此，我们在两张图上都有NB路径，并从p.p获得了极限参数。3-5。

第二阶段。映射


在此阶段，我们将从B列的每个NB路径的A列中选择候选NB路径（以下简称为“候选路径”）。为PathsB [i]的每个第i个路径从PathsA标记每个候选路径]将被写入二维动态数组（在C ++中-向量的向量）NPaths-分别写入第i个向量（第i行）-形式为数字的有序三倍：PathsA中相应路径的数目-PathsA中起始位置的数目-路径长度。

例如，PathsB [2] = {1、0、3、3、1、3}表示PathB [2]路径与A中​​的2条候选路径相关联：PathsA [1]-从零开始的前3个路径元素（初始），并从PathsA [3]开始-也有3个元素从第一个元素开始（在初始元素旁边）。

同时，我们将在4个方向上搜索（选择）候选路径：

  1. 从路径B中搜索图B的所有内部NB路径的候选路径。那些在图B中两个边界顶点都与至少两个其他顶点（无论这种连接的方向如何）相连的对象，同时，该路径也不是简单的循环（有向-对于有向图）。
  2. 从PathsB搜索用于跟踪NB路径的候选路径。
  3. 搜索NB路径的候选路径-来自PathsB的简单循环。
  4. 搜索NB路径的候选路径-来自PathsB的简单路径。

从PathsB中为每个第i条路径选择候选路径时，将对其进行比较（这是一些先前计算的限制器参数派上用场的地方）：

  • 它的长度和候选路径的长度（对于情况1和3，对于情况2和4，应相等，来自PathsA的候选路径也可以更长），
  • 它的边界顶点和候选路径的相应顶点的度（对于来自候选路径的顶点，这些值必须至少是来自PathsB的路径）。

如果根据阶段II的结果，没有为PathsB中的任何路径找到来自PathsA的单个候选路径，则认为A不包含与B列同构的“内接”子图。

细化


现在，让我们尝试“挤压”图A。我们只在图中留下那些进入找到的候选路径的边。如果与此同时，图A与其初始状态相比损失了至少一条边线，则我们返回到阶段I``预处理''：图A的顶点度，因此可以减少候选路径列表，并因此可以减少搜索空间。

第三阶段。细化候选路径列表


此步骤的目的是进一步消除尽可能多的不适当候选人。为此，我们执行以下步骤。

  1. 根据B列顶点之间的最小距离排除明显不合适的候选路径。对于每个PathB [i]的候选路径，至少找到一个PathB [j]的候选路径最短列A中其边界顶点之间的距离小于或等于图B中路径Paths [[i]和Paths B [j]]的对应边界顶点之间的最短距离。
  2. 从路径B到与其相关联的非循环候选路径的所有循环的异常，反之亦然。
  3. 类似于第1节的候选路径例外，但不取决于边界顶点之间最短距离的标准，而是取决于它们的（边界顶点）相互相等或不相等。

例如，如果：

  • PathsB [i]的起始元素不等于PathsB [j]的起始元素，并且
  • PathsB [i]的最终元素不等于PathsB [j]的最终元素，并且
  • PathsB [i]的开始元素等于PathsB [j]的结束元素，并且
  • PathsB [j]的开始元素不等于PathsB [i]的结束元素，

沿PathB [i]路径的候选路径，至少有一个PathB [j]找不到关于其（候选路径）初始和最终的相等/不相等的满足上述条件的任何候选路径高峰。

也就是说，粗略地说，我们基于与所有其他候选路径的距离（这些路径与所有其他候选路径都非常遥远），基于它们的周期性/非周期性，丢弃那些显然不会包含在所需子图中的候选路径；以及也基于它们的边界顶点与其他候选路径的边界顶点应有的相等/不等式。

如果根据阶段III的结果，从PathsA中删除了至少一条候选路径，则-再次-更新了列A-仅保留在其余候选路径中的那些边。而且，再次，如果同时使图A“失去权重”至少减少了一条边，我们将再次回到阶段I“预处理”：图A的顶点度以及相应的候选路径列表可以减少，从而可以减少搜索空间。

第四阶段。结论


所有剩余候选路径的每种可能组合都定义了列A的一个子图。对于每个此类子图，以与为图B构建邻接矩阵B00相同的方式，考虑候选路径的顺序来构造邻接矩阵，然后对这些邻接矩阵进行比较。

如果它们相等，则比较边缘的多重性（请参阅阶段I预处理的第3节）。如果满足所有这些条件，则将找到的子图视为与图B同构，并将其添加到找到的结果集中。

在阶段IV“结论”期间，可以使用各种其他检查来加快对不适当的子图的识别和拒绝。

5.如何混淆一切...考虑一个算法示例


我不认识你，但是如果没有一个例子，这对我来说是难以理解的。让我们看一个例子。

在图。下图是A = {1-> 2，2-> 5，5-> 15，16-> 15，5-> 5，5-> 5，5-> 4，5-> 6，7-> 6 ，6-> 8，6，-> 6，6，-> 9，9-> 10，9-> 11，12-> 0，0-> 12，4-> 13，13-> 14，14-> 4 }和B = {1-> 1，4-> 5，5-> 1，1-> 3，3-> 3，3-> 2，2-> 7，2-> 8，9-> 10， 10-> 9、1-> 6、6-> 11、11-> 12、12-> 6}。我们的任务是在图A中找到与图B同构的所有“内接”子图。结果也显示在图中：图A的找到的顶点和边线用粗线突出显示，并且图B的相应顶点的数目用括号括起来（如果有多个选项，则用括号表示）。分数）。

图片

解决与B列同构的“内接”子图的A列中的搜索问题时，我们得到该算法的以下结果。

阶段I：所有动作和计算均根据p.p.此步骤的1-5，以下是生成的PathA和PathB。

路径A：

1-> 2-> 5
4-> 13-> 14 4
5-> 4
5-> 5
5-> 6
5-> 15
6-> 6
6-> 8
6-> 9
7-> 6
9 -> 10
9-> 11
16-> 15
0-> 12-> 0

路径B：

1-> 1
1-> 3
1-> 6
2-> 7
2-> 8
3-> 2
3-> 3
4- > 5-> 1
6-> 11-> 12-> 6
9-> 10-> 9

阶段II-III。比较表明，对于来自路径A的每条路径，至少有一条来自路径B的候选路径，并且通过初步细化的结果缩短了路径A。在主要减薄阶段（III），没有进一步减少PathsA。结果，路径A和路径B的形式为：

路径A：

1-> 2-> 5
4-> 13-> 14-> 4
5-> 4
5-> 5
5-> 6
6-> 6
6-> 9
9-> 10
9-> 11
0-> 12-> 0

路径B：

1-> 1
1-> 3
1-> 6
2-> 7
2-> 8
3-> 2
3-> 3
4-> 5-> 1
6 -> 11-> 12-> 6
9-> 10->9

NPath的最终比较是：
NPaths：

i = 0：3 0 2
i = 1：4 0 2
i = 2：2 0 2
i = 3：7 0 2 8 0 2
i = 4：7 0 2 8 0 2
i = 5：6 0 2
i = 6：5 0 2
i = 7：0 0 3
i = 8：1 0 4
i = 9：9 0 3

现在是时候回顾一下NPaths [i]中每个有序三元组数字定义了相应的Paths B [i]候选路径从A格式：从PathA到相应路径的编号-从该路径开始的片段的起始位置-片段的长度。因此，很容易验证路径B [0] = {1-> 1}（i = 0：3 0 2）对应于从A开始的唯一路径，即从PathsA [3]开始的段和具有2的长度

第四阶段。结果，在与列B同构的A列中找到了唯一的子图A1。A1 = {0-> 12，1-> 2，2-> 5，4-> 13，5-> 4，5-> 5，5- > 6、6-> 6、6-> 9、9-> 10、9-> 11、12-> 0、13-> 14、14-> 4}。

5.接下来呢？


然后，原则上就是这样。尽管还不完全：作者必须承认该算法仍可以最终确定和确定。有什么要补充的？

  1. 当引入列A和B的顶点的附加特征时（例如，当化合物由化学化合物的图给出时，每个顶点只能与一个和一个原子（同位素）相对应的数字编码），由于根据阶段II进行的比较精度更高，因此可以加快搜索过程：选择候选路径的条件将是顶点标签的对应关系。
  2. . , «», «» - B.
  3. , , , «» :
    (1) «» , ,
    (2) .
    «» « - », , , .
  4. , - , .


一般问题：
1. Bonnici，V.，Giugno，R.，Pulvirenti，A.等。子图同构算法及其在生化数据中的应用。 BMC Bioinformatics 14，S13（2013）。doi.org/10.1186/1471-2105-14-S7-S13。
2. Cordella L，Foggia P，Sansone C，Vento M：用于匹配大型图的（子）图同构算法。 IEEE模式分析和机器智能交易。 2004，26（10）：1367-1372。 10.1109 / TPAMI.2004.75。
3. Ullmann Julian R .：子图同构的算法。计算机器协会杂志。 1976，23：31-42。 10.1145 / 321921.321925。
4. Ullmann Julian R .：用于二进制约束满足和子图同构的位向量算法。 J Exp算法学。 2011，15（1.6）：1.1-1.6。 1.64

用更正式的语言编写的关于此的预印本是最“基于NB-Paths的算法”，其中还包含有关尝试使用C ++实现的信息：
5. Chernoukhov SA 2020年。Preprints.RU。检查两个图的同构并搜索同构的“内接”子图：一种基于最大扩展非分支路径分析的方法来解决（子）图同构问题。DOI：dx.doi.org/10.24108/preprints-3111977

关于该主题的有用的互联网资源：
6. coderoad.ru/17480142/Is-li- simple-example-for-explanation-algorithm-Ulman
7. issue.life/questions / 8176298。

More articles:


All Articles