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

[ha]

Еще один пример:$\begin{bmatrix} a & b & c &d \\ b & a & d & c \\ c & d & e & f \\ d & c & f & g \end{bmatrix}$, $r(1) = 2,\ r(2) = 1,\ r(3) = 3,\ r(4) = 4$. Здесь внедиагональные элементы не совпадают с диагональными. Тем не менее $k_{13} = c \neq d = k_{23} = k_{r(1)r(3)}$.

[bin]

ha,
Прежде всего, позвольте узнать причину выбора столь сердитой формы Ваших сообщений. За недавнее время тут выступило трое оппонентов, и каждое выступление было все громче и громче, местами срываясь на крик. Невольно вспоминается пословица: "Юпитер, ты сердишься - значит, ты неправ" Убедительно прошу Вас: постарайтесь, пожалуйста, умерить эмоции до приличного для научного форума уровня, а то уважаемый модератор, наверное, уже устал делать замечания!

Что касается существа Вашей критики. Прежде всего, я не понял претензии:

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

Conclusion 2 не верно или по крайней мере не доказано. Чтобы сделать его верным нужно дополнительно потребовать, что существует хотя бы один изоморфизм между графами переводящий $i$ в $j$.

По определению изоморфизма, если два графа изоморфны, то для любой i-ой вершины первого графа всегда найдется подобная ей вершина j (одна или несколько) второго графа. Что тут еще нужно доказывать? Полагаю, что до выяснения этого ключевого момента отвечать на дальнейшие замечания преждевременно. Вместе с тем предлагаю Вам очистить Ваши сообщения от излишних эмоций и переписать их более внятно, с учетом того, что на ряд вопрсов как, например, h=r(h) я недавно уже ответил. Если в тех ответах Вас что-то не удовлетворило - процитируйте, что конкретно. Повторять же все, что я уже сказал здесь на эту тему, еще раз я в любом случае не буду. Переписав свои сообщения в более адекватной и внятной форме, Вы сильно сэкономите время, как мне, так и нашим читателям.

[bin]

PS На всякий случай внесу коррективы: выражение "h=r(h)" в предыдущем сообщении не стоит понимать буквально

[ha]

Сердитая форма вызвана тем, что мне пришлось решить не мало ребусов читая вашу статью. Во многих случаях оказывалось легче придумывать доказательство самому, чем пытаться оформить ваши рассуждения в строгую форму.

Я не спорю с тем, что для любой вершины i найдется подобная вершина j. Но в Conlusion 2 у вас этого требования нет. В графе G' могут оказаться несколько вершин j у которых множество координат x' совпадает с множеством координат x. И не для каждой из них соответствующая перестановка координат окажется изоморфизмом между графами.

Приведу наглядный пример. Пусть у нас в качестве $x$ выступает не решение системы линейных уравнений, а кратчайшее расстояние на графе. Пусть дополнительно ребра графа имеют длину.
Рассмотрим неориентированный граф G
1->2 длина 3
2->3 длина 1
3->4 длина 2
4->5 длина 4
5->1 длина 2
Граф G' выберем совпадающим с G.
Пусть i = 1, тогда вектор кратчайших расстояний будет $x_1 = (0,3,4,6,2)$.

Если j = 1, то $x'_1 = x_1 =(0,3,4,6,2)$. Получаем тождественную перестановку, которая является изоморфизмом графов. Ваше утверждение верно.

Пусть теперь j = 4. $x'_4 = x_4 = (6,3,2,0,4)$. Получаем перестановку $\pi(1) = 4, \pi(2) = 2, \pi(3) = 5, \pi(4) = 1, \pi(5) = 3$. Эта перестановка не сохраняет даже ребра, не говоря уж о весах. Таким образом, инвариантности определения $x$ при изоморфизмах не достаточно для справедливости вашего утверждения. Если вы хотите им пользоваться, то вам придется его доказать для вашего определения $x$.

Насчет r(h) - я хотел прочитать вашу статью не предвзято, а потому не читал соответствующие комментарии. В любом случае, если что-то нужно обязательно разъяснять - то это должно быть в статье. Мои предположения на данный момент:

r(h) - некоторая перестановка, про которую известно, что $w_h=w_{r(h)}$, $d_h=d_{r(h)}$ и $r(i)=p,\ r(p)=r(i)$. Никакие другие свойства в Лемме 1 не описаны, а значит пользоваться ими нельзя. Если это так, то главное равенство $k_{ij}=k_{r(i)r(j)}$ у вас не доказано и как показывают мои контрпримеры оно из этих свойств + симметричность матрицы $A$ не следует.

