2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5 ... 26  След.
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение21.04.2010, 18:31 


02/09/08
143
Написал немного не точно, из $b_i=b_j=max(b_1,\dots,b_n)$ с помощью малых шевелений (добавления $\varepsilon$ к $b_i$ или $b_j$) можно получить $x_i=x_j=max(x_1,\dots,x_n)$ при условии свойства 5.

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


22/09/09

1907
ha в сообщении #311817 писал(а):
Написал немного не точно, из $b_i=b_j=max(b_1,\dots,b_n)$ с помощью малых шевелений (добавления $\varepsilon$ к $b_i$ или $b_j$) можно получить $x_i=x_j=max(x_1,\dots,x_n)$ при условии свойства 5.
Свойство 5 рассматривает случай единственного максимума, т.е. когда все остальные $b_j$ меньше $b_i$ . Кроме того, из того, что одно $b$ будет приблизительно равно другому, совсем не следует, что соответствующие им $x будут также приблизительно равны (с той же погрешностью вычислений). И кроме того, из дальнейшего алгоритма видно, что $b$ там меняются совсем не малыми "шевелениями".

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение22.04.2010, 20:21 


02/09/08
143
Вот вам домашнее задание:

Дан набор непрерывных (хотите - можете считать линейных) функций $x_1(b_1,\dots,b_n),\dots, x_n(b_1,\dots,b_n)$. Известно, что для любого $i$ если $b_i>b_j$ для всех $j\neq i$ то $x_i(b_1,\dots,b_n)>x_j(b_1,\dots,b_n)$ для всех $j\neq i (другими словами, если $b_i$ единственный максимум, то и $x_i$ единственный максимум). Доказать, что из $b_i=b_j=\max(b_1,\dots,b_n)$ следует $x_i(b_1,\dots,b_n)=x_j(b_1,\dots,b_n)=\max(x_1(b_1,\dots,b_n),\dots,x_n(b_1,\dots,b_n))$. Ну или предъявите контрпример, если вы мне не верите.

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


22/09/09

1907
ha в сообщении #312237 писал(а):
Вот вам домашнее задание:

Дан набор непрерывных (хотите - можете считать линейных) функций $x_1(b_1,\dots,b_n),\dots, x_n(b_1,\dots,b_n)$. Известно, что для любого $i$ если $b_i>b_j$ для всех $j\neq i$ то $x_i(b_1,\dots,b_n)>x_j(b_1,\dots,b_n)$ для всех $j\neq i (другими словами, если $b_i$ единственный максимум, то и $x_i$ единственный максимум). Доказать, что из $b_i=b_j=\max(b_1,\dots,b_n)$ следует $x_i(b_1,\dots,b_n)=x_j(b_1,\dots,b_n)=\max(x_1(b_1,\dots,b_n),\dots,x_n(b_1,\dots,b_n))$. Ну или предъявите контрпример, если вы мне не верите.
Выше Вы уже предъявили контрпример графа с тремя вершинами :-) Но если хотите, можете сами попытаться доказать свое собственное утверждение. Однако как оно относится к обсуждаемому алгоритму? Никак. Явный уход в сторону от темы.

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


22/09/09

1907
В то же время со свойством 5 не все в порядке! Emil Jeřábek нашел контрпример: 4х вершинный цикл, берем $\vec B$ = (3, 33 ,30,30), т.е. $\vec b$= (1,11,10,10) - получаем $\vec x$ = (18,16,27,25). Какие будут мнения, как исправить это свойство? Например, с ходу возникают две идеи:

1) Если $b_i= max$, то $x_j= max$, где $max$ - единственный максимум.

2) Вообще удалить это свойство из статьи, т.к. дальнейшее доказательство в нем не нуждается.

В любом случае данный баг не является фатальной ошибкой.

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение23.04.2010, 15:05 


02/09/08
143
Попробуйте-ка сначала доказать условие задачи для моего графа, прежде чем бросаться голословными утверждениями, что это контрпример к моему утверждению. В математике утверждения требуют доказательств. Надеюсь для вас это не новость?

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

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


