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

[whitefox]

2ha

(Оффтоп)

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

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

Я ещё в прошлый раз убедился в бесперспективности любой попытки переубедить автора.

2bin
Поясните, пожалуйста, из чего следует следующее утверждение:

Цитата:

So, in the result of removeBadEdges we have only edges in H,
which edges connect similar vertices.

[bin]

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

ha

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

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

Я ещё в прошлый раз убедился в бесперспективности любой попытки переубедить автора.

whitefox
В прошлом сообщении Вы написали обратное - что в новом варианте статьи фактически все Ваши замечания учлись. А до того я довольно быстро согласился с Вашим замечанием в отношении опечатки в вызове GrtSimilar. Т.о. Ваше замечание про любую попытку - выглядит а) как переход на личности б) как "флюгерная дипломатия".

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

2bin
Поясните, пожалуйста, из чего следует следующее утверждение:

Цитата:

So, in the result of removeBadEdges we have only edges in H,
which edges connect similar vertices.

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

-- Пт июл 01, 2011 20:26:43 --

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

Конкретную ошибку не сложно увидеть, если рассмотреть случай (т.е. в обозначениях статьи). Сперва он сортирует строки матрицы смежности. Отсортированная строка матрицы смежности - это несколько единичек, за которыми следуют нулю.

ha
За те несколько месяцев, что мы с Вами интенсивно переписываемся - по нескольку email за день, Вы мне успели все уши прожужжать, как следует проверять и перепроверять свои сообщения. Но вот Вы пишете уже не только мне, а на форум и написали "за которыми следуют нулю"! Так-то Вы проверяете свои собственные сообщения. Но и по сути, а не только по форме, это Ваше сообщение выглядит не менее лихим. Где это Вы углядели у меня "отсортированную строку матрицы смежности" (сначала единички,в сумме дающие степень вершины, а далее "следуют нулю" ;) ? Мой алгоритм различает вершины регулярных графов, а тот, что Вы мне приписывате, различать не будет. Но это "частности", а если посмотреть с наиболее общих позиций, то граф с точностью до изоморфизма представляется своей матрицей смежности, и, поэтому, все графовые алгоритмы основаны на этой матрице и иного быть не может. Т.е., по Вашей логике получается, что все подходы к решению задачи изоморфизма графов бесперспективны, т.к. они неизбежно будут использовать матрицу смежности и ее элементарные свойства. Напомню, что в нашей приватной переписке, мы с Вами уже обсуждали этот вопрос, и я тогда отметил исследования, где по целым классам алгоритмов изоморфизма доказываются оценки для наихудшего случая, и т.о. показано, что выше головы эти алгоритмы прыгнуть не смогут, как их ни модифицируй. Примером одной из таких работ может служить статья известного специалиста по проблеме изоморфизма графов Ильи Пономаренко из Питера: A. Rahnamai Barghi, I. Ponomarenko, Non-isomorphic graphs with cospectral symmetric powers, Electronic Journal of Combinatorics, http://www.combinatorics.org/Volume_16/ ... i1r120.pdf Вы ответили, что Вам жалко времени. Возможно, Вы правы и времени на такое доказательство о бесперспективности действительно тратить не стоит (т.к. ничего не получится), но и не надо, в таком случае, подменять строгое доказательство тем, что кажется правдоподобным, о чем Вы мне, тоже, не так давно писали. Про removeBadEdges я уже ответил выше. Отмечу только, что именно такой критики с анализом я от Вас и добивался и наконец услышал (можете, когда хотите). А так Вы обычно ограничиваетесь "здесь неверно" и точка. А что и почему неверно? - полное молчание. Отмечу также, раз Вам захотелось вернуть наше обсуждение из приватной переписки на форум, что Вам также не приходится обижаться на меня за то, что я не прислушиваюсь к Вашим советам. В последней версии препринта очень прислушался и поблагодарил Вас в списке благодарностей.

Да, и последнее: Ваше утверждение "P1 работает не правильно, даже при правильно работающей GetSimilar" выглядит пока только правдоподобным, и то только для Вас. Нужно более строгое обоснование!

[whitefox]

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

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

Рад, что ошибался.

[ha]

Когда троллю не к чему придираться, он придирается к опечаткам.

Цитата:

Где это Вы углядели у меня "отсортированную строку матрицы смежности"

У меня все написано. "Конкретную ошибку не сложно увидеть, если рассмотреть случай $f(G)=M$". Сортировка чисел в строке выполняется в первых же строчках вашего алгоритма. Матрица, к которой применяется сортировка чисел - это $f(G)$.

