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

[ha]

Цитата:

Ага! По-Вашему алгоритм Дейкстры модифицируется в алгоритм Флойда — Уоршелла,

Конечно.

Цитата:

т.е. это один и тот же алгоритм поиска кратчайшего пути и сортировка пузырьком тоже модифицируется в эти алгоритмы. И все это один алгоритм! Ну и дела

Если вы делаете столь тривиальную ошибку о том, что если что-то модифицируется, то оно обязано остаться таким же, то как вы собираетесь решать сложную математическую проблему?

-- Пн июл 04, 2011 14:27:28 --

Цитата:

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

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

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

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

-- Пн июл 04, 2011 14:33:39 --

Цитата:

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

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

[ha]

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

(Оффтоп)

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

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

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

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

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

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

Изоморфизм удовлетворяет требованиям map, если для каждой пары вершин i->j в map, он переводит вершину i в j. И почему из того, что я не дал определение следует, что "Вы двух слов связать не можете" мне не понятно. В доказательствах так делать нельзя, но доказательствами у нас вы занимаетесь.

Цитата:

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

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

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

Нет, я не хочу этого сказать. То, что во всем ваше доказательстве можно выбрать любую $f(G)$ удовлетворяющую 3 свойствам, поскольку ничего кроме них не используется - хочу сказать, и уже вроде сказал.

Цитата:

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

Цитата:

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

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

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

Так вы не пользуйтесь тем, что блоки в конце будут с одним элементом в каждом. Но чтобы это увидеть, нужно написать доказательство. Тогда для доказательства того, что найденная перестановка является изоморфизмом нужно будет воспользоваться Утверждением 2. А в Утверждении 2 ничего о блоках (т.е. различности координат векторов) нет.

Цитата:

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

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

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

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

Цитата:

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

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

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

Разъясните, что за "все решения" имеются в виду. Подразумеваете ли вы под словом "разные" неравенство векторов? А может различность координат? И зачем нам единственность перестановки, если мы можем доказать, что она является изоморфизмом - мы можем без нее обойтись.

[bin]

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

Разъясните, что за "все решения" имеются в виду. Подразумеваете ли вы под словом "разные" неравенство векторов? А может различность координат? И зачем нам единственность перестановки, если мы можем доказать, что она является изоморфизмом - мы можем без нее обойтись.

Я же сказал " все решения для каждого графа разные, и они совпадают с точностью до перестановки" - это с очевидностью означает, что все координаты первого вектора решений (для первого графа) разные (нет двух равных координат), и все координаты второго вектора решений (для второго графа) разные, но для каждой координаты первого вектора найдется равная ей координата из второго вектора, т.е. если вектора отсортировать - они окажутся равными.

-- Пн июл 04, 2011 15:27:28 --

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

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

Здесь Вы правы, что этот момент стоит обсудить особо. Прежде всего, нужно восстановить Property 4 из первой версии препринта (мне прислали более четкое доказательство этого свойства). Предварительно отвечу, что при изменении исходного веса вершины $i$ ее вес увеличивается больше всего, далее увеличиваются веса ее соседей, соседей этих соседей (не связанных с $i$) и так по слоям, с удалением от $i$ прирост веса уменьшается, но веса всех вершин графа меняются в сторону увеличения. Для симметричного изменения на подобных вершинах нужно их симметричное расположение к уже рассмотренным соседям. Принимаю советы как это лучше доказать

-- Пн июл 04, 2011 15:32:37 --

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

Так вы не пользуйтесь тем, что блоки в конце будут с одним элементом в каждом. Но чтобы это увидеть, нужно написать доказательство. Тогда для доказательства того, что найденная перестановка является изоморфизмом нужно будет воспользоваться Утверждением 2. А в Утверждении 2 ничего о блоках (т.е. различности координат векторов) нет.

Да, я помню, что Вы присылали мне по email вариант утверждения с разными координатами. Нужно будет добавить. А по новой функции Comp замечаний нет?

[bin]

(Оффтоп)

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

Если вы делаете столь тривиальную ошибку о том, что если что-то модифицируется, то оно обязано остаться таким же,

Цитата:

