图同构 [英] Graph Isomorphism

问题描述

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

Is there an algorithm or heuristics for graph isomorphism?

推论：图形可以重新presented在不同的不同的图

Corollary: A graph can be represented in different different drawings.

什么是最好的方式找到一个图的不同的绘图？

What s the best approach to find different drawing of a graph?

推荐答案

这是一个问题的地狱。

在一般情况下，其基本思想是简化图形转换为规范形式，然后执行的规范形式比较。这一目标产生生成树，但生成树不是唯一的，所以你需要有一个规范的方法来创建它们。

In general, the basic idea is to simplify the graph into a canonical form, and then perform comparison of canonical forms. Spanning trees are generated with this objective, but spanning trees are not unique, so you need to have a canonical way to create them.

在有规范的形式，可以执行同构的比较（相对）很容易，但是这仅仅是开始，因为非同构图形可以有相同的生成树。 （例如，想想一个生成树T和一个除了边缘将其打造T'。这两个图不是同构的，但它们具有相同的生成树）。

After you have canonical forms, you can perform isomorphism comparison (relatively) easy, but that's just the start, since non-isomorphic graphs can have the same spanning tree. (e.g. think about a spanning tree T and a single addition of an edge to it to create T'. These two graphs are not isomorph, but they have the same spanning tree).

的其它技术包括比较描述符（节点的数目例如，边缘的数目），其可产生在一般的假阳性

Other techniques involve comparing descriptors (e.g. number of nodes, number of edges), which can produce false positive in general.

我建议你开始与有关图同构问题 wiki页面。我也有一书中提出：图论及其应用。这是一个大部头，但值得每一个页面。

I suggest you to start with the wiki page about the graph isomorphism problem. I also have a book to suggest: "Graph Theory and its applications". It's a tome, but worth every page.

由于从你必然的结果，给定曲线的顶点每一个可能的空间分布是一个同构。所以2同构的图具有相同的拓扑结构和它们，中底，在同一张图，从拓扑点。另一个问题是，例如，去寻找那些同构结构的享受特殊属性（例如，使用非交叉的边缘，如果存在的话），那取决于你想要的属性。

As from you corollary, every possible spatial distribution of a given graph's vertexes is an isomorph. So two isomorph graphs have the same topology and they are, in the end, the same graph, from the topological point of view. Another matter is, for example, to find those isomorph structures enjoying particular properties (e.g. with non crossing edges, if exists), and that depends on the properties you want.

这篇关于图同构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！