图同构算法

Question

可能的重复：
图同构

是否有任何众所周知的图同构启发法。如果有人知道，请让我知道任何好的且易于理解的图同构算法。

Answer 1

检查不具有病态统一结构的图之间的同构性的简单但有效的方法是选取节点不变量，计算所有节点的不变量值，然后对实际同构执行（深度优先）搜索仅每个配对节点具有相同的节点不变量值。节点不变量的想法是，它是一个对象（通常是数字或数字序列），以完全独立于图的表示的方式计算节点；即在选择表示形式时它是不变的。

例如，节点具有的邻居数量是不变的，但程序迭代节点邻居的顺序并不取决于表示（数据结构）。

通常，节点不变量是迭代计算的，例如这个简单的不变量 I[n]，其中 n 是节点，I[n] 是无符号 32 位整数：

for every node in graph:
  I[node] = count_neighbors(node)
for i = 0 .. N: # N is a constant, number of iterations
  for every node in graph:
    I'[node] = (I[node] << 13 | I[node] >> 19) ^ 0xff00ff00
    for every node' in neighbors(node):
      I'[node] += I[node']
  for every node in graph:
    I[node] = I'[node]

这些类型的不变量实际上以非均匀方式区分大多数节点图表，使搜索阶段在实践中变得更快。