22/09/09

1907
ha в сообщении #312469 писал(а):
В математике утверждения требуют доказательств.
Вот именно! Вы сделали некое утверждение и вместо того, чтобы его доказать как положено - поставили передо мной такое "задание". Вы наверное меня с кем-то перепутали, я не Ваш ученик (если они у Вас есть) и здесь Вам не школа, и учителем с правом расставлять двойки Вас никто не назначал. Да и "задачка" обсуждается отнюдь не школьная - не даром ее пока никому не удалось решить (мой препринт - не окончательный вариант решения). А грубость, как известно, доказательством не является.

Если Вас интересует мой уровень, то в области Computer Sci. (у нас так ведь называется этот подфорум) я 30 лет. Дополнительную информацию можно получить, например, здесь: http://software.intel.com/en-us/article ... l-of-fame/ см. секцию Top Community Masterminds.

ha в сообщении #312469 писал(а):
Если утверждение не используется, зачем вы его приводите?
Виноват. Оно осталось от прежнего доказательства. Так ли оно нужно в данном - об этом я и хотел посоветоваться с Сообществом.
Жаль, конечно, но Ваше право выйти из обсуждения, я надеялся услышать от Вас что-то более внятное.

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


22/09/09

1907
Откорректировал свойство 5: Вместо:
"Если $b_i= max$..."
Следует читать:
"Мы всегда можем задать такое $b_i= max$..., что $x_i= max$..."
Свойство 5 не используется в доказательстве в явном виде, однако проясняет работу алгоритма. Поэтому в новой версии препринта оно не будет отмечено как свойство 5, а перейдет в текст как замечание.

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


02/09/08
143
Вот вам еще пища для размышлений. "Further, without loss of generality of the task, we will consider undirected connected graphs without loops [7, 10]."
Но для деревьев изоморфизм графов тривиален. Или тут имелось в виду все наоборот - граф без деревьев?

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


22/09/09

1907
Loop (петля) - это когда у ребра с 2х концов одна и та же вершина. А дерево - это граф без циклов (cycle, ring). Это общая терминология. Имелось в виду граф без петель, который может быть деревом, а может содержать и циклы. Строго говоря, изоморфизм деревьев нетривиален, но для него давно известны эффективные алгоритмы.

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение08.05.2010, 21:03 


02/09/08
143
Вот оно что. Будем знать.

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


22/09/09

1907
Внимание! Выложил новую версию 1.1.6 программы, реализующий алгоритм. В ней исправлены замеченные «баги» реализации. Вскоре так же последует обновление статьи: концепция та же – но скорректирован ряд важных деталей. В частности, по отмеченному выше свойству и по доказательству Леммы 1. Кроме того, англоязычные коллеги подсказали несколько важных для понимания статьи языковых правок. Помню, что обещал русскоязычную версию статьи – сделаю ее позже – ориентировочно к осени. Дополнительно сообщу – по мере готовности.

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение18.09.2010, 11:17 
Заблокирован


18/09/10

183
bin в сообщении #310516 писал(а):
Приглашаю обсудить мою статью: http://arxiv.org/abs/1004.1808v1

Несколько лет назад натолкнулся на быстрый алгоритм изоморфизма графов, который использовал вероятностную интерпретацию (помнится, порядка 10000 тысяч узлов (а может и 100000 тысяч: точно не помню) он на P4 перебирал за секунды 3: там был выложен тест). Там ни автор, ни его оппонеты так и не смогли найти пример неизоморфных графов, которые бы программа не распознала.

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


22/09/09

1907
Выложил новую версию статьи: http://arxiv.org/abs/1004.1808 (и программы).

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение22.09.2010, 11:44 
Заблокирован


18/09/10

183
bin в сообщении #355033 писал(а):
Выложил новую версию статьи: http://arxiv.org/abs/1004.1808 (и программы).

Спасибо. А вы не могли бы сказать что-либо по поводу моего предыдущего сообщения: перерыл у себя архивы, но ничего не нашел.

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

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



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

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


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

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