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

[ha]

Написал немного не точно, из $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.

[bin]

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$ там меняются совсем не малыми "шевелениями".

[ha]

Вот вам домашнее задание:

Дан набор непрерывных (хотите - можете считать линейных) функций $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))$. Ну или предъявите контрпример, если вы мне не верите.

[bin]

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))$. Ну или предъявите контрпример, если вы мне не верите.

Выше Вы уже предъявили контрпример графа с тремя вершинами Но если хотите, можете сами попытаться доказать свое собственное утверждение. Однако как оно относится к обсуждаемому алгоритму? Никак. Явный уход в сторону от темы.

[bin]

В то же время со свойством 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) Вообще удалить это свойство из статьи, т.к. дальнейшее доказательство в нем не нуждается.

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

[ha]

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

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

[bin]

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

В математике утверждения требуют доказательств.

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

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

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

Если утверждение не используется, зачем вы его приводите?

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

[bin]

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

[ha]

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

[bin]

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

[ha]

Вот оно что. Будем знать.

[bin]

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

[y_nikolaenko]

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

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

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

[bin]

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

[y_nikolaenko]

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

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

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