Какие существуют алгоритмы проверки изоморфности 2х графов?

[BlackSem]

Интересует как описание, так и может быть какие то исхоники.
Спасибо

[MrD]

Никто не поможет. Только в лоб перебирать N! способов обозначить вершины.

[незваный гость]

Ну уж так уж в лоб.

Я бы начал с инвариантов, в попытке доказать неизоморфность. Если граф ориентированный - тем лучше. Первые инварианты которые приходят в голову -- количество вершин и количество дуг. Дальше -- сортируем вершины по количеству исходящих и входящих дуг. Пары должны совпасть для обоих графов.

Следующий шаг -- вычисляем матрицу кратчайших расстояний (за кубическое время). Опять же, наборы строк должны совпасть.

Ну а если ничего не помогло -- последние две операции построили для нас (возможно большие) классы кандидатов на эквивалентности.

Теперь мы можем повторить подсчет дуг, но уже считая, в какой или из какого класса эквивалентности они идут. Опять-таки сигнатуры должны совпасть. А количество классов - увеличиться.

При удаче количество классов на данный момент станет равно количеству вершин. А коли нет -- тут уж придется делать ограниченный перебор.

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

P.S. Если допускаются кратные дуги, тоже не проблема -- объединяем их в одну, и приписываем новой объединенной дуге вес. Тогда сигнатуры должны включать еще и веса дуг, а расчет кратчайшего расстояния -- функцию расстояния от веса дуги. При этом, перечитывая с разными функциями, получаем дополнительную проверку...

P.P.S. При большом количестве дуг $> \frac{n(n-1)}{4}$ может быть проще доказывать изоморфность дополнения...

[V.V.]

BlackSem писал(а):

Интересует как описание, так и может быть какие то исхоники.
Спасибо

Поищите в инете!
Вроде, какие-то сибиряки анонсировали полиномиальный алгоритм.

[PAV]

http://lib.mexmat.ru/books/528

стр. 396-401

[незваный гость]

Часть упомянутого выше алгоритма (на Python):

class Node:
  def __init__(self, no):
    self.no = no
    self.color = None
    self.edges = []

  def connections(self):
    d = {}
    for e in self.edges:
      if e.color in d:
        d[e.color] += 1
      else:
        d[e.color] = 1
    dlist = d.items()
    dlist.sort()
    return (self.color, tuple(dlist))

class Graph:
  def __init__(self, nodeCount):
    self.nodeCount = nodeCount
    self.nodes = [Node(ix) for ix in range(nodeCount)]
    self.edgeCount = 0

  def addEdge(self, a, b):
    self.nodes[a].edges.append(self.nodes[b])
    self.nodes[b].edges.append(self.nodes[a])
    self.edgeCount += 1

  def addEdges(self, edgeList):
    for a, b in edgeList:
      self.addEdge(a, b)

  def _createHistogram(self):
    d = {}
    for n in self.nodes:
      k = n.connections()
      if k in d:
        d[k].append(n)
      else:
        d[k] = [n]
    return d

  def _wipe(self, color):
    for n in self.nodes:
      n.color = color

  def quickCheck(self, other):
    if self.nodeCount != other.nodeCount:
      return False
    if self.edgeCount != other.edgeCount:
      return False
    if self.nodeCount  <= 1:
      return True

    colors = 0
    colorCounters = {0: self.nodeCount}
    self._wipe(colors); other._wipe(colors)
    painted = True
    while painted:
      painted = False
      sHistogram = self._createHistogram(); oHistogram = other._createHistogram()
      for k in sHistogram:
        sNodes = sHistogram[k]; oNodes = oHistogram[k]
        if len(sNodes) != len(oNodes):
          return False
        if len(sNodes) != colorCounters[k[0]]:
          colors += 1
          colorCounters[colors] = len(sNodes)
          colorCounters[k[0]] -= len(sNodes)
          for n in sNodes:
            n.color = colors
          for n in oNodes:
            n.color = colors
          painted = True
    return True


