Полиноминальный алгоритм решения проблемы изоморфизма графов

[iaiaoee]

Добрый день,

я придумал алгоритм. на простых графах он работает, а сложных я не видел. прежде чем предоставить общественности мое творение я хотел бы его проверить на ваших примерах. может где есть список графов на которых тестят алгоритмы по изоморфизму?

-- 31.07.2018, 17:33 --

Может быть есть где специальное место куда скидывают все неправильные решения, или которые дают решения для специального вида графов, я там просто поищу и успокоюсь.

Потому что мое решение чет очень просто, а доказать его истинность математически я пока не готов.

[mihaild]

Вот например: https://www.lii.rwth-aachen.de/en/resea ... marks.html
Там есть несколько разных серий видов, разбитых на группы, в каждой группе несколько пар, графы из одной пары изоморфны, из разных - скорее всего нет.

[iaiaoee]

отбой,
мое решение годно только для планарных графов,
для графов вида шар из вершин где каждая вершина имеет связи с половиной всех вершин мое решение не работтает

[mihaild]

Если оно работает для всех планарных графов - это всё равно интересно. Полиномиальный алгоритм проверки изоморфизма планарных графов известен, но нетривиален.

[iaiaoee]

Ок, сейчас выложу решение

[iaiaoee]

проблема изоморфизма

есть 2 (стула, зачеркнуто) графа.

В общем случае они представлены матрицей смежности

0, 1, 1, 1, 0, 0,
1, 0, 1, 0, 1, 0,
1, 1, 0, 0, 0, 1,
1, 0, 0, 0, 1, 1,
0, 1, 0, 1, 0, 1,
0, 0, 1, 1, 1, 0,


или файлом в специальном формате, где указано количество вершин, количество ребер и перечислены связи между ребрами

p edge 16 76
e 1 3
e 1 4
e 1 6
e 1 8
e 1 9
...

по известным алгоритмам одно представление переходит в другое.

если в матрице смежности поменять местами 2 строки и 2 столбца с теми же индексами, то мы получим изоморфный граф.

задача состоит в том чтобы в первой матрице поменять строки и столбцы так чтоб она совпала со второй. если менять только первую матрицу а вторую не трогать то в общем случае это займет n факториал перестановок, что очень много.
сократим количество перебора.

преобразуем матрицу смежности в матрицу расстояний.

0, 1, 1, 1, 2, 2
1, 0, 1, 2, 1, 2
1, 1, 0, 2, 2, 1
1, 2, 2, 0, 1, 1
2, 1, 2, 1, 0, 1
2, 2, 1, 1, 1, 0

для каждой строки построим индекс, (это уже другой граф)
[0, 1, 2, 2, 2, 3, 3, 3, 3, '0', '|1-1-3-4'],
[1, 0, 1, 1, 1, 2, 2, 2, 2, '5', '|1-4-4-0'],
[2, 1, 0, 1, 2, 1, 2, 1, 1, '2', '|1-5-3-0'],
[2, 1, 1, 0, 2, 2, 1, 2, 2, '3', '|1-3-5-0'],
[2, 1, 2, 2, 0, 3, 3, 3, 3, '4', '|1-1-3-4'],
[3, 2, 1, 2, 3, 0, 3, 2, 2, '1', '|1-1-4-3'],
[3, 2, 2, 1, 3, 3, 0, 3, 3, '6', '|1-1-2-5'],
[3, 2, 1, 2, 3, 2, 3, 0, 2, '7', '|1-1-4-3'],
[3, 2, 1, 2, 3, 2, 3, 2, 0, '8', '|1-1-4-3']
здесь мы видим матрицу расстояний, передпоследний столбец - номер строки, чтобы знать какую вершину какой сопоставлять, последний столбец - индекс, каждая позиция это количество вершин которые можно достичь за указаное количество шагов.

если индекс уникален, то он, однозначно определяет вершину.

меняем строки и столбцы, чтоб уникальные вершины были сверху, потом перестраиваем индекс.

индекс состоит из 2-х частей, фиксированная и плавающая.

то что до слеша фиксированная, что после слеша, плавающая.