Модификация — преобразование, усовершенствование, видоизменение чего-либо с приобретением новых свойств. Модификации — качественно различные состояния или разновидности чего-либо.
http://ru.wikipedia.org/w/index.php?tit ... d=31151307

Не надо путать понятия "вид" и "разновидность"! Замену одного алгоритма на другой модификацией называть абсурдно: "выкидываем все что там есть" - в том числе и все видовые признаки, "заменяем на другой" - в том числе на все другие видовые признаки. Полную замену вида модификацией не называют.

[bin]

ha
В отношении перспективности моего подхода у меня есть гораздо более серьезные обоснования, чем те, что Вы мне приписываете. В частности, алгоритмы, о бесперспективности которых пишет Пономаренко, по сути, являются алгоритмами канонизации. Однако проблема канонизации - это отдельная открытая проблема. Очевидно, что если удастся найти ее решение за полиномиальное время, то проблема изоморфизма графов будет решена, однако обратное не очевидно. Мне нужен любой изоморфизм, а не только тот, который удовлетворяет каноническому представлению, такое представление более сильное требование. В моем алгоритме канонизации нет, в этом я вижу одно из обоснований перспективности моего подхода. Следует также учитывать, что данный подход уже зарекомендовал себя для распознавания молекулярных графов при решении сложных задач мат.химии. Например, молекула кунеана может быть представлена регулярным графом с тремя группами неэквивалентных атомов (вершин), эта неэквивалентность обнаруживается в реальной молекуле по константам спин-спинового взаимодействия из спектров ЯМР, и ее обнаруживает P1 анализируя данный граф. При этом в ряде литературных обзоров отмечается, что очень многие способы распознавания графов не видят этих свойств кунеана.

-- Пн июл 04, 2011 22:12:58 --

upsetter

upsetter в сообщении #464922 писал(а):

михаил, присчылайте мне в [e-mail] ЭКЗЕШНИК под виндуя буду проверять - лучшего тестировщика вы хрен найдетеа вообщем мне ваша разработка нравится-- Пн июл 04, 2011 02:23:28 --мож и правда у вас поли-тайм.....я к сожалению небольшой экспертно у меня мой поли-тайм http://funkybee.narod.ru/graphs.htmсчитает Сибирские графы за доли секунды, у вас минуту

Спасибо за нравится. ЭКЗЕШНИК, когда будет готов, выложу на указанном в статье сайте и буду благодарен за тестирование. Но, как ранее отмечалось в этой теме, основная цель данной работы - не сделать быстрый алгоритм, а доказать его "поли-тайм" для всех случаев. Поэтому я не настаиваю на некоторых, сделанных ранее, решениях, если обнаруживается другое, пусть оно будет менее эффективным, но легче доказуемым. Т.о. ЭКЗЕШНИК, возможно, будет не очень скоро. С искренним пожеланием успехов в Вашем решении.

[upsetter]

ЗЫ
Прошу Вас. Михаил, извинить меня
Я все-таки поступил некрасиво - на том форуме - cstheory
Мне надо было писать приватом, Вам напрямую

-- Вт июл 05, 2011 02:45:23 --

я потом очень переживал....
чечстно
думал: ну нахрен я это чсделал?

-- Вт июл 05, 2011 02:48:13 --

я очень много графов проверил на Вашей демо-проге
НИ ОДНОЙ ОШИБКИ!

-- Вт июл 05, 2011 02:50:59 --

я проверил кучу самых страшных регулярных графов на Вашей проге

всё работает как часики

-- Вт июл 05, 2011 03:01:44 --

но мне кажется
это порочный подход - просто изначально - если в GI проблеме числа
у меня простой BFS

Ваше замечание насчет скорости - это я прекрасчно понимаю
Есно не в скорости дело

-- Вт июл 05, 2011 03:08:01 --

почсмотрите как у меня учстроено чсраывнение графоыв
http://funkybee.narod.ru/griso_praust.htm
http://funkybee.narod.ru/griso_siberian.htm

[ha]

upsetter
Не расстраивайтесь. У меня есть примеры графов, где предыдущая программа Михаила не работает.

