有图同构的算法或启发式算法吗？
推论：一个图可以用不同的图形表示。
找到不同图形的最佳方法是什么？
最佳答案
这真是个麻烦。
一般来说，基本思想是将图简化为规范形式，然后对规范形式进行比较。生成生成树的目的是这样的，但是生成树并不是唯一的，所以您需要有一个规范的方法来创建它们。
在有了规范形式之后，可以相对容易地执行同构比较，但这只是开始，因为非同构图可以有相同的生成树。（例如，考虑一个生成树t，并在它上添加一个边来创建t’。这两个图不是同构的，但它们有相同的生成树）。
其他技术包括比较描述符（例如节点数、边数），这通常会产生假阳性。
我建议你从wiki页面开始。我还有一本书要推荐：graph isomorphism problem。这是一本书，但每一页都值得。
从你的推论来看，给定图的顶点的每个可能的空间分布都是同构的。所以两个同构图具有相同的拓扑，从拓扑的角度来看，它们最终是相同的图。另一个问题是，例如，找到那些具有特殊性质的同构结构（例如，如果存在非交叉边），这取决于所需的属性。
关于algorithm - 图同构，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/1695173/