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

[Toucan]

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

[bin]

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

Новую функцию Comp я не смотрел. [...] Вникать в новый вариант при условии, что вы его еще не проверили даже на всех графах с <=7 (а еще лучше 8, если сможете) вершинами мне пока что-то не хочется.

Я уже рекомендовал Вам книгу Лакатос И. Доказательства и опровержения. Как доказываются теоремы. — М.: Наука, 1967. В ней подробно показано, как должно идти обсуждение. Если Вы выступаете в роли проверяющего так и давайте конкретные замечания, а не пытайтесь загрузить меня объемной рутинной работой. Тем более, что нужен не столько контрпример, сколько замечания на теоретическом уровне.

[ha]

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

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

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

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

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

[upsetter]

так-с, исправляюсь
У Михаила его прога работает просто на ура, кроме шуток
Ну очень много чего я проверил на ней
И мне вот кажется

[ha]

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

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

Новую функцию Comp я не смотрел. [...] Вникать в новый вариант при условии, что вы его еще не проверили даже на всех графах с <=7 (а еще лучше 8, если сможете) вершинами мне пока что-то не хочется.

Я уже рекомендовал Вам книгу Лакатос И. Доказательства и опровержения. Как доказываются теоремы. — М.: Наука, 1967. В ней подробно показано, как должно идти обсуждение. Если Вы выступаете в роли проверяющего так и давайте конкретные замечания, а не пытайтесь загрузить меня объемной рутинной работой. Тем более, что нужен не столько контрпример, сколько замечания на теоретическом уровне.

Я уже несколько десятков ваших доказательств с помощью подстановки $f(G)=M$ опроверг --- так почему же вы не хотите сделать этой проверки? К тому же, она дает в любом случае упрощение алгоритма. Разве совершение одной и той же ошибки доказывающим входит в то, как должно идти обсуждение по Лакатосу?

[bin]

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

Разве совершение одной и той же ошибки доказывающим входит в то, как должно идти обсуждение по Лакатосу?

Если доказывающий делает одну и ту же ошибку - это может означать, что проверяющий не сумел четко объяснить в чем ошибка. Как в школе: если ученики не умеют сокращать дроби, скорее всего, сам учитель путается в сокращении дробей ;) Объясните столь же четко, как делают у Лакатоса, и не будет проблем.

-- Ср июл 06, 2011 22:09:31 --

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

так-с, исправляюсь
У Михаила его прога работает просто на ура, кроме шуток
Ну очень много чего я проверил на ней
И мне вот кажется

Спасибо! :)

-- Ср июл 06, 2011 22:11:53 --

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

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

У меня уже несколько исправлений, но мне интересно: какое выбрали Вы?

-- Ср июл 06, 2011 22:16:06 --

PS ha, я все жду от Вас конструктивных идей, а не только огульной критики

-- Ср июл 06, 2011 22:28:13 --

PPS Занимаясь поисками решения задачи GI, может и неразрешимой, мы в то же время совершенствуем наши индексы, повышая их дискриминирующую способность. Возможно, если не GI в целом, то некоторые подзадачи мы решим. Так ha верно отметил: "Ведь это сам по себе важный результат - полиномиальный алгоритм нахождения изоморфизма, при условии, что у нас есть оракул, позволяющий определить подобие вершин". А вообще, спрос на хорошие индексы в "прикладухе" оч. большой

[upsetter]

Я вот думаю...
Михаил Трофимов допилит свой алгоритм.... а у кого багов не бывает?
У всех баги бывают
Потом вы еще увидите

Я потом оттестирую его по полной программе

[whitefox]

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

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

Как уже отметил ha, даже при наличии подобного оракула, Ваша процедура P1 работает некорректно.

[bin]

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

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