[ha]

О, я заметил notes to lemma 1 в которых похоже и скрыто доказательство этого факта. Никогда раньше не видел чтобы доказательство самого главного факта статьи переносили в notes.

-- Пт апр 22, 2011 14:13:57 --

Почитал комментарии и остаток статьи. Теперь мне понятно что такое r(h) и возражений whitefox'a у меня нет. Только удивительный факт - что такое r(h) нигде в самой статье не написано! Теперь с этих позиций стали ясны и другие проблемы.

Например, я согласен с тем, что r(i)=p, но почему r(p) = i? Может оказаться, что $w_i = w_p = w_q$ и когда мы будем строить соответствие у нас в $W_i$ в какой-то строке будут идти $w_p$ и $w_q$, а в $W_p$ в той же строке будут идти $w_q$ и $w_i$. В итоге мы получим r(p)=q, r(q)=i. Так что утверждение r(p)=i не верно для любой перестановки r устанавливающей соответствие между $W_i$ и $W_p$. (конкретный пример графа - треугольник или просто полный граф с n>2 вершинами, где можно создавать и более длинные циклы)

Конкретно эта проблема легко решается. Всегда можно подправить r, чтобы r(p)=i (p всегда будет на той же строке в матрице $W_i$, что и i в матрице $W_p$ в виду симметричности расстояния).

Но вот в Appendix 2 встречаются более серьезные проблемы. Вы берете две вершины l и m соответствующие друг другу. r(l)=m по определению. А вот r(m)=l может не выполняться. И даже подправить r уже нельзя. Дело в том, что вершина m в матрице $W_i$ может находится в другой строчке, чем вершина l в матрице $W_p$. И тогда r(m)=l уже будет противоречить определению r. Вершины i и p при этом разумеется не могут быть подобны.

И даже если бы этой проблемы не было, нельзя утверждать, что $k_{lh} = k_{mr(h)}$. Между этими строчками обязано быть соответствие, но оно не обязано совпадать с r. Эта может быть другая, никак не связанная с r перестановка.

С учетом этих фатальных ошибок, остаток Appendix 2 я дочитывать не буду.

[bin]

ИМХО ребусов нет - Вы просто пытаетесь создать искусственные сложности, в частности, неэквивалентными переформулировками. Например:

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

Приведу наглядный пример. Пусть у нас в качестве выступает не решение системы линейных уравнений, а кратчайшее расстояние на графе.

Но мое Утверждение доказано для решений СЛУ, составленной по определенным в статье правилам, а не для расстояний, и для неориентированного графа (а Ваш пример для орграфа). То, что верно для этих решений, необязательно верно для расстояний на орграфе - т.о. Ваша подмена некорректна.

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

Никогда раньше не видел чтобы доказательство самого главного факта статьи переносили в notes.

ИМХО самый главный факт - это Утверждение 1 и выводы из него, а другой главный факт - это СЛУ и как его строить, третий гл. факт - описание алгоритма и много еще там есть главных фактов, как и в каждой не совсем тривиальной статье Традиция выносить объемные детали (в том числе и детали доказательства) в приложение или в примечание - широко распространена. Так, редакторы многих крупных научных журналов требуют этого. И надо признать, что в таком требовании есть большой смысл - статья становится более структурированной: можно сравнить с программированием - когда фрагмент кода оформляют в виде процедуры. Читабельность и статьи, и кода повышается - в противном случае можно получить ситуацию, когда за деревьями не видно леса.
У меня еще есть много что сказать, например, если $W_i=W_p=W_q$, то $i=r(p)=t(q)$, но нас интересуют не любые перестановки, а нас интересует только то, что в числе многих других есть такая, для которой $i=r(p)$,$p=r(i)$. Не нужно путать доказательство леммы с алгоритмом: для поиска нужной перестановки в доказательстве и полный перебор не волнует. И еще есть что сказать, но послушаю сначала, что Вы ответите на уже сказанное.
PS Еще замечание про ребусы: если что и назвать Ребусом - это саму задачу построения алгоритма изоморфизма графов с полиномиальной выч. сложностью. Недаром 30 лет ее решают Но не всякая сложная задача имеет простое решение, поэтому готов признать, что мое решение не выглядит очень простым. И в качестве развлекательного чтива моя статья не годится

[ha]

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

ИМХО ребусов нет - Вы просто пытаетесь создать искусственные сложности, в частности, неэквивалентными переформулировками. Например:

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