когда мы определили первые n строк, то в каждой строке первые n растояний не будут меняться никогда

и мы получаем следующий индекс
[0, 1, 2, 2, 3, 3, 3, 3, 3, '6', '|1-1-2-5'],
[1, 0, 1, 1, 2, 2, 2, 2, 2, '3', '|1-3-5-0'],
[2, 1, 0, 1, 1, 2, 1, 2, 2, '5', '|1-4-4-0'],
[2, 1, 1, 0, 2, 1, 2, 1, 1, '2', '|1-5-3-0'],
[3, 2, 1, 2, 0, 3, 2, 3, 3, '4', '3-2-1-2|1-0-1-3'],
[3, 2, 2, 1, 3, 0, 3, 2, 2, '1', '3-2-2-1|1-0-2-2'],
[3, 2, 1, 2, 2, 3, 0, 3, 3, '0', '3-2-1-2|1-0-1-3'],
[3, 2, 2, 1, 3, 2, 3, 0, 2, '7', '3-2-2-1|1-0-2-2'],
[3, 2, 2, 1, 3, 2, 3, 2, 0, '8', '3-2-2-1|1-0-2-2']

первые 4 вершины, это уникальные, для остальных построен индекс, который более однозначно определяет вершины

после сортировки у нас вершины делятся на 2 группы, в одной 2 вершины в друго 3.

Для планарных графов это вершины которые взаимо заменяемы(утверждение спорно, нужно или доказать или опровергнуть)

после каждой итерации смотрим совпадают ли индексы левой и правой матрицы, если совпадают, можно сортировать и переходить к следующей итерации, если не совпадают, то изоморфизм невозможен(утверждение верно для планарных графов, математического доказательства нет, утверждение никто в общем случае не проверял)

вначале мы имеем матрицы каждая из которых состоит из 2-х частей, неизменяемая и возможная, с каждым шагом неизменяемая часть увеличевается, возможная уменьшается(та что в индексе после вертекальной черты)

я назвал свой алгоритм метод зонной плавки https://ru.wikipedia.org/wiki/Зонная_плавка Метод является разновидностью направленной кристаллизации, от которой отличается тем, что в каждый момент времени расплавленной является некоторая небольшая часть образца.

код лежитздесь

zone_melting.py - основной файл который находит или не находит решение, на вход пеердаются 2 матрицы смежности, в ответ решение или невозможность решения

также написаны 2 обертки
iso_solver_graphml.py
iso_solver.py

первая для графов постороеных в http://graphonline.ru (граф->экспорторовать грф)

нарисуйте 2 предположительно изоморфных графа,
запустите
python iso_solver_graphml.py -i palm2.graphml
в ответ увидете
matrix size:9 iteration:6

и файл, out.graphml, который импортировав в http://graphonline.ru можно увидеть над вершинами индексы которые можно сопоставить и убедиться в изоморфности

второй файл для файлов в формате

p edge 16 76
e 1 3
e 1 4
e 1 6
e 1 8
e 1 9
...
python iso_solver.py -i1 cfi-rigid-t2-0016-04-1 -i2 cfi-rigid-t2-0016-04-2

для каждого файла есть справка

python iso_solver.py -h
usage: iso_solver.py [-h] -i1 I1 -i2 I2 [-o O]

optional arguments:
-h, --help show this help message and exit
-i1 I1 first file
-i2 I2 second file
-o O output file

[mihaild]

iaiaoee в сообщении #1331481 писал(а):

для каждой строки построим индекс

iaiaoee в сообщении #1331481 писал(а):

последний столбец - индекс

Так индекс - это матрица "до скольки вершин есть путь такой длины" (и "ровно такой" или "не более такой"?), или один столбец?

iaiaoee в сообщении #1331481 писал(а):

то что до слеша фиксированная, что после слеша, плавающая.

А где слеш-то?

Вообще пока что выглядит как какая-то эвристика без оценок эффективности.

[grizzly]

mihaild в сообщении #1332167 писал(а):

А где слеш-то?

Подразумевалась прямая вертикальная черта внутри одиночных кавычек.

[iaiaoee]

каждая строка матрицы расстояний описывает вершину.

