Простой вариант в реализации - перебирайте перестановку. Вот у вас в ответе буквам сопоставляются числа. Зафиксируйте порядок букв (вершин в одном графе). Тогда вершины второго графа (числа в ответе) будут представлять собой перестановку. Перебирайте все перестановки. Потом проверяйте, что одна матрица смежности после перестановки станет равна второй. Буквально для всех
i, j
проверяйте, что
a[p[i]][p[j]] == b[i][j]
.
Перебор перестановок - известная
задача. Применяйте этот алгоритм в цикле к текущей перестановке (которая изначально p[i] == i), пока получается. Реализация этого алгоритма уже есть в
python.
Как только нашли перестановку, для которой матрицы совпали - выводите перестановку в ответ и вываливайтесь из перебора.
Чуть более сложный в реализации, но более быстрый - перестановки перебираются рекурсивной функцией с одного конца. При этом, по мере выбора нового элемента, сразу же производятся все проверки (вот, зафиксировали вы p[i] на i-ом уровне рекурсии, сразу же посмотрите, что для всех j
a[p[i]][p[j]]==b[i][j] выполняются).
Как соберете всю перестановку (дойдете до n-ого уровня рекурсии) - вы нашли ответ.
Если реализация выдает неправильный ответ, попробуйте вместо условия a[p[i]][p[j]]==b[i][j]
поменять на a[i][j]==b[p[i]][p[j]]
(Тут сложно понять, прямую или обратную перестановку вы хотите в ответе).