Этот пример основан на построении двух графов $G_1$ и $G_2$ таких, что у каждого из этих графов все вершины подобны. Кроме того, выполнено следующее свойство. Пусть $v$ - некоторая вершина графа. Сопоставим каждой вершине графа $u$ набор чисел $(uv_1,uv_2,...)$, где $uv_k$ - количество путей (возможно самопересекающихся) длины $k$ между вершинами $u$ и $v$. Далее отсортируем эти вектора (сами вектора, а не числа в них) в лексикографическом порядке. Тогда последовательности этих векторов у графов $G_1$ и $G_2$ совпадут, но при этом сами графы не изоморфны (это кстати было одной из проблем при построении контрпримера - как проверить эту неизоморфность, если даже такой сильный инвариант не работает? Пришлось писать перебор, который, к счастью, закончился достаточно быстро).

Если существование таких графов опровергает ваш алгоритм, то он не верен.

-- Вт июл 05, 2011 21:01:39 --

Ваша программа правильно их распознает.
Для не изоморфных:
1) n = 36 NONisomorphic ** 0.075
Для изоморфных:
1) n = 73 + 14.894
Как-то многовато.

Вообще BFS должен быть правильным, но слишком долгим в специальных случаях. Так что не понятно какие контрпримеры вы ищите.

[ha]

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

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

Разъясните, что за "все решения" имеются в виду. Подразумеваете ли вы под словом "разные" неравенство векторов? А может различность координат? И зачем нам единственность перестановки, если мы можем доказать, что она является изоморфизмом - мы можем без нее обойтись.

Я же сказал " все решения для каждого графа разные, и они совпадают с точностью до перестановки" - это с очевидностью означает, что все координаты первого вектора решений (для первого графа) разные (нет двух равных координат), и все координаты второго вектора решений (для второго графа) разные, но для каждой координаты первого вектора найдется равная ей координата из второго вектора, т.е. если вектора отсортировать - они окажутся равными.

Фух, а то мне на секунду показалось, что вы на правильном пути к доказательству того, что если в P1 выполнено n итераций, то конечная перестановка является изоморфизмом (для этого правда нужно подправить P1). Ваше же разъяснение показывает, что это не так.

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

Цитата:

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

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

Здесь Вы правы, что этот момент стоит обсудить особо. Прежде всего, нужно восстановить Property 4 из первой версии препринта (мне прислали более четкое доказательство этого свойства). Предварительно отвечу, что при изменении исходного веса вершины $i$ ее вес увеличивается больше всего, далее увеличиваются веса ее соседей, соседей этих соседей (не связанных с $i$) и так по слоям, с удалением от $i$ прирост веса уменьшается, но веса всех вершин графа меняются в сторону увеличения. Для симметричного изменения на подобных вершинах нужно их симметричное расположение к уже рассмотренным соседям. Принимаю советы как это лучше доказать

Что доказать? То, что для симметричного изменения на подобных вершинах нужно их симметричное расположение к уже рассмотренным соседям скорее всего не верно. Ничто не мешает двум подобным вершинам иметь одинаковые расстояния до уже рассмотренных и тем не менее располагаться не симметрично. Конкретный пример лучше всего искать среди графов, у которых все вершины подобны - тогда условие подобия вершин не накладывает никаких ограничений. Остается найти такой граф, что у него в решении случайно окажутся две совпадающих координаты для вершин расположенных не симметрично относительно той, для которой мы взяли решение.

Кстати, если брать $f(G)=M$, то никаких сложных доказательств того, что решение убывает с расстоянием не нужно - оно просто сразу становится нулем. А если так нужно доминирование диагонали - можно добавить $2E$.

Цитата:

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

Так вы не пользуйтесь тем, что блоки в конце будут с одним элементом в каждом. Но чтобы это увидеть, нужно написать доказательство. Тогда для доказательства того, что найденная перестановка является изоморфизмом нужно будет воспользоваться Утверждением 2. А в Утверждении 2 ничего о блоках (т.е. различности координат векторов) нет.

Да, я помню, что Вы присылали мне по email вариант утверждения с разными координатами. Нужно будет добавить. А по новой функции Comp замечаний нет?

Так не нужно утверждению 2 различность координат. Поэтому и бороться за него не имеет смысла.