пока ни одной вершины не известно то меняя местами строки и столбцы мы можем выстроить n! сочетание расстояний до других вершин, единственная стабильная характеристика каждой строки(вершины) это количество вершин с минимальным расстоянием |1-1-2-5

до одной вершины расстояние 1
до 1 вершины расстояние 1
до 2-х вершин расстояние 2
до 5 вершин расстояние 3

как ни меняй строки местами расстояние до вершин не изменится

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

Дальше как не переставляй остальные неизвестные строки, первые n ячеек останутся неизменными, потомучто первые n вершин определены, получаем составной ключ 3-2-2-1|1-0-2-2
первая часть расстояние до известных вершин, вторая расстояние до неизвесных

в каждый момент времени если мы имеем 2 и более одинаковых ключа, то эти вершины могут быть взаимозаменяемы.

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

[MerkulovaLE]

Добавлю усложнение алгоритма,
которое работает и на сильно регулярных графах

Возьмем два графа $G_1$ и $G_2$.
Количество вершин в обоих графах - $n$
Их матрицы смежности $A_1$ и $A_2$.
Сделаем из них две трехмерные матрицы $B_1[i,j,k]$ и $B_2[i,j,k]$
$B_1[i,j,k]=A_1[i,j]$; $B_2[i,j,k]=A_2[i,j]$

Теперь обозначим вершины графов:
Если $ i=j=k$, то $B_1[i,j,k]=2$, $B_2[i,j,k]=2$.
-------------------------------------------------------------
Далее построим две трехмерные матрицы $C_1$ и $C_2$, такие, что
$ C_1[i_1,j_1,k_1] = C_2[i_2,j_2,k_2]$ тогда и только тогда, когда
$ B_1[i_1,j_1,k_1] = B_2[i_2,j_2,k_2]$ и совпадают наборы триад в этих
матрицах:

В матрице $C_1$ это n триад:
$C_1[1,j_1,k_1];C_1[i_1,1,k_1];C_1[i_1,j_1,1]$
$C_1[2,j_1,k_1];C_1[i_1,2,k_1];C_1[i_1,j_1,2]$
$C_1[3,j_1,k_1];C_1[i_1,3,k_1];C_1[i_1,j_1,3]$
$\dots $
$C_1[n,j_1,k_1];C_1[i_1,n,k_1];C_1[i_1,j_1,n]$

В матрице C_2 это n триад:
$C_2[1,j_2,k_2];C_2[i_2,1,k_2];C_2[i_2,j_2,1]$
$C_2[2,j_2,k_2];C_2[i_2,2,k_2];C_2[i_2,j_2,2]$
$C_2[3,j_2,k_2];C_2[i_2,3,k_2];C_2[i_2,j_2,3]$
$\dots $
$C_2[n,j_2,k_2];C_2[i_2,n,k_2];C_2[i_2,j_2,n]$

В противном случае $ C_1[i_1,j_1,k_1]$ не равно $C_2[i_2,j_2,k_2]$

Если в матрицах $C_1$ и $C_2$ элементы совпадают,
то графы $G_1$ и $G_2$ изоморфны.
-------------------------------------------------------------------
сделаем процедуру, которая будет сравнивать элементы матриц $B_1$ и $B_2$
внутри самих матриц и между матрицами.

Значения матриц $D_1old$ и $D_2old$ первоначально совпадают с $B_1$ и $B_2$.

Если значения элементов $D_1old[i_1,j_1,k_1]$ и $D_2old[i_2,j_2,k_2] $
и множества $n$ триад матриц$ D_1old $ и $D_2old$ совпадают,
то в новых вариантах трехмерных матриц $D_1new$ и $D_2new$
эти элементы будут пронумерованы одинаково,
если нет - то неодинаково.

Если количество одинаковых элементов в двух
матрицах окажется неодинаковым,
то графы неизоморфны.

Процедура запускается с матрицами $D_1old$ и $D_2old$,
переписывая новые варианты $D_1new$ и $D_2new$, в конце
процедуры $D_1old$ и $D_2old$ приравниваются к $D_1new$ и $D_2new$,
а $D_1new$ и $D_2new$ обнуляются

