Как найти изоморфизм графов?

Question

[Nikolay L]

a, b, c, d, g, h, i, j = range(8)

#    a, b, c, d, g, h, i, j
G = [
    [0, 0, 0, 0, 1, 1, 1, 0],  # a
    [0, 0, 0, 0, 1, 1, 0, 1],  # b
    [0, 0, 0, 0, 1, 0, 1, 1],  # c
    [0, 0, 0, 0, 0, 1, 1, 1],  # d
    [1, 1, 1, 0, 0, 0, 0, 0],  # g
    [1, 1, 0, 1, 0, 0, 0, 0],  # h
    [1, 0, 1, 1, 0, 0, 0, 0],  # i
    [0, 1, 1, 1, 0, 0, 0, 0]   # j
]

#    1, 2, 3, 4, 5, 6, 7, 8
H = [
    [0, 1, 0, 1, 1, 0, 0, 0],  # 1
    [1, 0, 1, 0, 0, 1, 0, 0],  # 2
    [0, 1, 0, 1, 0, 0, 1, 0],  # 3
    [1, 0, 1, 0, 0, 0, 0, 1],  # 4
    [1, 0, 0, 0, 0, 1, 0, 1],  # 5
    [0, 1, 0, 0, 1, 0, 1, 0],  # 6
    [0, 0, 1, 0, 0, 1, 0, 1],  # 7
    [0, 0, 0, 1, 1, 0, 1, 0]   # 8
]

Чтобы определить изоморфизм, нужно путём перестановки строк и столбцов матрицы смежности графа G получить получить матрицу смежности графа H. (???)
Как дойти до ответа вида:

?

Answer 1

[Wataru]

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

Перебор перестановок - известная задача. Применяйте этот алгоритм в цикле к текущей перестановке (которая изначально p[i] == i), пока получается. Реализация этого алгоритма уже есть в python.

Как только нашли перестановку, для которой матрицы совпали - выводите перестановку в ответ и вываливайтесь из перебора.

Чуть более сложный в реализации, но более быстрый - перестановки перебираются рекурсивной функцией с одного конца. При этом, по мере выбора нового элемента, сразу же производятся все проверки (вот, зафиксировали вы p[i] на i-ом уровне рекурсии, сразу же посмотрите, что для всех ja[p[i]][p[j]]==b[i][j] выполняются).

Как соберете всю перестановку (дойдете до n-ого уровня рекурсии) - вы нашли ответ.

Если реализация выдает неправильный ответ, попробуйте вместо условия a[p[i]][p[j]]==b[i][j] поменять на a[i][j]==b[p[i]][p[j]] (Тут сложно понять, прямую или обратную перестановку вы хотите в ответе).