Алгоритм определения изоморфности 2 графов
Отказ от ответственности: я новичок в теории графов, и я не уверен, относится ли это к SO, Math SE и т. Д.
Учитывая 2 матрицы смежности A и B, как я могу определить, являются ли A и B изоморфными.
Например, A и B, которые не являются изоморфными, и C и D, которые являются изоморфными.
A = [ 0 1 0 0 1 1 B = [ 0 1 1 0 0 0
1 0 1 0 0 1 1 0 1 1 0 0
0 1 0 1 0 0 1 1 0 1 1 0
0 0 1 0 1 0 0 1 1 0 0 1
1 0 0 1 0 1 0 0 1 0 0 1
1 1 0 0 1 0 ] 0 0 0 1 1 0 ]
C = [ 0 1 0 1 0 1 D = [ 0 1 0 1 1 0
1 0 1 0 0 1 1 0 1 0 1 0
0 1 0 1 1 0 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 0 1
0 0 1 1 0 1 1 1 0 0 0 1
1 1 0 0 1 0 ] 0 0 1 1 1 0 ]
(sorry for this ugly notation, I'm not quite sure how to draw matrices on SO)
Вот как я начал свой алгоритм (простите за отсутствие математической строгости), пожалуйста, помогите мне завершить / исправить!
Если размер (количество ребер, в данном случае количество 1 с) A! = Размер B => графы не изоморфныДля каждой вершины A посчитайте ее степень и найдите совпадающую вершину в B, которая имеет такую же степеньа также не было найдено ранее. Если совпадений нет =>, графы не изоморфны.Теперь, когда мы не можем быстро доказать, что A и B не изоморфны, каков следующий шаг? Было бы правильно попробовать каждую перестановку строк в A, пока A не совпадет с B? На самом деле не уверен насчет этого ...