Процедура продолжается, пока не перестанет выдавать новые значения элементов матриц,
$D_1new$ и $D_2new$, отличные от элементов старых матриц,
либо обнаружится несовпадение числа одинаковых элементов в новых матрицах.

Если все элементы $D_1new$ совпадают с элементами $D_2new$,
и новых различий нет,то графы изоморфны.

[MerkulovaLE]

Полиномиальный алгоритм распознавания изоморфизма графов.

Пусть $ G_1 $ и $G_2$ - невзвешенные неориентированные графы
Количество вершин в каждом графе $n$.
Их матрицы смежности $A_1$ и $A_2$.

Под перестановкой будем иметь в виду функцию
$T[i]$, которая каждому числу $i $ от $1$ до $n$ ставит в соответствие
число $T[i]$ от $1$ до $n$. $T[i]=T[j]$ тогда и только тогда, когда $i=j$.

Модифицируем матрицы смежности в матрицы $B_1$ и $B_2$
$B_1[i,j] = A_1[i,j]$ при разных $i$ и $j$
$B_1[i,i] =$ неповторяющиеся числа от $3$ до $n+2$

$B_2[i,j] = A_2[i,j]$ при разных $i$ и $j$
$B_2[i,i] =$ неповторяющиеся числа от $3$ до $n+2$

Введем функцию $F_1(i_1,j_1,i_2,j_2)$

$F_1(i_1,j_1,i_2,j_2) = $истина, тогда и только тогда,
когда $B_1[i_1,j_1] = B_2[i_2,j_2]$
и существуют
$2$ перестановки чисел от $1 $до $n$, $T_1$ и $T_2$, такие,
что, $F_1(k,j_1,T_1[k],j_2) =$ истина
и $ F_1(i_1,k,i_2,T_2[k]) =$ истина
при любом $k$ от $1$ до $n$.

Лемма 1.1

Если существуют такие $i_1,i_2,j_1,j_2,$
что $F_1(i_1,j_1,i_2,j_2) = $ истина, то графы
$G_1$ и $G_2$ изоморфны. Маркированные вершины
графа $G_1$ переходят в одинаково маркированные
вершины графа $G_2$.

Доказательство леммы 1.1:

В матрицах $B_1$ и $B_2$ вершинам графов
поставлен в соответствие уникальный номер от
$3$ до $n+2$. Если $F_1[i_1,j_1,i_2,j_2] = $ истина,
то и $F_1(i_1,i_1,i_2,i_2) =$ истина,
и $B_1[i_1,i_1] = B_2[i_2,i_2]$.
Аналогично $B_1[j_1,j_1] = B_2[j_2,j_2]$.

Также $F_1(i_1,1,i_2,T_2[1]) = $истина
$F_1(i_1,2,i_2,T_2[2]) = $истина
...
$ F_1(i,1,n,i_2,T_2[n]) =$ истина (формула 1.1)

Согласно описанию F_1 из формулы 1.1 следует
$ F_1(1,1,T_1[1],T_2[1]) =$ истина
$F_1(2,1,T_1[2],T_2[1]) =$ истина
...
$ F_1(n,1,T_1[n],T_2[1]) =$ истина

$F_1(1,2,T_1[1],T_2[2]) =$ истина
$F_1(2,2,T_1[2],T_2[2]) =$ истина
...
$F_1(n,2,T_1[n],T_2[2]) = $ истина

и.т.д.

Между одинаково маркированными вершинами - одинаковые рёбра.

Графы изоморфны.
Лемма 1.1 доказана.

Если графы изоморфны, то для любой нумерации вершин графа $G_1$
найдется нумерация вершин графа $G_2$, при которых $F_1 = $ истина.

Рассмотрим $4-$мерные матрицы $C_1$ и $C_2$.

$C_1[i_1,i_1,i_1,i_1]=4 $
$C_1[i_1,i_2,i_2,i_2]=3$ при неравных$ i_1$ и $i_2$
$C_1[i_1,i_2,i_3,i_4]=A_1[i_3,i_4]$ в остальных случаях

