graph - 如何检查两个带有 LABELED 顶点的图是否同构？

Question

例如，假设我有一个图 G，它包含所有蓝色节点和一个红色节点。我还有一个图 F，它有一个全蓝色和一个红色节点。

我可以运行什么算法来验证这两个图关于它们的彩色节点是同构的？

Answer 1

我已经尝试创建多项式图同构算法，虽然我还没有创建一个被证明在每种情况下都是多项式的算法，但我想出的一个算法特别适合这个目的。它基于 DFA 最小化算法（具体算法是http://en.wikipedia.org/wiki/DFA_minimization#Hopcroft.27s_algorithm；您可能想从其他地方找到描述，因为很难理解维基百科）。

最初的算法是通过根据度数将顶点组织成不同的组来初始化的（一组用于度数为 1 的顶点，一组用于度数为 2 的顶点，等等）。出于您的目的，您需要根据度数和标签将顶点组织成组；这将确保如果两个节点具有不同的标签，则不会配对。每个图都应该有自己的包含这些组的结构。检查两个图的组集合；两个图应该有相同数量的组，并且对于一个图中的每个组，另一个图中应该有一个组包含相同数量的相同度数和标签的顶点。如果不是这种情况，则图不是同构的。

在主算法的每次迭代中，您应该为下一步将使用的顶点组的两个图中的每一个生成一个新的数据结构。对于每个组，为与所讨论的顶点相邻的顶点对应的组索引/ID 的每个顶点生成一个列表（包括此列表中的重复组）。检查每个组以查看每个包含的顶点的排序组索引/ID 列表是否相同。如果是这种情况，请在下一步的组结构中创建该组的未修改副本。如果不是这种情况，那么对于该组中的每个组索引/ID 的唯一列表，为生成该列表的原始组中的顶点创建一个新组，并将这个新组添加到下一步的组结构中。如果在给定的迭代中不细分任一图的任何组，请停止运行该算法的主要部分。如果您至少细分一个组，则需要再次检查以确保两个图的组结构彼此对应。此检查将类似于在算法初始化结束时执行的检查（您甚至可以对两者使用相同的函数）。如果此检查失败，则图不是同构的。如果检查通过，则丢弃/释放当前组结构并使用新创建的组开始下一次迭代。此检查将类似于在算法初始化结束时执行的检查（您甚至可以对两者使用相同的函数）。如果此检查失败，则图不是同构的。如果检查通过，则丢弃/释放当前组结构并使用新创建的组开始下一次迭代。此检查将类似于在算法初始化结束时执行的检查（您甚至可以对两者使用相同的函数）。如果此检查失败，则图不是同构的。如果检查通过，则丢弃/释放当前组结构并使用新创建的组开始下一次迭代。

为了使确定“对应组”的过程更容易，我强烈建议使用可预测的方案将组添加到结构中。例如，如果在初始化时按（度，标签）顺序添加组，按索引升序细分组，并根据组索引列表的顺序（即按第一个列出的索引排序，然后是第二个等），那么两个组结构之间的对应组将始终具有相同的索引，这使得跟踪哪些组彼此对应的过程变得更加容易。

如果算法完成时所有组都包含 3 个或更少的顶点，则图是同构的（对于包含 2 个或 3 个顶点的相应组，任何顶点配对都是有效的）。如果不是这种情况（这总是发生在所有节点都具有相同度数和标签的图上，有时会发生在具有该属性的子图上），那么这些图尚未确定为同构或非同构。要区分这两种情况，请选择第一个图的最大组的任意节点并将其分成自己的组。然后，对于另一个图的最大组的每个节点，尝试再次运行算法，将该节点分成自己的组。在本质上，您正在从第一个图中选择一个未配对的节点，并通过猜测和检查将其配对到第二个图中仍然是合理配对的每个节点。如果任何分叉迭代返回同构，则图是同构的。如果它们都没有，则图不是同构的。

对于一般情况，该算法是多项式的。在极端情况下，算法可能是指数的。是否是这种情况与算法在图输入和节点选择的最坏情况下被迫分叉的频率有关，我在尝试设置有用的界限时遇到了困难。例如，虽然算法在比较两个完整图时在每一步都分叉，但该树的每个分支都会产生同构；因此，在这种情况下，算法在多项式时间内返回，即使遍历整个执行树将需要指数时间，因为仅遍历执行树的一个分支需要多项式时间。

无论如何，这个算法应该可以很好地满足您的目的。我希望我对它的解释是可以理解的；如果没有，我可以尝试提供处理简单案例的算法示例或将其表示为伪代码。

Answer 2

几年前，我为这个问题（带有标签的图同构）创建了一个简单而灵活的算法。

我将它命名为“Powerhash”，创建算法需要两个见解。第一个是幂迭代图算法，也用于PageRank。第二个是能够用我们想要的任何东西替换幂迭代的内部阶跃函数。我用一个函数替换了它，该函数在每次迭代和每个节点上执行以下操作：

• 对节点邻居的哈希值（来自上一次迭代）进行排序
• 散列连接的排序散列
• 用新计算的哈希替换节点的哈希

第一步，节点的散列受到其直接邻居的影响。第二步，一个节点的哈希值受到距离它 2 跳的邻居的影响。在第 N 步，节点的哈希值将受到其周围 N 跳的邻域影响。所以你只需要继续运行 N = graph_radius 步骤的 Powerhash。最终，图中心节点的哈希值将受到整个图的影响。

要生成最终哈希，请对最后一步的节点哈希进行排序并将它们连接在一起。之后，您可以比较最终的哈希值来确定两个图是否同构。如果您有标签，则将它们（在第一次迭代中）添加到您为每个节点计算的内部哈希中。

有关这方面的更多信息，您可以在此处查看我的帖子：

https://plus.google.com/114866592715069940152/posts/fmBFhjhQcZF

上面的算法是在“madIS”函数关系数据库中实现的。你可以在这里找到算法的源代码：

https://github.com/madgik/madis/blob/master/src/functions/aggregate/graph.py

Answer 3

只是检查; 你的意思是严格的图同构还是别的什么？同构图具有相同的邻接关系（即，如果节点 A 在一个图中与节点 B 相邻，则节点 g(A) 在另一个图中与节点 g(B) 相邻，这是将变换 g 应用于第一个图中的结果...）如果您只是想检查一个图是否具有与另一个图相同的类型和节点数，那么您可以比较计数。