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
903
Глупый вопрос - а из чего следует свойство 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
903
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, Супермодераторы



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

Сейчас этот форум просматривают: ilghiz


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

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