$С_2[i_1,i_1,i_1,i_1]=4 $
$C_2[i_1,i_2,i_2,i_2]=3$ при неравных$ i_1$ и$ i_2$
$C_2[i_1,i_2,i_3,i_4]=A_2[i_3,i_4]$ в остальных случаях.

Введем функцию $F_2(i_1,i_2,i_3,i_4,j_1,j_2,j_3,j_4)$
$F_2(i_1,i_2,i_3,i_4,j_1,j_2,j_3,j_4) =$ истина,
тогда и только тогда, когда
$C_1[i_1,i_2,i_3,i_4] = C_2[j_1,j_2,j_3,j_4]$
и существуют перестановки $T_3,T_4,T_5$ и $T_6$
$F_2(i_1,i_2,i_3,k,j_1,j_2,j_3,T_3[k]) =$ истина при $k$ от $1$ до $n$
$F_2(i_1,i_2,k,i_4,j_1,j_2,T_4[k],j_4) =$ истина при $k$ от $1$ до $n$
$F_2(i_1,k,i_3,i_4,j_1,T_5[k],j_3,j_4) =$ истина при $k$ от $1$ до $n$
$F_2(k,i_2,i_3,i_4,T_6[k],j_2,j_3,j_4) =$ истина при $k$ от $1$ до $n$

Лемма 2.1

Если существуют такие $i_1, i_2, i_3, i_4, j_1, j_2, j_3,j_4$, что
$F_2(i_1,i_2,i_3,i_4,j_1,j_2,j_3,j_4) =$ истина, то графы $G_1 $и $G_2$
изоморфны.

Доказательство леммы 2.1:
Все $n$ $3$-мерных подматриц
$C_1[1,i_2,i_3,i_4]$ и $C_2[1,j_2,j_3,j_4]$
$C_1[2,i_2,i_3,i_4]$ и $C_2[2,j_2,j_3,j_4]$
...
$C_1[n,i_2,i_3,i_4] $ и $C_2[n,j_2,j_3,j_4]$
отмечены четвёркой на элементах
$C_1(i_1,i_1,i_1,i_1)$ и $C_2(j_1,j_1,j_1,j_1)$.
и тройками на остальных $n-1$ вершинах.
в $С_1[i_1,i_2,i_3,i_4]$ при неравных$ i_1$ и $i_2$ вершина $i_1$ маркирована
отличным от остальных коэффициентом,
так как $F_2(i_1,k,i_3,i_4,j_1,T_5[k],j_3,j_4) =$ истина при $k$ от $1$ до $n$
по определению функции $F_2$, и только у вершины $i_1$ в подматрице есть
в одной из тетрад четвёрка
вершина$ i_2 $маркирована тройкой.
И к этой $2$-мерной матрице поэлементно
применяется $2$-мерная матрица $C_1[i_2,i_2,i_3,i_4]$,
которая хранит информацию о матрицах$ С_1[k,i_2,i_3,i_4]$
$ k $ от $1$ до $ n$

$ 1 $ - иерархия вершин, к которой применяется $ 2 $
$ 2 $ - иерархия вершин, которая применаяется к $ 1 $

$ \begin{tabular}{cc|c} 1 & 2 & $final$ \\ \hline $4$ & &$4$ \\ $3$ & $4$ & $5$\\ & $3$ & $3$ \end{tabular} $

$ \begin{tabular}{cc|c} 1 & 2 & $final$ \\ \hline $4$ & &$4$ \\ $5$ & $4$ & $6$\\ $3$ & $5$ & $7$\\ & $3$ & $3$ \end{tabular} $

$ \begin{tabular}{cc|c} 1 & 2 & $final$ \\ \hline $4$ & &$4$ \\ $6$ & $4$ & $8$\\ $7$ & $6$ & $9$\\ $3$ & $7$ & $10$\\ & $3$ & $3$ \end{tabular} $


и так далее до $n$ вершин в столбце.
При этом проходятся все возможные варианты нумерации вершин графа.
Каждая вершина нумерует отдельным маркером смежные вершины
по вертикали в матрице смежности, и по горизонтали учитываются
смежные с помеченной вершиной вершины.

Лемма 2.1 доказана

Теперь рассмотрим две трёхмерные матрицы $D_1$ и $D_2$

