Полиномиальный алгоритм изоморфизма графов

[bin]

Приглашаю обсудить мою статью: http://arxiv.org/abs/1004.1808v1

[Pavlovsky]

А что на русском языке нет?

[Xaositect]

Не могли бы Вы дать некоторую оценку того, с какой точностью необходимо производить вычисления при большом $n$? Верно ли я понимаю, что при переходе по ребру от $x_i$ к $x_j$ отношение $\Delta x_i$ к $\Delta x_j$ примерно $d_i + 1$, а это значит, что $\varepsilon$ можно грубо оценить снизу как $\frac{1}{n^n}$?

-- Сб апр 17, 2010 14:45:32 --

Так, c $\epsilon$ я вроде разобрался. Там обращение матрицы, так что с ним все хорошо. Разбираюсь подробнее.
Вначале мы вводим некоторую систему уравнений $x_i = \frac{1}{d_i + 1}\sum_{j\ \text{смежна с}\ i} x_j + b_i$
Ее можно переписать в виде $(E + D - M)\bar{x} = \bar {B}$, $E$ - единичная, $D$ - матрица степеней, $M$ - матрица смежности, $B_i = (d_i + 1) b_i$. В утверждениях Conclusion 1 - Conclusion 3 решения этой системы связываются с изоморфизмами.
Для удобства я обозначу $E+D-M = A$.
Далее, мы вводим $w_i$ и $W_i$. Если я правильно понял, то его можно записать в виде $w_i = \mathrm{sort}(e_i A^{-1})$. А $W_i$ содержит все $w_j$ в особом порядке - в разных строках $w_j$ для вершины с разным расстоянием от $i$, отсортированные по убыванию. Правильно ли я понимаю, что матричная структура $W_i$ не используется, и вместо него можно писать просто набор $(w_i); (w_{j_1}, w_{j_2},\dots), (w_{k_1}, w_{k_2},\dots)$, где скобки соответствуют различному удлению от $i$?
Утверждается, что $W_i = W'_j$ т. и т.т., когда $i$ и $j$ подобны.

Дальше у меня такой вопрос. Можно ли сделать так: выделить подобные вершины в каждом графе и сопоставить группы подобных вершин с помощью сравнения всех $W_i$ и $W'_i$ ($n^6$), а затем проверить равентство мощностей этих групп и, в конце концов, построить соответствие подобных вершин подобным и проверить его на то, является ли оно изоморфизмом?
Этот алгоритм имеет худшую асимптотику, чем описанный в статье, но, на мой взгляд, более понятен. Не упустил ли я чего нибудь?

[bin]

Pavlovsky в сообщении #310535 писал(а):

А что на русском языке нет?

На русском пока нет: был предварительный русский вариант в MS Word, потом было много дополнений в англ., потом перевел его в LaTeX... Думаю в ближайшее время сделать и русскоязычный вариант - так будет удобнее обсуждать, как сделаю и выложу - так сообщу. Только из меня плохой переводчик в обе стороны - всегда предпочитаю пересказывать, а не переводить, так что варианты не будут "тождественны"

-- Сб апр 17, 2010 20:25:38 --

Xaositect в сообщении #310546 писал(а):

Не могли бы Вы дать некоторую оценку того, с какой точностью необходимо производить вычисления при большом $n$? Верно ли я понимаю, что при переходе по ребру от $x_i$ к $x_j$ отношение $\Delta x_i$ к $\Delta x_j$ примерно $d_i + 1$, а это значит, что $\varepsilon$ можно грубо оценить снизу как $\frac{1}{n^n}$?

-- Сб апр 17, 2010 14:45:32 --

Оценка в приложении 3 для звездчатых графов.

Xaositect в сообщении #310546 писал(а):

