图同构

Question

图同构

algorithmgraph

16

是否有用于图同构的算法或启发式算法？

推论：一个图可以用不同的绘图表示。

如何找出一个图的不同绘图的最佳方法？

- DarthVader

这个算法可能是你正在寻找的答案。多项式时间算法用于图同构测试和映射的链接 - Ahmad

9个回答

6

找到图同构中最好的算法之一是VF2。

我已经写了一篇关于VF2在化学中的高级概述- 在那里它被广泛使用。这篇文章涉及VF2和Ullmann之间的差异。还有一个用Java编写的从头开始实现VF2，可能会有所帮助。

- Rich Apodaca

4

一个非常类似的问题——图自同构——可以通过saucy来解决，该软件可提供源代码。它可以找到图形的所有对称性。如果你有两个图形，请将它们合并成一个，任何同构都可以被发现作为联接的自同构。

免责声明：我是 saucy 的合作者之一。

- Igor Markov

3

有算法可以做到这一点——然而，我还没有真正研究过它们。我相信Donald Knuth在他的计算机艺术系列中在第二次(重新)编写时会介绍这个主题。

至于在小图上可能实际起作用的简单方法，我建议计算度数，然后对于每个顶点，还要注意与之相邻的顶点的度数集合。这将为每个点提供一组潜在的顶点同构。然后只需从这个受限制的集合中尝试所有这些（通过蛮力，但选择潜在的顶点同构集合按递增顺序选择顶点）。直观地说，大多数图同构都可以通过这种方式在实践中计算出来，尽管显然会有可能需要很长时间的退化情况。

- Paul Hsieh

2

我的项目 - Griso - 在sf.net上：http://sourceforge.net/projects/griso/，并附有以下描述：
Griso是一个用C++编写的图同构测试工具。它基于我的自己POLYNOMIAL-TIME算法（这也是该项目的亮点）。请在http://funkybee.narod.ru/graphs.htm页面上查看Griso的样例输入/输出。

- trg787

3

你是什么动机自己设计算法？你有没有一篇论文描述它，并在不同类型的图上与流行的算法（如vf2，nauty）进行性能比较？您的算法动机是什么？您是否有一篇论文描述该算法并将其与流行的算法（如vf2、nauty）在不同类型的图上的性能进行比较？ - Szabolcs

@Szabolcs，是什么激励了我？是一个“多项式时间”算法。 - trg787

当然，如果算法100％正确，那将是不可思议的。但是我还没有遇到过它的反例（对于Griso_3in1版本）。 - trg787

2

我最近看到了这篇论文：http://arxiv.org/abs/0711.2010。这篇论文提出了“图同构的多项式时间算法”。

- ravi

1

nauty和Traces

nauty和Traces是用于计算图形和有向图的自同构群的程序[*]。它们还可以生成一个规范标签。它们是用C的可移植子集编写的，并且可以在许多不同的系统上运行。

GRAPE的GAP软件包中的AutGroupGraph命令。
bliss：另一个对称性和规范标记程序。
conauto：一个图形同构包。

- Human Learning

0

关于启发式算法：我一直在幻想一个修改过的Ullmann算法，不仅使用广度优先搜索，而且将其与深度优先搜索混合使用。首先你要集中使用广度优先搜索，然后设置广度分析的限制，在检查几个邻居之后再深入探索，并在每一步降低广度。这实际上就是我在地图上找路的方式：首先用广度优先搜索定位自己，然后用深度优先搜索搜索路径 - 大体上来说，这是我大脑发明的最好进化方式。长期来看，可以增加一些智能，以增加关键顶点的广度优先搜索邻居数量 - 例如，当有大量具有相同边数的相邻顶点时。就像有时候在没有GPS的情况下用车检查你的实际路线一样。

- user5501583

0

我发现该算法属于k维Weisfeiler-Lehman算法类别，并且在常规图形中失败。更多信息请参见：

http://dabacon.org/pontiff/?p=4148

以下是原始帖子：

我曾经研究过在图形数据库（包含化学成分）中查找同构图的问题。

简而言之，该算法使用幂迭代方法创建图形的哈希值。可能会出现错误的哈希碰撞，但这种概率非常小（我在数以万计的图形中没有遇到过这样的碰撞）。

算法的工作方式如下：

进行N次迭代（其中N是图形的半径）。在每次迭代和每个节点上：

对节点的邻居的哈希值（从上一步骤）进行排序
哈希连接排序后的哈希值
用新计算的哈希值替换节点的哈希值

在第一步中，节点的哈希值受其直接邻居的影响。在第二步中，节点的哈希值受其2跳邻域的影响。在第N步中，节点的哈希值将受到其周围N跳邻域的影响。因此，您只需要继续运行Powerhash N = graph_radius步即可。最终，图形中心节点的哈希值将受到整个图形的影响。

为了生成最终哈希，需将最后一步的节点哈希进行排序并连接在一起。然后，您可以比较这些最终哈希以判断两个图是否同构。如果有标签，则在计算每个节点的内部哈希时（第一步），将它们加入其中。

更多背景信息请查看以下内容：

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

你可以在这里找到它的源代码：

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

- estama

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Stefano Borini · Accepted Answer

这是一个麻烦的问题。

一般来说，基本思想是将图形简化为规范形式，然后进行规范形式的比较。生成跨度树以达到此目的，但跨度树并不唯一，因此需要有一种规范的方法来创建它们。

在获得规范形式之后，你可以相对容易地执行同构比较，但这只是开始，因为非同构的图可能具有相同的跨度树。（例如，考虑一棵跨度树T和向其添加单个边缘以创建T'的情况，这两个图不同构，但它们具有相同的跨度树）。

其他技术涉及比较描述符（例如，节点数，边数），但通常会产生误报。

我建议您先从维基百科页面“图同构问题”开始了解。我还有一本书推荐：“图论及其应用”。这是一本厚重的书，但值得一读。

根据你的推论，给定图的每种可能的空间分布都是同构的。因此，两个同构图具有相同的拓扑结构，并且从拓扑角度来看它们是相同的图。另一方面，例如要找到享有特定属性（例如，如果存在，则为非交叉边缘）的同构结构，则取决于您想要的属性。