$D_1[i_1,i_1,i_1] = 3$
$D_1[i_1,i_2,i_3] = A_1[i_2,i_3]$ при неравных$ i_2$ и $i_3$
$D_1[i_1,i_2,i_3] = 0$ во всех остальных случаях

$D_2[j_1,j_1,j_1] = 3$
$D_2[j_1,j_2,j_3] = A_2[j_2,j_3]$ при неравных j_2 и j_3
$D_2[j_1,j_2,j_3] = 0$ во всех остальных случаях

Введем функцию $F_3(i_1,i_2,i_3,j_1,j_2,j_3)$

$F_3(i_1,i_2,i_3,j_1,j_2,j_3) =$ истина тогда, и только тогда,
когда

$D_1[i_1,i_2,i_3]=D_2[j_1,j_2,j_3] $
и существует перестановка $T_7$, такая, что

$F_3(i_1,i_2,k,j_1,j_2,T_7[k]) = $ истина при $k$ от $1$ до $n$
$F_3(i_1,k,i_3,j_1,T_7[k],j_3) =$ истина при $k$ от $1$ до $n$
$F_3(k,i_2,i_3,T_7[k],j_2,j_3) =$ истина при $k$ от $1$ до $n$

Лемма 2.2 Если $F_3(i_1,i_2,i_3,j_1,j_2,j_3) =$ истина
при некоторых $i_1, i_2, i_3, j_1, j_2, j_3,$
то графы $G_1$ и $G_2$ изоморфны.

Доказательство леммы 2.2

Рассматривается $F_3(i_1,i_2,k,j_1,j_2,T_7[k])$
по вертикали
и вместе с тем, $F_3 $от той же перестановки $T_7$
$F_3(i_1,k,i_3,j_1,T_7[k],j_3)$ по горизонтали.

Это аналогично $F_2 $на трёхмерной матрице с
маркированными элементами $[i_1,i_1,i_1]$

Остается только одна возможность маркировки вершин
(не $3$ и $4$, а только $3$).

Так как истинность $F_2$ на каких-либо элементах
ведет к изоморфизму графов, то и истинность
$F_3$ на каких-либо элементах ведет к
изоморфизму графов.

Истинность $ F_3(i_1,i_1,i_1,j_1,j_1,j_1)$
означает подобие вершин $i_1$ и $j_1$.

Лемма 2.2 доказана.

Алгоритм на двух графах.

Строятся две трёхмерные матрицы $D_1$ и $D_2$.

$D_1[i_1,i_1,i_1] = 3$
$D_1[i_1,i_2,i_3] = A_1[i_2,i_3] $при неравных $i_2$ и $i_3$
$D_1[i_1,i_2,i_3] = 0 $во всех остальных случаях

$D_2[j_1,j_1,j_1] = 3$
$D_2[j_1,j_2,j_3] = A_2[j_2,j_3]$ при неравных $i_2$ и $i_3$
$D_2[j_1,j_2,j_3] = 0$ во всех остальных случаях

шаг алгоритма:

каждый элемент матрицы $D_1$ сравнивается с остальными элементами
матрицы $D_1$ и всеми элементами матрицы $D_2$.
$D_1[i_1,i_2,i_3]$;
$D_1[l_1,l_2,l_3]$;
$D_2[j_1,j_2,j_3]$;

также сравниваются наборы триад

$D_1[k,i_2,i_3];D_1[i_1,k,i_3];D_1[i_1,i_2,k]$ для всех $k$ от $1$ до $n$
$D_1[k,l_2,l_3];D_1[l_1,k,l_3];D_1[l_1,l_2,k]$ для всех k от $1$ до$ n$
$D_2[k,j_2,j_3];D_1[j_1,k,j_3];D_1[j_1,j_2,k]$ для всех $k$ от $1$ до $n$

Если элементы матриц и наборы триад совпадают, то элементы новых матриц
$H_1[i_1,i_2,i_3]$ и $H_2[j_1,j_2,j_3]$ одинаковые, иначе разные.

В конце шага матрицы $H_1$ и $H_2$ переносятся в $D_1$ и $D_2$
Сами $H_1$ и $H_2$ после этого обнуляются.

