Алгоритм определения изоморфности 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)
Вот как я начал свой алгоритм (простите мне отсутствие математической строгости) пожалуйста, помогите мне завершить / исправить!
- Если размер (число ребер, в данном случае количество 1s) A != размер B = > графы не изоморфны
- для каждой вершины A подсчитайте ее степень и найдите соответствующую вершину в B, которая имеет такую же степень и не была сопоставлена ранее. Если совпадения нет => графики не изоморфны.
Теперь, когда мы не можем быстро доказать, что A и B не изоморфны, каков следующий шаг?
Это было бы правильно попробовать все перестановки строки до тех пор, пока матчи Б? Правда, не уверен насчет этого...
3 ответов:
Это довольно сложная задача для решения. Об этом есть страница Википедии:
Согласно этой странице существует ряд частных случаев, которые были решены с эффективными полиномиальными временными решениями, но сложность оптимального решения все еще неизвестна.
Мой проект-Griso-at sf.net: http://sourceforge.net/projects/griso/ с таким описанием:
Griso-это утилита для тестирования изоморфизма графов, написанная на C++ и основанная на моем собственном algo.
Смотрите пример ввода/вывода Griso на этой странице: http://funkybee.narod.ru/graphs.htm
Ну, очень легко быстро сказать, что они не изоморфны, сделав следующее.
areIsomorphic(G1, G2): if(G1.num_verticies != G2.num_verticies) return False if(G1.num_total_edges != G2.num_total_edges) return False for each vertex v in G1: if( G2.find(v).edges != v.edges): return False; //Try and find a property in graph G1 that does not exist in G2. // Use a heuristic. ie- try and find nonmutually adjacenct sets.
Comments