if __name__ == "__main__":
  g1 = Graph(7)
  g1.addEdges([(0,1), (1,2), (2,3), (3,4), (4,5), (5,0), (5,1), (3,6)])

  g2 = Graph(7)
  g2.addEdges([(0,1), (1,2), (2,3), (3,4), (4,5), (5,0), (5,1), (4,6)])

  print "expected False:", g1.quickCheck(g2)
  print "expected True:", g1.quickCheck(g1)

В целом "color" -- это абстрактный цвет узла. Если графы изоморфны, то изоморфны и раскрашенные таким образом графы. И вершины тоже должны быть "монотонными", то есть одного цвета. Все это весьма аналогично написанному в книжке, только книжка красит один раз, а я перекрашиваю несколько (не больше n). В результате у меня количество классов может быть и больше, а их размеры -- меньше. А может и вовсе отличить неизоморфные. Кроме того, исходящие дуги можно покрасить цветом узла, в который они ведут, что также сокращает перебор.

[maxal]

Вот парочка ссылок:

http://www.vigder.com/chris/iso.html

http://www.cs.sunysb.edu/~algorith/file ... hism.shtml

[BlackSem]

Реализовал идею группировки исх множества вершин по кол-ву вход и исх дуг, а далее перебором поиск одинаковой матрицы инцидентности. Для 9 вершин работает порядка 20 секунд. Ужас но пойдёт

[незваный гость]

А можно пример, на котором работает 20 секунд?

[BlackSem]

Я думаю привести пример не получится, так как класс писался, учитывающий специфику тематики, которую я уже интерпретировал в проверку изоморфности графов. Да и классы все на работе
Кратко приведу алгоритм:
Вход: 2 графа
1. Разбиваем граф на группы(группы вершин) по кол-ву входящих, исходящих дуг (inc,out) - определяет группу. (делаем это для каждого графа. В итоге 1ая проверка - одинаковость видов групп и число вершиин в каждой группе)
2. Для каждой группы:
для группый графа А строим матрицу инцидентности, фиксируем её. Меняя нумерацию вершин в группе графа Б, строим для каждого случая матрицу инцидентоности и сравнивем с матрицей для группы графа А. Т.о. если за полное число перенумерации не найдётся такой же матрицы - false - графы не изоморфны.

Основной тормоз алгоритма - полный перебор в нумерации - n! где n - число элементов в группе
9! = 362880 операций.

[незваный гость]

BlackSem писал(а):

Я думаю привести пример не получится, так как класс писался, учитывающий специфику тематики, которую я уже интерпретировал в проверку изоморфности графов.

Я имел в виду пример графов, а не пример кода. Мне почему-то кажется, что должно быть куда быстрее.

Не сочтите за назойливость, но может быть Вы найдете время вставить отладочную печать, например, матриц инцидентности?

[BlackSem]

Пример графа: point <=> point <=> point <=> point <=> point <=> point <=> point <=> point <=> point <=> point <=> point

9 точек со связями (4, 4)
Конечно, не всё время работает долго. Это максимально время, как вы понимаетет, так как при встрече совпавшей матрицы - всё ок

[Ринат]

А как вам мешает составить алгоритм следующая теорема?
Теорема: Два графа являются изоморфными если их матрицы смежности изоморфны.
Две матрицы изоморфны тогда, когда одна получается из другой перестановкой двух строк или столбцов...

[незваный гость]

Ринат писал(а):

А как вам мешает составить алгоритм следующая теорема? ....

Теорема никак не мешает и никак не помогает. Вопрос -- как проверить изоморфность двух матриц? Кстати -- этим путем (после некоторой оптимизации) BlackSem и пошел.

[Amigo]

Полностью согласен с MrD , что для положительного ответа
во всех случаях, необходимо перебрать N! способов обозначить вершины. (частные эвристики способны во многтх ситуациях
облегчить ответ, однако не способны его полностью исчерпать)
Приведу алгоритм на Delphi;(для графов имеющих 10 вершин)

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;
Const
  N=10;