Приведу наглядный пример. Пусть у нас в качестве выступает не решение системы линейных уравнений, а кратчайшее расстояние на графе.

Но мое Утверждение доказано для решений СЛУ, составленной по определенным в статье правилам, а не для расстояний, и для неориентированного графа (а Ваш пример для орграфа). То, что верно для этих решений, необязательно верно для расстояний на орграфе - т.о. Ваша подмена некорректна.

Я же написал, что граф неориентированный. Значит все указанные ребра можно проходить в обе стороны.
Вы ничего не доказали, вы просто утверждаете что это верно. Ваше обоснование - Conclusion 1 (точнее в статье обоснование отсутствует, но можно догадаться, что имеется в виду conсlusion 1). В моем случае оно выполняется, а Conclusion 2 - нет. Так что потрудитесь привести доказательство.

Цитата:

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

Никогда раньше не видел чтобы доказательство самого главного факта статьи переносили в notes.

ИМХО самый главный факт - это Утверждение 1 и выводы из него, а другой главный факт - это СЛУ и как его строить, третий гл. факт - описание алгоритма и много еще там есть главных фактов, как и в каждой не совсем тривиальной статье Традиция выносить объемные детали (в том числе и детали доказательства) в приложение или в примечание - широко распространена. Так, редакторы многих крупных научных журналов требуют этого. И надо признать, что в таком требовании есть большой смысл - статья становится более структурированной: можно сравнить с программированием - когда фрагмент кода оформляют в виде процедуры. Читабельность и статьи, и кода повышается - в противном случае можно получить ситуацию, когда за деревьями не видно леса.

Ага, замечательно повышается. В начале приводится "доказательство" в котором отсутствуют обоснования наиболее важных частей, а затем кусок текста который как-то с ней связан. Логику связи между ними должен придумывать читатель. Лично мне она до сих пор не до конца понятна. Это доказательство Леммы 1? Какой-то ее части? Алгоритма? На данный момент это не важно в виду найденных мною ошибок.

Цитата:

У меня еще есть много что сказать, например, если $W_i=W_p=W_q$, то $i=r(p)=t(q)$, но нас интересуют не любые перестановки, а нас интересует только то, что в числе многих других есть такая, для которой $i=r(p)$,$p=r(i)$. Не нужно путать доказательство леммы с алгоритмом: для поиска нужной перестановки в доказательстве и полный перебор не волнует. И еще есть что сказать, но послушаю сначала, что Вы ответите на уже сказанное.

Мало ли что можно выбрать. Факт тот, что утверждение в вашей статье не верно. А любое неверное утверждение - веская причина для отказа публикации. Рецензент додумывать обоснование и читать дальше первой ошибки не обязан. Подразумеваете, что можно выбрать, вместо для любого - так и пишите и обосновывайте почему можно выбрать. Иначе вам придется ждать еще 2 месяца только для того, чтобы вставить эту фразу. Это в ваших же интересах.

Эффективность поиска выбора в доказательстве меня тоже не волнует.

