2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2, 3, 4, 5 ... 26  След.
 
 Полиномиальный алгоритм изоморфизма графов
Сообщение17.04.2010, 12:22 
Аватара пользователя


22/09/09

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

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение17.04.2010, 13:12 
Аватара пользователя


21/02/10
1594
Екатеринбург
А что на русском языке нет?

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение17.04.2010, 13:52 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Не могли бы Вы дать некоторую оценку того, с какой точностью необходимо производить вычисления при большом $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$), а затем проверить равентство мощностей этих групп и, в конце концов, построить соответствие подобных вершин подобным и проверить его на то, является ли оно изоморфизмом?
Этот алгоритм имеет худшую асимптотику, чем описанный в статье, но, на мой взгляд, более понятен. Не упустил ли я чего нибудь?

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение17.04.2010, 18:48 
Аватара пользователя


22/09/09

1907
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 графа?" за полиномиально зависящее от числа вершин время.

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение17.04.2010, 19:37 
Заслуженный участник
Аватара пользователя


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

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

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

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

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

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение17.04.2010, 20:06 
Аватара пользователя


22/09/09

1907
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 второго.

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение17.04.2010, 20:14 
Заслуженный участник
Аватара пользователя


06/10/08
6422
bin в сообщении #310664 писал(а):
К сожалению, нет. Взляните на пример 3 (приложение 1) вершины 1 и 14 не подобны, а при сравнении только разбиений может получиться, что вершина 1 первого графа будет соотнесена с вершиной 14 второго.

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

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение17.04.2010, 20:32 
Аватара пользователя


22/09/09

1907
Xaositect в сообщении #310667 писал(а):
В таком случае, правильно ли я понимаю, что разбиения можно не вычислять, а сравнить попарно все $W_i$ и $W'_j$, и построить поозреваемое на изоморфизм отображение исходя только из данных об этих сравнениях?
На каждом шаге итерации мы измельчаем блоки разбиения, выбирая очередную вершину-источник. Вершины могут быть подобными, но отображение подобной вершины в подобную (но не там лежащую) будет неверным, и его зарубит функция Verify. Посмотрите на рис.2, G2. Правые вершины, обозначенные кружком и треугольником, подобны соответствующим левым кружкам и треугольникам (и квадратики по центру изображения графа). Соотносим правый кружок-вершину первого графа с правым кружком второго, правый верхний треугольник первого с левым верхним второго и правый нижний треугольник первого с правым нижним второго... В итоге получаем неверный ответ.

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение17.04.2010, 20:36 
Заслуженный участник
Аватара пользователя


06/10/08
6422
bin в сообщении #310674 писал(а):
Xaositect в сообщении #310667 писал(а):
В таком случае, правильно ли я понимаю, что разбиения можно не вычислять, а сравнить попарно все $W_i$ и $W'_j$, и построить поозреваемое на изоморфизм отображение исходя только из данных об этих сравнениях?
На каждом шаге итерации мы измельчаем блоки разбиения, выбирая очередную вершину-источник. Вершины могут быть подобными, но отображение подобной вершины в подобную (но не там лежащую) будет неверным, и его зарубит функция Verify. Посмотрите на рис.2, G2. Правые вершины, обозначенные кружком и треугольником, подобны соответствующим левым кружкам и треугольникам (и квадратики по центру изображения графа). Соотносим правый кружок-вершину первого графа с правым кружком второго, и правый верхний треугольник первого с левым верхним второго... В итоге получаем неверный ответ.

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

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение17.04.2010, 20:42 
Аватара пользователя


22/09/09

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

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение20.04.2010, 12:50 


02/09/08
143
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$.

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение20.04.2010, 14:46 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение20.04.2010, 19:24 
Аватара пользователя


22/09/09

1907
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?
Это следует из начал линейной алгебры, которые проходят и в средней школе. Только в школе существование и единственность решения для СЛУ определенного типа доказывают через определители, а на первом курсе института уже вводится понятие ранга матрицы ;-)

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение20.04.2010, 22:10 
Заслуженный участник
Аватара пользователя


06/10/08
6422
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

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение20.04.2010, 22:26 
Заслуженный участник


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

Спасибо.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 380 ]  На страницу 1, 2, 3, 4, 5 ... 26  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group