Алгоритм изоморфизма графов

Простой, но эффективный способ проверки изоморфизма между графами, которые не имеют патологически однородной структуры, состоит в том, чтобы выбрать инвариант узла, вычислить значение инварианта для всех узлов, а затем выполнить поиск (сначала в глубину) фактического изоморфизма. только каждое соединение узлов, которые имеют одинаковое значение для инварианта узла. Идея инварианта узла состоит в том, что это объект (обычно число или последовательность чисел), который вычисляется для узлов таким образом, который полностью не зависит от представления графа; т. е. инвариантен относительно выбора формы представления.

Например, количество соседей узла является инвариантом, но порядок, в котором ваша программа перебирает соседей узла, не зависит от представления (структур данных).

Обычно инварианты узла вычисляются итеративно, например. этот простой инвариант 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]

Эти типы инвариантов на практике отличают большинство узлов друг от друга в неоднородных графах, что на практике ускоряет этап поиска.