Цитата:

они неизбежно будут использовать матрицу смежности и ее элементарные свойства.

Они используют весьма не элементарные свойства этой матрицы, теоремы математики и подходы к доказательству.

Цитата:

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

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

Заметьте, что в указанной вами работе, ни о каком классе алгоритмов не идет речи. Там рассматривается ровно один алгоритм - "two graphs are isomorphic if and only if their m-th symmetric powers are cospectral".

Цитата:

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

Модифицируем алгоритм - выкидываем все что там есть, заменяем на другой. Так что там разрешены далеко не любые модификации. Думаю, что не очень сложно модифицировать любой алгоритм, чтобы он вышел за рамки любой из подобных теорем. Но это не делает любой подход перспективным.

Цитата:

подменять строгое доказательство тем, что кажется правдоподобным

Никакой подмены нет. Утверждение о перспективности или бесперспективности какого-либо подхода математическим не является. Это автоматически означает что оно может являться лишь правдоподобным. Соответственно только вам могло показаться, что я имею в виду, что оно мною строго доказано на языке математики. Или может людям нужно перестать писать предложения которые не являются математическими утверждениями?

Цитата:

Нужно более строгое обоснование!

Доказывать утверждение являющееся отрицанием вашего я не обязан.

Обоснование правильности работы P1 полностью отсутствует. Это достаточное основание, чтобы требовать его доказательства. Добавьте его в статью. Желательно в виде отдельной теоремы. Ведь это сам по себе важный результат - полиномиальный алгоритм нахождения изоморфизма, при условии, что у нас есть оракул, позволяющий определить подобие вершин (или подобие вершин при условии, что $r$ переходит в $t$). Вот если у нас есть оракул, позволяющий определить подобие вершин при условии, что изоморфизм удовлетворяет требованиями map - то это общеизвестно. Никаких линейных уравнений для этого не надо:

function P1(G,G'):TMap;
var
  map:TMap;
  i,j:integer;
begin
  map:=empty map;
  for i:=1 to n do
  begin
    j:=FindSimilarWithMapRestriction(G,G',i,map);
    map.add(i->j);
  end;
  P1:=map;
end;

Пользуйтесь на здоровье.

[bin]

Что такое опечатка? Это тривиальная ошибка. Распространенность опечаток показывает, что ошибки неизбежны и наличие даже тривиальных ошибок не дает оснований для вывода о бесперспективности подхода. "Конкретную ошибку не сложно увидеть, если рассмотреть случай $f(G)=M$" - Вы берете вырожденный случай, неэквивалентный моему подходу. У меня действия производятся над весами вершин, при этом веса имеют такое свойство, что изменение начального веса одной лишь вершины вызывает изменение весов всех вершин - от центра до самых до окраин. Разве это свойство - элементрарное свойство матрицы смежности? Разве любые $f(G)$ будут вести себя подобным образом? Именно благодаря свойствам, избранным для данного подхода весов, и возможен итеративный процесс по последовательному измельчению блоков разбиения. Перебирая подобные вершины, P1 выбирает пару, которая вызывает одинаковые изменения всех весов при изменении весов этой пары. В итоге мы получаем все разные веса для вершин каждого графа, причем соответствующие пары весов (вершина из одного - вершина из другого) совпадают. Т.о. воможна единственная перестановка для Утверждения 1 и эта перестановка будет изоморфизмом. Все это написано в статье.

-- Сб июл 02, 2011 14:55:04 --

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

Утверждение о перспективности или бесперспективности какого-либо подхода математическим не является. Это автоматически означает что оно может являться лишь правдоподобным.

1) Не только математические утверждения доказываются. 2) Есть множество примеров, когда бесперспективность доказывается математически. Например, известны публикации, в которых для решения проблемы изоморфизма в задачах мат.химии предлагалось использовать индекс Хосойа. Однако все способы его расчета экспоненциальны по времени, более того, уже для графов в шесть вершин существуют неизоморфные с одинаковым индексом. Следовательно, его использование для данной задачи бесперспективно.

-- Сб июл 02, 2011 15:02:43 --

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

Модифицируем алгоритм - выкидываем все что там есть, заменяем на другой. Так что там разрешены далеко не любые модификации.

Зачем доходить до очевидного абсурда? Совершенно очевидно, что такая замена одного алгоритма на другой модификацией не называется.

[bin]

Функцию $Compare$ необходимо изменить. Публикую следующую черновую идею в порядке обсуждения. Есть $n$ решений для $n$ линейно независимых векторов для каждого из двух данных изоморфных графов:

$$ X[1],...,X[n]$$

$$ X'[1],...,X'[n]$$

Отсортируем каждое из решений:

$$ Xs[1],...,Xs[n]$$

$$ Xs'[1],...,Xs'[n]$$

причем при сортировке будем запоминать первоначальные индексы координат. Функция $index$ будет возвращать значения индекса в отсортированном векторе для указанной координаты, соответствующей номеру вершины. Для пары подобных вершин $(r,t)$: $Xs[r]=Xs'[t]$. Строим биграф $H_{0}$, в котором, первое множество вершин - вершины первого графа, второе - вершины второго и если $Xs[r,index(i)]=Xs'[t,index(j)]$, то строим ребро $(i,j)$ в этом биграфе. Очевидно, что число ребер биграфа $H_{0}$ не будет превосходить $n^{2}$. Для каждого из этих ребер $(i,j)$, если $Xs[i]=Xs'[j]$, то строим биграф $H_{ij}$, в котором, если $Xs[i,index(p)]=Xs'[j,index(q)]$, то строим в нем ребро $(p,q)$. Множества ребер для каждого из этих биграфов обозначим соответственно $E_{ij}$, а $E_{0}$ множество ребер графа $H_{0}$. Рассмотрим пересение этих множеств:

$$ E=E_{0}\bigcap E_{ij}$$

Если найдется вершина $k$, не имеющая ребер в множестве $E$, то будем называть такое множество неподходящим. Очевидно, что для неподходящего множества невозможно найти решений, удовлетворяющих Утверждению 3. Поэтому если множество ребер биграфа $H_{ij}$ образует при пересечении с множеством ребер биграфа $H_{0}$ неподходящее множество, то будем удалять биграф $H_{ij}$ из дальнейшего рассмотрения и ребро $(i,j)$ из $H_{0}$. Очевидно также, что если после такого удаления множество $E_{0}$ окажется неподходящим, то пара вершин $(r,t),$ по которой строился биграф $H_{0}$, окажется парой неподобных вершин. Если пересечение $E$ всех множеств, принятых к дальнейшему рассмотрению

$$ E=(\bigcap_{(ij)}E_{ij})\bigcap E_{0}$$

не будет неподходящим, то для всех $i,j,p,q$ существуют соответствия $i\leftrightarrow j$, $p\leftrightarrow q,$ для которых $Xs[i,index(p)]=Xs'[j,index(q)]$ и, согласно Утверждению 3, пары $i\leftrightarrow j$, $p\leftrightarrow q$ дадут изоморфизм графов, а значит, в $E$ будут ребра, соединяющие только подобные вершины. Как было отмечено выше, число ребер $H_{ij}$ не превосходит $n^{2}$, следовательно, число биграфов $H_{ij}$ не превосходит $n^{2}$. Построение каждого биграфа имеет полиномиальную вычислительную сложность. Следовательно, множество $E$ может быть найдено за полиномиальное время.

[arseniiv]

(Оффтоп)

Вы не пробовали писать названия функций прямым шрифтом?

[bin]

(Оффтоп)

arseniiv в сообщении #464341 писал(а):

Вы не пробовали писать названия функций прямым шрифтом?

Спасибо за совет. А почему? Так понятнее? Или правило какое оформительское существует?

[arseniiv]

(Оффтоп)

Мне кажется, так удобнее читать. Всё-таки принято, что курсивные буквы каждая «сама за себя», а названия функций ещё и являются частями кода, который набирается обычно не курсивом.

[caxap]

(Оффтоп)

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

Или правило какое оформительское существует?

Не оформительское, а типографическое
Просто курсивный шрифт отдан под однобуквенные переменные. Это удобное соглашение, позволяющее не писать постоянно значки умножения: $index=i\cdot n\cdot d\cdot e\cdot x$. Если же вам имеете в виду цельное имя "index", то его следует писать $\mathrm{index}$. Ср. также $\sin x$ и $sin x=s\cdot i\cdot n\cdot x$.

[bin]

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

Заметьте, что в указанной вами работе, ни о каком классе алгоритмов не идет речи. Там рассматривается ровно один алгоритм - "two graphs are isomorphic if and only if their m-th symmetric powers are cospectral".

Цитата:

Во всех проанализированных случаях (см. обзор [17] и недавнюю работу [32]) оказалось, что когерентная конфигурация, получающаяся на выходе алгоритма, мажорируется когерентной конфигурацией, которая за то же время строится m-мерным алгоритмом Вейсфейлера-Лемана для подходящего m. Однако в этом случае, надежда на то, что построенный алгоритм проверяет изоморфизм графов за полиномиальное время, является несостоятельной в силу теоремы 5.10.

