Алгоритм определения изоморфности 2 графов - PullRequest
Новая
       94

Алгоритм определения изоморфности 2 графов

8 голосов
/ 06 октября 2010

Отказ от ответственности: я новичок в теории графов, и я не уверен, относится ли это к 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. Если размер (количество ребер, в данном случае количество 1 с) A! = размер B => графы не изоморфны
  2. Для каждой вершины A посчитайте ее степень и найдите соответствующую вершину в B, которая имеет такую ​​же степень , а не было сопоставлено ранее.Если совпадений нет => графы не изоморфны.
  3. Теперь, когда мы не можем быстро доказать, что A и B не изоморфны, каков следующий шаг?Было бы правильно попробовать каждую перестановку строк в A, пока A не совпадет с B?На самом деле не уверен насчет этого ...

Ответы [ 3 ]

7 голосов
/ 07 октября 2010

Это довольно сложная проблема для решения.Об этом есть страница в Википедии:

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

4 голосов
/ 12 апреля 2011

Мой проект - Griso - на sf.net: http://sourceforge.net/projects/griso/ с этим описанием:
Griso - это утилита для тестирования изоморфизма графов, написанная на C ++ и основанная на моем собственном алгоритме.
См. Пример ввода / вывода Griso на этой странице: http://funkybee.narod.ru/graphs.htm

0 голосов
/ 10 декабря 2014

Ну, очень легко быстро сказать, что они НЕ изоморфны, выполнив следующее. 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.

...