type
  Graf=array[1..n,1..n] of byte;
  Vect=array[1..N] of byte;
  TForm1 = class(TForm)
    Edit1: TEdit;
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;
  Per:vect;
  G1,G2:Graf;
implementation

{$R *.dfm}
Procedure PolnGraf;
var i,j:byte;
Begin
randomize;
for i:=1 to n do begin
for j:=1 to n do begin
{G1[i,j]:=random(2);
G2[i,j]:=random(2);{}
//if i=j then begin G1[i,j]:=1;G2[i,j]:=1;end else begin G1[i,j]:=0;G2[i,j]:=0;end;
G1[i,j]:=0;G2[i,j]:=0;
//G2[i,j]:=G1[i,j];
end;
end;
//G1[3,7]:=1;
j:=random(11);
i:=random(11);
G1[i,j]:=1;
j:=random(11);
i:=random(11);

If (j=0)or (j=6) then j:=4;
G2[j,i]:=1;
{G1[6,7]:=1;
G2[4,8]:=G1[6,7];
{for j:=1 to n do begin

G2[5,j]:=G2[7,j];
G2[7,j]:=G1[5,j];
end;{}



end;
function ProverkaTopologii(l:byte):boolean;
Label 1;
var i,j:byte;
b:boolean;
Begin
b:=true;
for i:=1 to l do begin
for j:=1 to l do begin
if G1[i,j]<>G2[Per[i],Per[j]] then begin
b:=false; goto 1;end;

end;end;
1:
ProverkaTopologii:=b;

end;

Procedure Perestanovka10;
Label 2,1;
var i1,i2,i3,i4,i5,i6,i7,i8,i9,i10:byte;
t:longint;
Begin
t:=0;
for i1:=1 to N do begin Per[1]:=i1; for i2:=1 to N do begin if i1<>i2 then begin Per[2]:=i2; for i3:=1 to n do begin if (I3<>i1) and (I3<>i2) then
begin Per[3]:=i3; for i4:=1 to n do begin if (i4<>i3)and(i4<>i2)and(i4<>i1) then begin Per[4]:=i4; for i5:=1 to n do
begin if (i5<>i1)and(i5<>i2)and(i5<>i3)and(i5<>i4) then begin Per[5]:=I5; for i6:=1 to n do begin if (i6<>i1)and(i6<>i2)and(i6<>i3)and(i6<>i4) and(i6<>i5) then
begin  Per[6]:=I6;for i7:=1 to n do begin if (i7<>i1)and(i7<>i2)and(i7<>i3)and(i7<>i4) and(i7<>i5)and(i7<>i6) then begin Per[7]:=I7; for i8:=1 to n do
begin if (i8<>i1)and(i8<>i2)and(i8<>i3)and(i8<>i4) and(i8<>i5)and(i8<>i6)and(i8<>i7) then begin Per[8]:=I8; for i9:=1 to n do begin if (i9<>i1)and(i9<>i2)and(i9<>i3)and(i9<>i4) and(i9<>i5)and(i9<>i6)and(i9<>i7)and(i9<>i8) then
begin Per[9]:=I9;for i10:=1 to n do begin if (i10<>i1)and(i10<>i2)and(i10<>i3)and(i10<>i4) and(i10<>i5)and(i10<>i6)and(i10<>i7)and(i10<>i8)and(i10<>i9) then begin
Per[10]:=I10;
if ProverkaTopologii(n)=true then begin t:=1;goto 2;end;
{Per[10]:=I10;
t:=t+1;
if t=2000000 then begin
Per[10]:=I10;

end;{}
end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;
showmessage('Ãðàôû íå èçîìîðôíû');goto 1;

2:for i1:=1 to N do form1.Edit1.Text:=form1.Edit1.Text+' I('+inttostr(i1)+')='+inttostr(Per[i1])+' ,';


1:
end;//êîíåö ïðîöåäóðû




procedure TForm1.Button1Click(Sender: TObject);
begin
form1.Edit1.Text:='';
PolnGraf;
Perestanovka10;
end;

end.