И.Н. Пономаренко, Проблема изоморфизма графов: Алгоритмические аспекты (записки к лекциям), С.54, http://logic.pdmi.ras.ru/csclub/sites/d ... _notes.pdf
[32] -- указанная ранее работа.

-- Сб июл 02, 2011 17:15:12 --
caxap

(Оффтоп)

caxap в сообщении #464352 писал(а):

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

Или правило какое оформительское существует?

Не оформительское, а типографическое
Просто курсивный шрифт отдан под однобуквенные переменные. Это удобное соглашение, позволяющее не писать постоянно значки умножения: $index=i\cdot n\cdot d\cdot e\cdot x$. Если же вам имеете в виду цельное имя "index", то его следует писать $\mathrm{index}$. Ср. также $\sin x$ и $sin x=s\cdot i\cdot n\cdot x$.

Разумно! Спасибо - в будущем обязательно учту.

[ha]

Цитата:

Что такое опечатка? Это тривиальная ошибка. Распространенность опечаток показывает, что ошибки неизбежны и наличие даже тривиальных ошибок не дает оснований для вывода о бесперспективности подхода.

Я имею в виду ошибки в логических выводах. Если вы у вас половина выводов не верны, то вам не стоит заниматься математикой.

Цитата:

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

Конечно. Называется элементы $f(G)$ отличны от нуля. Если вы укажете где без него нельзя обойтись, то я выберу $f(G)=M+E_1$, где $E_1$ - матрица в которой все элементы равны 1.

Цитата:

Разве любые будут вести себя подобным образом? Именно благодаря свойствам, избранным для данного подхода весов, и возможен итеративный процесс по последовательному измельчению блоков разбиения.

Вы говорите, что его используйте, а на самом деле нигде им не пользуйтесь. Поэтому можно рассматривать $f(G)=M$.

Цитата:

Перебирая подобные вершины, P1 выбирает пару, которая вызывает одинаковые изменения всех весов при изменении весов этой пары.

Выбрали. Нам даже известно, что они подобны.

Цитата:

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

А это не верно. На каком-нибудь этапе может не найтись ни одной пары, хотя графы изоморфны. Просто потому, что мы набрали в map вершин так, что никакого изоморфизма нет. Для каждой пары он есть, а для всех вместе - нет.

Цитата:

Т.о. воможна единственная перестановка для Утверждения 1 и эта перестановка будет изоморфизмом.

Из Утверждения 1 нельзя сделать вывод что какая-то перестановка является изоморфизмом. Оно этого требует.

Цитата:

Все это написано в статье.

Укажите номер теоремы.

-- Сб июл 02, 2011 21:36:47 --

Цитата:

1) Не только математические утверждения доказываются. 2) Есть множество примеров, когда бесперспективность доказывается математически. Например, известны публикации, в которых для решения проблемы изоморфизма в задачах мат.химии предлагалось использовать индекс Хосойа. Однако все способы его расчета экспоненциальны по времени, более того, уже для графов в шесть вершин существуют неизоморфные с одинаковым индексом. Следовательно, его использование для данной задачи бесперспективно.

Почему это? Не доказано, что нет полиномиальных алгоритмов вычисления этого индекса. Вдруг он найдется? $P\neq NP$ ведь еще не доказали. А так же вдруг можно добавить еще один индекс и контрпримеров больше не будет? Например собственные значения графа. Так что никакого "следовательно" сделать нельзя.

Цитата:

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

Модифицируем алгоритм - выкидываем все что там есть, заменяем на другой. Так что там разрешены далеко не любые модификации.

Зачем доходить до очевидного абсурда? Совершенно очевидно, что такая замена одного алгоритма на другой модификацией не называется.

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

[bin]

(Оффтоп)

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

Я имею в виду ошибки в логических выводах. Если вы у вас половина выводов не верны, то вам не стоит заниматься математикой.

C тем же успехом мог бы сказать, что если Вы двух слов связать не можете, то Вам не стоит ничего писать и не только по математике, но и, например, по филологии ;-) Вот Вы написали:

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

что изоморфизм удовлетворяет требованиями map