Так, c $\epsilon$ я вроде разобрался. Там обращение матрицы, так что с ним все хорошо. Разбираюсь подробнее.
Вначале мы вводим некоторую систему уравнений $x_i = \frac{1}{d_i + 1}\sum_{j\ \text{смежна с}\ i} x_j + b_i$
Ее можно переписать в виде $(E + D - M)\bar{x} = \bar {B}$, $E$ - единичная, $D$ - матрица степеней, $M$ - матрица смежности, $B_i = (d_i + 1) b_i$. В утверждениях Conclusion 1 - Conclusion 3 решения этой системы связываются с изоморфизмами.
Для удобства я обозначу $E+D-M = A$.
Далее, мы вводим $w_i$ и $W_i$. Если я правильно понял, то его можно записать в виде $w_i = \mathrm{sort}(e_i A^{-1})$. А $W_i$ содержит все $w_j$ в особом порядке - в разных строках $w_j$ для вершины с разным расстоянием от $i$, отсортированные по убыванию. Правильно ли я понимаю, что матричная структура $W_i$ не используется, и вместо него можно писать просто набор $(w_i); (w_{j_1}, w_{j_2},\dots), (w_{k_1}, w_{k_2},\dots)$, где скобки соответствуют различному удлению от $i$?
Утверждается, что $W_i = W'_j$ т. и т.т., когда $i$ и $j$ подобны.

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

Xaositect в сообщении #310546 писал(а):

Дальше у меня такой вопрос. Можно ли сделать так: выделить подобные вершины в каждом графе и сопоставить группы подобных вершин с помощью сравнения всех $W_i$ и $W'_i$ ($n^6$), а затем проверить равентство мощностей этих групп и, в конце концов, построить соответствие подобных вершин подобным и проверить его на то, является ли оно изоморфизмом?
Этот алгоритм имеет худшую асимптотику, чем описанный в статье, но, на мой взгляд, более понятен. Не упустил ли я чего нибудь?

Так ведь проблема в том, чтобы в каждом графе выделить подобные вершины! Первоначальный алгоритм (опубликованный в "Известиях РАН. Сер. хим.") не использовал W-матриц. 95 миллионов молекулярных графов - практически все интересные для компьютерной химии - прекрасно им распознавались. И только такой "патологический" граф, как в Примере 3 Приложения 1 (невозможный для хим.молекулы), заставил задуматься о более тонком распознавании подобных вершин. В обсуждаемой статье внимание не на прикладную ценность алгоритма, а на принципиальную возможность дать ответ на вопрос "изоморфны ли 2 графа?" за полиномиально зависящее от числа вершин время.

[Xaositect]

bin в сообщении #310640 писал(а):

Так ведь проблема в том, чтобы в каждом графе выделить подобные вершины! Первоначальный алгоритм (опубликованный в "Известиях РАН. Сер. хим.") не использовал W-матриц. 95 миллионов молекулярных графов - практически все интересные для компьютерной химии - прекрасно им распознавались. И только такой "патологический" граф, как в Примере 3 Приложения 1 (невозможный для хим.молекулы), заставил задуматься о более тонком распознавании подобных вершин. В обсуждаемой статье внимание не на прикладную ценность алгоритма, а на принципиальную возможность дать ответ на вопрос "изоморфны ли 2 графа?" за полиномиально зависящее от числа вершин время.

Я имею в виду, если мы имеем $W_i$ для всех вершин, то мы можем выделить подобные вершины просто попарным сравнением, так? Построение всех $W_i$ может быть сделано за $n^4$, а их попарные сравнения за $n^5$. Суть алгоритма в этом?

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

-- Сб апр 17, 2010 19:41:24 --

А, я понял. Используемые в алгоритме разбиения $\mathfrak{U}$ - это и есть разбиения вершин графа на множества подобных.

[bin]

Xaositect в сообщении #310653 писал(а):

Я имею в виду, если мы имеем $W_i$ для всех вершин, то мы можем выделить подобные вершины просто попарным сравнением, так? Построение всех $W_i$ может быть сделано за $n^4$, а их попарные сравнения за $n^5$. Суть алгоритма в этом?

Да,+ детали...

Xaositect в сообщении #310653 писал(а):

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

-- Сб апр 17, 2010 19:41:24 --

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

Xaositect в сообщении #310653 писал(а):

А, я понял. Используемые в алгоритме разбиения $\mathfrak{U}$ - это и есть разбиения вершин графа на множества подобных.