Я по прежнему жду от вас ответа на все остальные найденные мною ошибки. Напоминаю: доказательство Conclusion 2 (считайте, что G=G' - доказательство будет проще, а случай изоморфных графов из него выводится), доказательство $k_{ij}=k_{r(i)r(j)}$ в лемме 1 (если здесь не подразумевается, что доказательство в notes), обоснование почему можно выбрать r таким, что не только r(l)=m, но и r(m)=l, обоснование равенства $k_{lh}=k_{mr(h)}$ (то, что $k_{lh}=k_{m\sigma(h)}$ для некоторой перестановки $\sigma$ у меня не вызывает сомнений). Слово очевидно в качестве ответа меня не устраивает.

А может мы говорим о разных статьях? Я читаю то, что выложено на архиве. Это могло бы объяснить непонимание. На всякий случай то, как я понимаю Conclusion 2:

Пусть графы G и G' изоморфны. Для любых $i\in G$ и j \in G', если у решений уравнений $A\cdot X=e_i$ и $A'\cdot X'=e'_j$ все координаты различны и есть некоторая перестановка $\sigma$ которая переводит вектор $X$ в $X'$, то соответствующее этой перестановке отображение является изоморфизмом графов G и G'.

В случае если А - обратная к матрице расстояний в графе (тогда X будет равен $A^{-1}\cdot e_i$ - вектор расстояний до вершины i), а ребра в графах имеют длины, я уже привел пример, что это утверждение не верно. Так что это утверждение не тривиально.

-- Сб апр 23, 2011 00:34:08 --

Если у вас есть телефон, skype или jabber-аккаунт (почта на gmail например) - напишите в личку. Общение в реалтайм позволит обсудить все на много быстрее.

[bin]

Да, действительно Вы написали, что граф неориентированный, меня смутили обозначения "1->2" и т.д. Возможно, я немного тороплюсь в своих ответах, но мне хотелось бы быстрее выйти на содержательное обсуждение Для этого мне нужно понять Вашу фразу "Вы ничего не доказали, вы просто утверждаете что это верно" - что именно я не доказал? Утверждение 1 не доказал? И все равно, причем здесь расстояния? Как можно подменять решения моего СЛУ расстояниями? - Вы не ответили.
И далее: "Мало ли что можно выбрать. Факт тот, что утверждение в вашей статье не верно." - Извините! постойте! здесь и тут это определяюще! Если можем выбрать перестановку, для которой $i=r(p)$,$p=r(i)$, то это как раз то, что нужно на данной стадии доказательства! И в чем факт? И откуда Вы взяли, что это не верно? Если Вы и дальше будете по существу полу-фразы писать, а за ними делать громкие обобщения типа "фатальная ошибка" - боюсь, что до содержательного обсуждения мы можем и не дойти. Потрудитесь, пожалуйста, делать более внятные, пусть и менее лаконичные (избыточные) формулировки. А то ведь читаешь и, как учителя не математики, но русского языка говорили на разборах школьных сочинений "непонятно что на ком стояли"

-- Сб апр 23, 2011 00:28:10 --

PS Кстати, Вы зря волнуетесь за рецензентов, последние двое рецензентов не нашли ничего предосудительного ни в Утверждении 1, ни в Лемме 1 - придирки наступили сильно позже. Когда будет время, я здесь об этом подробно расскажу. И еще про рецензентов: Утвержение 1 и выводы из него были одобрены рецензентами Известий РАН и перепечатаны мной почти дословно из указанной в статье публикации (там, если обратите внимание, и сноска стоит).

-- Сб апр 23, 2011 00:37:36 --

PPS Написал ЛС

[bin]

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

На всякий случай то, как я понимаю Conclusion 2:

Пусть графы G и G' изоморфны. Для любых $i\in G$ и j \in G', если у решений уравнений $A\cdot X=e_i$ и $A'\cdot X'=e'_j$ все координаты различны и есть некоторая перестановка $\sigma$ которая переводит вектор $X$ в $X'$, то соответствующее этой перестановке отображение является изоморфизмом графов G и G'.

"2. Если для изоморфных графов при некоторых (i) и (j) решения $X$ и $X'$ систем $A\cdot X=e_i$ и $A'\cdot X'=e'_j$ получаются перестановкой друг друга и имеют все различные координаты (X(k) ≠ X(l), ∀k ≠ l), то соответствующая перестановка координат векторов $X$ в $X'$, дает изоморфизм графов G и G'." -- Изв.РАН, Сер.хим., 2005, 2175.

[upsetter]

bin, понимаете какое дело.
Я совершенно случайно зашел на тот сайт.
Увидел обсуждение Вашей статьи, а я перец такой - я не буду полгода обсуждать (как они)
я просто взял и скачал Вашу демо-прогу. Я чел жутко не ленивый, набросал скрипт под ваш формат,
(Pavia меня знает - я darcus на сорцах.ру и очень редко пишу херню)
Если бы Ваша прога прошла все мои тесты, я бы там так и написал: всё ок на моих тестах!
имеет смысл читать ваше доказательство.
А когда у вас начинаются фри паскаль рулит и т.д. Ну извините.
Я абсолютно уверен что Вы очень таланливый человек, тут и к гадалке не ходи.
Но понимаете всему же есть предел.

[bin]

Упростил алгоритм, исправил ряд ошибок, выложил новую версию препринта:
http://arxiv.org/abs/1004.1808

[whitefox]

Вы, наверно, опять со мной не согласитесь, но в новом варианте статьи Вами фактически учтены все мои замечания.

Введение биграфа $\mathrm{H}$ -- замечательная находка.

Большего пока сказать не могу -- в свободное время изучу Вашу статью внимательно.

[whitefox]

Поясните, пожалуйста, где в вашем алгоритме используется процедура $\textit{Calc2}$ ?

[bin]

whitefox в сообщении #462093 писал(а):

Поясните, пожалуйста, где в вашем алгоритме используется процедура $\textit{Calc2}$ ?

В самый первый листинг (p.7, секция 4, "{1. Find solutions for") вкралась опечатка: вместо Solve нужно Calc2.

whitefox в сообщении #462055 писал(а):

Вы, наверно, опять со мной не согласитесь, но в новом варианте статьи Вами фактически учтены все мои замечания.

Введение биграфа $\mathrm{H}$ -- замечательная находка.

Большего пока сказать не могу -- в свободное время изучу Вашу статью внимательно.

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

[ha]

whitefox
Если вы поймете его статью, то возможно поможете мне убедить автора в бесперспективности этого подхода. Все его попытки можно свести к следующей схеме.

Строим отображение $f$ из графов в матрицы $n\times n$ обладающее следующими свойствами:
1. Для разных графов $G$ и $G'$ значения функции различны: $f(G)\neq f(G')$.
2. Перестановка вершин графа $G$ приводит к такой же перестановке строк и столбцов в матрице $f(G)$.
3. Матрица $f(G)$ симметрична.
4*. У матрицы $f(G)$ элементы на диагонали не совпадают с внедиагональными элементами. (от этого свойства на самом деле можно легко избавится и оно не используется в новой версии автора)