Ведь ничего же не понятно, кто кого и чем удовлетворяет. И это не придирка, т.к. на лицо полная неуловимость смысла. Либо изоморфизм удовлетворяет требованиЯМ map, но тогда какие там требования - map пассивно формируется в ходе работы процедуры? Либо изоморфизм удовлетворяется требованиЯМИ map? А может требования к map удовлетворяются изоморфизмом? Явный ребус. И это только один пример Вашей железной логики изложения. Однако несмотря на столь своеобразное изложение, я не говорю Вам "прекратите писать, что-либо" и поддерживаю с Вами диалог, и более того пытаюсь все время направить его в конструктивное русло :-)

-- Сб июл 02, 2011 22:25:41 --

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

Конечно. Называется элементы отличны от нуля. Если вы укажете где без него нельзя обойтись, то я выберу , где - матрица в которой все элементы равны 1.

Долго думал над этим заявлением, но так и не понял. Вы хотите сказать, что любые ненулевые элементы матрицы можно заменять единичками? В матрице расстояний, например? Может, мне кто из читателей объяснит?

-- Сб июл 02, 2011 22:30:35 --

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

Цитата:

Разве любые будут вести себя подобным образом? Именно благодаря свойствам, избранным для данного подхода весов, и возможен итеративный процесс по последовательному измельчению блоков разбиения.

Вы говорите, что его используйте, а на самом деле нигде им не пользуйтесь. Поэтому можно рассматривать

Как это не пользуюсь?! Разбиения измельчаются вплоть до блоков с одним элементом в каждом.

-- Сб июл 02, 2011 22:53:03 --

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

А это не верно. На каком-нибудь этапе может не найтись ни одной пары, хотя графы изоморфны. Просто потому, что мы набрали в map вершин так, что никакого изоморфизма нет. Для каждой пары он есть, а для всех вместе - нет.

Да, две подобных вершины могут дать несовпадение решений, если их положение по отношению к уже рассмотренным соседям не симметрично, но мы формируем map последовательно, и там производится проба на шаг вперед (см. комментарий "save old value" в листинге P1), если проба привела к несовпадающему решению, процедура ищет другое для данного шага.

-- Сб июл 02, 2011 23:03:17 --

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

Из Утверждения 1 нельзя сделать вывод что какая-то перестановка является изоморфизмом. Оно этого требует.

Если графы изоморфны, и все решения для каждого графа разные и они совпадают с точностью до перестановки, то эта перестановка 1) единственная 2) является изоморфизмом. Если графы не изоморфны и все решения для каждого графа разные и они совпадают с точностью до перестановки, то процедура Verify покажет, что данная перестановка не изоморфизм, т.к. других перестановок нет, то отсюда следует подтверждение, что графы не изоморфны.

-- Сб июл 02, 2011 23:06:50 --

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

Укажите номер теоремы.

Как теорема не оформлено.

-- Сб июл 02, 2011 23:11:20 --

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

Почему это? Не доказано, что нет полиномиальных алгоритмов вычисления этого индекса. Вдруг он найдется? $P\neq NP$ ведь еще не доказали. А так же вдруг можно добавить еще один индекс и контрпримеров больше не будет? Например собственные значения графа. Так что никакого "следовательно" сделать нельзя.

Ok. Пока не доказано, что $P= NP$, его использование для данной задачи бесперспективно

[bin]

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

Вполне себе в математике называется. Такие у нас порядки.

Ага! По-Вашему алгоритм Дейкстры модифицируется в алгоритм Флойда — Уоршелла, т.е. это один и тот же алгоритм поиска кратчайшего пути и сортировка пузырьком тоже модифицируется в эти алгоритмы. И все это один алгоритм! Ну и дела

[upsetter]

михаил, присчылайте мне в [e-mail] ЭКЗЕШНИК под винду
я буду проверять - лучшего тестировщика вы хрен найдете
а вообщем мне ваша разработка нравится

-- Пн июл 04, 2011 02:23:28 --

мож и правда у вас поли-тайм.....
я к сожалению небольшой эксперт
но у меня мой поли-тайм http://funkybee.narod.ru/graphs.htm
считает Сибирские графы за доли секунды, у вас минуту

-- Пн июл 04, 2011 02:24:52 --

зы
Сибирские - это №9 (40 вершин)

-- Пн июл 04, 2011 02:49:48 --

Миша, извините меня за некоторый пиар в вашем топике
http://sourceforge.net/projects/griso/files/
но если кто меня разоблачит - я буду только рад
Я 3 месяца продолбался в поисках контр-примера

-- Пн июл 04, 2011 02:53:40 --

ЗЫ
формат входа как в левыой полоывине http://funkybee.narod.ru/graphs.htm
пары графоыв, один за другим

ЗЗЫ
ЧСорри, жутко глючит клавыа