шаг алгоритма проводится до того, как более не выявится новых различий,
либо между графами выявятся различия, заключающиеся в разном количестве
одинаковых элементов матриц $H_1$ и $H_2$. Тогда графы неизоморфны.

шагов алгоритма не может быть более $2\cdot n^3$.
(количество элементов в матрицах)
Шаг алгоритма требует времени порядка $n^8$.Сравнение $n^3$ и $2 \cdot n^3$ элементов из
$n$ триад с $n$ триадами.

Памяти требуется порядка $n^3$

Алгоритм полиномиален.

[whitefox]

MerkulovaLE
Поздравляю, вы изобрели процедуру refinement из алгоритма программы nauty. Хотя вы и выполняете её весьма своеобразно, это именно она. Смотрите Brendan D. McKay Practical graph isomorphism.

Во многих случаях эта процедура действительно даёт орбиты группы автоморфизмов графа, но далеко не всегда. В алгоритме nauty она выполняется на предварительном шаге, и только потом начинается сам поиск. Вам осталось придумать свою версию заключительного шага. В программе nauty он не полиномиальный, дерзайте — может у вас получится лучше чем у McKay-я.

[MerkulovaLE]

whitefox,

Это не совсем refinement, алгоритм учитывает еще и помеченные пары графов

Для заключительного шага нахождения
конкретного изоморфизма графа (да, задачка) надо запустить ту
же процедуру расщепления, но с отличными от других коэффициентами
на подобных вершинах. Возможно, стоит вернуться к четырехмерной
матрице, там изоморфизм графов с весами на вершинах гарантированно
работает

Итак,

Рассмотрим $4-$мерные матрицы $C_1$ и $C_2$.

$C_1[i_1,i_1,i_1,i_1]=4$
$C_1[i_1,i_2,i_2,i_2]=3$ при неравных$ i_1$ и $i_2$
$C_1[i_1,i_2,i_3,i_4]=A_1[i_3,i_4]$ в остальных случаях

$С_2[i_1,i_1,i_1,i_1]=4$
$C_2[i_1,i_2,i_2,i_2]=3$ при неравных$ i_1$ и$ i_2$
$C_2[i_1,i_2,i_3,i_4]=A_2[i_3,i_4]$ в остальных случаях.

Введем функцию $F_2(i_1,i_2,i_3,i_4,j_1,j_2,j_3,j_4)$
$F_2(i_1,i_2,i_3,i_4,j_1,j_2,j_3,j_4) =$ истина,
тогда и только тогда, когда
$C_1[i_1,i_2,i_3,i_4] = C_2[j_1,j_2,j_3,j_4]$
и существуют перестановка $T_3
$F_2(i_1,i_2,i_3,k,j_1,j_2,j_3,T_3[k]) =$ истина при $k$ от $1$ до $n$
$F_2(i_1,i_2,k,i_4,j_1,j_2,T_3[k],j_4) =$ истина при $k$ от $1$ до $n$
$F_2(i_1,k,i_3,i_4,j_1,T_3[k],j_3,j_4) =$ истина при $k$ от $1$ до $n$
$F_2(k,i_2,i_3,i_4,T_3[k],j_2,j_3,j_4) =$ истина при $k$ от $1$ до $n$

При нетривиальном автоморфизме графа подобные вершины помечаются
коэффициентом $n^4+1$ и расщепление запускается,
пока для каждой вершины первого графа не останется в подобии только
одна вершина второго.

В четырехмерных матрицах $C_1$ и $C_2$ запускается расщепление
коэффициентов до тех пор, пока не будет новых коэффициентов, либо
установится неизоморфность графов при отличии количества одинаковых элементов

В любом случае, whitefox, спасибо за внимание и ссылку.

[MerkulovaLE]

Уважаемые коллеги!

Два варианта алгоритма распознавания
изоморфизма графов

ссылка в облаке mail
https://cloud.mail.ru/public/4tYt/3CUHnrbH1

$3d $ лучше и быстрее, но не удается
корректно сделать переход от $4d$.

Оба варианта полиномиальные, но требуют
много ресурсов, однако хорошо
распараллеливаются.