Что-то не получается найти такой граф. Обязательно какая-то из вершин (необязательно выбранных) "чувствует" иное расположение. М.б. P1 стоит заменить на следующую процедуру: выбираем вершину первого графа, перебираем подобные ей вершины: для каждой такой пары вычисляем $n$ векторов с начальными весами $e_i+b$, где $b$ - начальные веса для выбранных вершин, и вызываем функцию comp. Но прежде чем обсуждать такую модификацию, стоило бы обсудить comp. Что там не так?

[whitefox]

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

М.б. P1 стоит заменить на следующую процедуру: выбираем вершину первого графа, перебираем подобные ей вершины: для каждой такой пары вычисляем $n$ векторов с начальными весами $e_i+b$, где $b$ - начальные веса для выбранных вершин

Оракул, вызываемый в процедуре P1, получает на вход вершину $i$ графа $G$ и некоторое подмножество вершин $\mathfrak{U}_k'$ графа $G'$. Ему ничего не известно об уже построенном частичном отображении $map$ и, поэтому, выданная им вершина $j'$ может этому отображению не соответствовать. Добиться такого соответствия это уже задача процедуры P1. В этом направлении её и нужно изменить.

[ha]

Цитата:

Что-то не получается найти такой граф. Обязательно какая-то из вершин (необязательно выбранных) "чувствует" иное расположение.

А вы $f(G)=M$ попробуйте.

[bin]

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

Цитата:

Что-то не получается найти такой граф. Обязательно какая-то из вершин (необязательно выбранных) "чувствует" иное расположение.

А вы $f(G)=M$ попробуйте.

Пробовал. Наверное, я как-то не так пробую?

[ha]

Попробуйте запустить алгоритм на кольце из $n\ge 8$ вершин. Чем больше $n$, тем меньше вероятность (при случайном и равновероятном выборе нумерации вершин кольца), что он при $f(G)=M$ сработает правильно. Ведь вершина влияет только на двух своих соседей.

[bin]

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

Попробуйте запустить алгоритм на кольце из $n\ge 8$ вершин. Чем больше $n$, тем меньше вероятность (при случайном и равновероятном выборе нумерации вершин кольца), что он при $f(G)=M$ сработает правильно. Ведь вершина влияет только на двух своих соседей.

А те влияют на своих соседей

-- Пт июл 08, 2011 16:00:01 --

Множество вершин каждого графа можно разбить однозначным образом на семейства подобных вершин, где каждая вершина подобна всем вершинам своего семейства и неподобна вершинам других семейств того же графа. Очевидно, что любая вершина подобна самой себе, т.о. может быть семейство, состоящее только из одной вершины. Вершина из одного семейства неподобна вершинам из других семейств, т.о. каждая вершина графа входит только в одно семейство. Для двух изоморфных графов существует однозначное соответствие между семействами их вершин. Если для вершин $i,j$ графа $G$ и вершин $i',j'$ графа $G'$ отображения $i\leftrightarrow i'$, $j\leftrightarrow j'$ входят в какой-либо изоморфизм (графы изоморфны), то вершины $i,j$ могут принадлежать к одному семейству или к двум разным семействам графа $G$, а вершины $i',j'$ принадлежат к одному или двум соответствующим семействам графа $G'$. В любом случае для любого пути между вершинами $i,j$ найдется такой же путь между вершинами $i',j'$, причем соответствующие вершины из этого пути в графе $G$ будут принадлежать к тем же семействам, что и в графе $G'$, более того, для любого подграфа, в который входит такой путь в графе $G$, можно найти такой же подграф в графе $G'$, и все вершины одного подграфа будут соответствовать (в том числе и по принадлежности к семействам) вершинам другого подграфа. Назовем такие подграфы подобными фрагментами между данной парой вершин. Если отображения $i\leftrightarrow i'$, $j\leftrightarrow j'$ входят в какой-либо изоморфизм, то для каждого подобного фрагмента между $i,j$ найдется такой же подобный фрагмент между $i',j'$. Пусть вершина $k$ принадлежит к тому же семейству, что и вершина $j$. Тогда между вершинами $i,k$ будут такие же (возможно, несколько раз повторенные) подобные фрагменты, что и между $i,j$ (это следует из подобия вершин - каждая вершина в семействе принадлежит одинаковым, с точностью до изоморфизма, подобным фрагментам). Если между $i,j$ будут какие-то подобные фрагменты, а между $i,k$ будут одинаковые, но несколько раз повторенные подобные фрагменты, то отображение $i\leftrightarrow i'$, $j\leftrightarrow k'$ не будет входить ни в какой изоморфизм. Эти фрагменты и такие же несколько раз повторенные не могут дать сходства решений на своих вершинах при том, что $b_{i}=b'_{i'}\neq b_{j}=b'_{k'}$ и на всех других, соответствующих искомому изоморфизму парах вершин, установлены попарно равные исходные веса.