К сожалению, нет. Взляните на пример 3 (приложение 1) вершины 1 и 14 не подобны, а при сравнении только разбиений может получиться, что вершина 1 первого графа будет соотнесена с вершиной 14 второго.

[Xaositect]

bin в сообщении #310664 писал(а):

К сожалению, нет. Взляните на пример 3 (приложение 1) вершины 1 и 14 не подобны, а при сравнении только разбиений может получиться, что вершина 1 первого графа будет соотнесена с вершиной 14 второго.

В таком случае, правильно ли я понимаю, что разбиения можно не вычислять, а сравнить попарно все $W_i$ и $W'_j$, и построить поозреваемое на изоморфизм отображение исходя только из данных об этих сравнениях?

[bin]

Xaositect в сообщении #310667 писал(а):

В таком случае, правильно ли я понимаю, что разбиения можно не вычислять, а сравнить попарно все $W_i$ и $W'_j$, и построить поозреваемое на изоморфизм отображение исходя только из данных об этих сравнениях?

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

[Xaositect]

bin в сообщении #310674 писал(а):

Xaositect в сообщении #310667 писал(а):

В таком случае, правильно ли я понимаю, что разбиения можно не вычислять, а сравнить попарно все $W_i$ и $W'_j$, и построить поозреваемое на изоморфизм отображение исходя только из данных об этих сравнениях?

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

Осознал.
Завтра прочитаю еще раз, а на следующей неделе попробую обсудить с научным руководителем, думаю, ему будет интересна новость.

[bin]

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

[ha]

Property 5 не верно, поскольку из него с помощью малых шевелений следует, что из $b_i=b_j$ следует $x_i=x_j$, но для графа на 3 вершинах с ребрами 1-2, 2-3, при $b_1=1,\ b_2=1,\ b_3=0$ выполнено $x_1=4/3+3/4,\ x_2=3/2+2/3,\ x_3=1/3+3/4$ и легко видеть, что $x_1\neq x_2$.

[12d3]

Глупый вопрос - а из чего следует свойство 1?

[bin]

ha в сообщении #311376 писал(а):

Property 5 не верно, поскольку из него с помощью малых шевелений следует, что из $b_i=b_j$ следует $x_i=x_j$, но для графа на 3 вершинах с ребрами 1-2, 2-3, при $b_1=1,\ b_2=1,\ b_3=0$ выполнено $x_1=4/3+3/4,\ x_2=3/2+2/3,\ x_3=1/3+3/4$ и легко видеть, что $x_1\neq x_2$.

1) Уточните, пожалуйста, что Вы понимаете под "малым шевелением"?
2) Свойство 5 утверждает, что если мы зададим максимальный свободный член для какой-то вершины (вершины-источника), то вес этой вершины окажется максимальным (речь идет о единственном максимуме). При этом веса вершин, соседних с данной (т.е. удаленные на расстояние 1), будут не меньше весов вершин на расстоянии 2, те в свою очередь будут не меньше, чем веса вершин на расстоянии 3 и т.д. Т.е. приращение веса убывает по мере удаления от вершины-источника. Здесь нет ничего про равенство $b_i=b_j$ , и не утверждается, что в случае такого равенства $x_i=x_j$.

-- Вт апр 20, 2010 20:27:13 --

12d3 в сообщении #311413 писал(а):

Глупый вопрос - а из чего следует свойство 1?

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

[Xaositect]

bin в сообщении #311481 писал(а):

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

Я думаю, что 12d3 в курсе понятия ранга (а если нет, сможет его найти).

Дело в том, что матрица этой системы $E + D - M$ положительно определенная, т.к. $D - M$ неотрицательно определенная, это известная теорема алгебраической теории графов ($x^{*} (D-M) x = \sum\limits_{i,j\text{ смежны}}(x_i - x_j)^2$).

http://en.wikipedia.org/wiki/Laplacian_matrix

[12d3]

Xaositect в сообщении #311521 писал(а):

Дело в том, что матрица этой системы $E + D - M$ положительно определенная, т.к. $D - M$ неотрицательно определенная, это известная теорема алгебраической теории графов ($x^{*} (D_M) x = \sum\limits_{i,j\text{ инцидентны}}(x_i - x_j)^2$).

Спасибо.