Новую функцию Comp я не смотрел. Никаких ссылок на свойства $f(G)$ за исключением указанных 3 там не видно. Поэтому ни что не мешает вам ее реализовать для $f(G)=M$ или $f(G)=E+D-M$, где $D$ - диагональная матрица со степенями вершин (тогда будет выполняться столь любимое вами свойство, что вектор из единиц переходит в вектор из единиц). После чего вы сможете сами протестировать ее на небольших графах и увидеть все ошибки. Вникать в новый вариант при условии, что вы его еще не проверили даже на всех графах с <=7 (а еще лучше 8, если сможете) вершинами мне пока что-то не хочется. Тем более, что никакой длинной арифметики для указанных $f(G)$ не надо.

Именно подстановкой простых $f(G)$ я нахожу ошибки в ваших доказательствах, так почему бы вы вам не попробовать этот прием для их проверки?

[bin]

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

Фух, а то мне на секунду показалось, что вы на правильном пути к доказательству того, что если в P1 выполнено n итераций, то конечная перестановка является изоморфизмом (для этого правда нужно подправить P1)

И как по-Вашему "нужно подправить P1"?

[upsetter]

ha писал(а):

Ваша программа правильно их распознает.

Для не изоморфных:
1) n = 36 NONisomorphic ** 0.075
Для изоморфных:
1) n = 73 + 14.894
Как-то многовато.

Вообще BFS должен быть правильным, но слишком долгим в специальных случаях. Так что не понятно какие контрпримеры вы ищите.

Дело в том что:

1.
У меня тоже поли-тайм алгоритм. Собсно в этом его соль.

2.
Изоморфные пары графов моим алгоритмом можно не проверять - ответ неизбежно будет правильным.

3.
Контр-пример мне нужен вот какой:
найти два неизоморфных графа для которых мой алгоритм скажет что они изоморфны.
Я 3 месяца искал - не нашел.

-- Вт июл 05, 2011 22:59:48 --

Эдуард Игоревич Ватутин ( http://evatutin.narod.ru ),
автор статьи "Изоморфизм графов" в Википедии.ру, проверил очень много графов моим алгоритмом:
http://evatutin.livejournal.com/12588.html

-- Вт июл 05, 2011 23:42:02 --

У Джона-Тагора Тевета, эстонца, который сделал поли-тайм для сабжа, вместе с индийцем
( see : http://graphs.ee )
так у них их демо-прога Сибирские графы дождаться ответа невозможно
Я через час снял задачу

Я у него приватом спрашивал: почему нет отклика в мире?
Он почему-то ничего не ответил (а мы в хороших с ним отношениях, ему кстати 80 (!) лет)

[ha]

Построил контрпример. Берем 100 точек на окружности и одну в центре. Соединяем соседние точки на окружности и центральную со всеми.
Теперь в графе $G_1$ дополнительно соединяем точки на окружности на расстоянии 9 (т.е. $i$ и $i+9\pmod {100}$ где $i=0,\dots,99$).
В графе $G_2$ дополнительно соединяем точки на окружности на расстоянии 11.
Программа выдает
1) n = 101 + 64.374
Хотя графы не изоморфны. Увеличение количества звездочек не поможет.

[bin]

Уважаемые коллеги!
Эта тема была открыта для обсуждения конкретного подхода, но не всех возможных подходов к проблеме GI. Почему бы вам не сделать отдельную тему для таких обсуждений?

[upsetter]

ну тады всё.... я навсегда завязываю с этой темой
ha, спасибо

-- Ср июл 06, 2011 00:54:53 --

ha, если Вам не трудно,
пришлите мне на [e-mail] любую контр-примерную пару
в моем формате, 2 матрицы смежностей

[upsetter]

ЗЫ
Дело в том что я разбил свой алгоритм на 3 функции
просто чтоб быстрее считало, а на самом деле это неважно
У меня есть тайная модификация
Я ее отослал Эдуарду Ватутину
Если вы пришлите мне письмо - я и вам ее отошлю
а вобщем..... бесполезняк

[upsetter]

ha,
без обид, но Вы мне прислали изоморфные графы
Т.е. контр-примера под мой алгоритм я пока не встретил