Рассмотрим следующий пример (рис. 1). Для отображения 3-3', 4-5' несовпадение решений обусловлено разными путями между этими вершинами: 3-7-4, 3-10-6-9-5-8-4 и 3'-7'-4'-8'-5', 3'-10'-6'-9'-5'. На этих путях находятся изоморфные подграфы, иначе вершины были бы неподобны. Такая ситуация будет происходить для любого графа при выборе несимметричных пар подобных вершин: обязательно найдутся разные пути (и разное число одинаковых подобных фрагментов на этих путях), иначе с чего бы парам быть несимметричными? Например, в следующем графе (рис.2) можно выбирать любые пары подобных вершин для изоморфизма: пути между любыми парами одинаковые и все подобные вершины симметричны.

[bin]

Уже целых три дня от моих уважаемых оппонентов (ha, whitefox) никакой критики не наблюдается А я тем временем продолжаю анализировать и дополнять. Не думаю, что следующее правило принципиально изменит процедуру Р1, однако, может, так станет очевиднее, а правило такое: после выбора в семействе пары вершин на следующем шаге выбирать ту вершину из невыбранных в этом семействе, которая больше всего по весу. Например, для графа на рис.1 (см. предыдущий пост): если на предыдущем шаге была выбрана вершина 3, то на следующем невыбранные вершины семейства образуют следующую последовательность по убыванию весов: 6,4,5 – выбираем 6. А если, например, на предыдущем шаге была выбрана вершина 5, то последовательность будет 4,6,3 – выбираем 4. При этом последовательности повторяют те же веса, что и понятно - вершины-то подобны! Но, предположим, как было в предыдущем примере: на одном шаге мы выбрали вершины 3-3', а на следующем пробуем 4-4' или 4-5'. Если нам хочется выбрать вершину 4, то ее вес однозначно укажет пару 4', но не 5'. Почему так происходит? Выпишем оригинальные пути (цепи типа 3-1-4 vs 3-1-5, вносящие один и тот же вклад в перераспределение начального веса, рассматривать не будем):
выбор 3,4:
3-10-6-9-5-8-4 длина 6
3-1-6-9-5-8-4 длина 6
3-2-6-9-5-8-4 длина 6
3-7-4 длина 2
выбор 3,5:
3-10-6-9-5 длина 4
3-1-6-9-5 длина 4
3-2-6-9-5 длина 4
3-7-4-8-5 длина 4
Как интересно! В первом случае сумма всех длин 20, а во втором только 16. Но цепь 3-7-4 способствует большему приращению веса, чем более длинные цепи. Что вес зависит от маршрутов, можно видеть из ряда для обратной матрицы на стр. 4 второй версии статьи. И если у двух подобных вершин маршруты неодинаковы - не будет одинаковых приращений веса! Вершины, удаленные на расстояние 4, получают только часть веса от удаленных на меньшее расстояние, и сколько бы таких частей они не получили, скомпенсировать влияние более близких не смогут! (стр.3-4, версия 2)