После чего автор предлагает искать соответствие между матрицами $f(G)$ и $f'(G)$ вместо задачи изоморфизма графа. Проблема в том, что его сложное отображение $f(G)=A^{-1} можно заменить на $f(G)=M+2E$, где $M$ - матрица смежности графа, $E$ - единичная матрица. А если избавится от свойства 4, то можно просто брать $f(G)=M$. Но искать соответствие между матрицами смежности, это в точности тоже самое, что и решать исходную задачу об изоморфизме графа. Поэтому его идея, которой он так гордится, не дает ровно ничего. Установить какие-либо дополнительные полезные свойства $f(G)=A^{-1}$ тоже весьма проблематично.

Далее автор пытается использовать простейшие свойства матриц чтобы решить задачу изоморфизма. Если бы это можно было сделать, это давно бы придумали. Но автора это не останавливает.

Конкретную ошибку не сложно увидеть, если рассмотреть случай $f(G)=M$ (т.е. $X=Mb$ в обозначениях статьи). Сперва он сортирует строки матрицы смежности. Отсортированная строка матрицы смежности - это несколько единичек, за которыми следуют нулю. Количество единичек равно степени вершины. Затем выбирается пара вершин $(r,t)$ с совпадающими отсортированными строками, т.е. 2 вершины одинаковой степени. После чего строится двудольный граф $H$ в котором соседи $r$ соединены с соседями $t$, а не соседи $r$ соединены c не соседями $t$.

После чего вызывается процедура removeBadEdges. Она берет ребро $(u,v)$ в графе $H$. После чего проверяется, что для любого ребра $(k,l)$ из $H$ если $u$ сосед $k$, то $v$ сосед $l$ и наоборот.

Если существует изоморфизм $P$ который переводит $r$ в $t$, но не переводит $u$ в $v$, то найдется такое $k$, что либо $u$ и $k$ соседи, а $v$ и $P(k)$ не соседи, либо наоборот $u$ и $k$ не соседи, а $v$ и $P(k)$ соседи. Поскольку ребро $(k,P(k))$ лежит в $H$ (по крайней мере изначально), то такое ребро $(u,v)$ будет выкинуто.

Здесь мы и видим две проблемы. Во-первых, поскольку мы выкидываем ребра из $H$ в процессе выполнения процедуры removedBadEdges, то эти рассуждения могут перестать работать. А во-вторых, мы с легкостью можем выкинуть ребра между подобными вершинами (если бы этой проблемы не было, то первая проблема не была бы проблемой). Ведь если вершины $u$ и $v$ подобны, то может существовать изоморфизм, который не переводит одну в другую, а в таком случае, как мы показали выше, ребро будет выкинуто (если только ребро $(k,P(k))$ между подобными вершинами не будет выкинуто раньше). После чего функция GetSimilar будет работать не правильно (не выдавать подобную вершину, не смотря на то, что она существует) и, как следствие, вся программа будет работать не правильно.

Есть и другие проблемы. К примеру, функция P1 работает не правильно, даже при правильно работающей GetSimilar. Из подобия вершин $i$ и $j$ и похожести разбиений не значит, что можно добавлять $i\rightarrow j$ в map. Это можно делать только на первом шаге. После первого шага мы возможно уже определились с изоморфизмом, а подобные вершины выбранные на втором шаге к нему не подходят. Похожесть разбиений никак не может помочь, поскольку автор ничего существенного про них не доказал.