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

[whitefox]

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

Для удобства обозначений будем нумеровать шаги алгоритма начиная с нуля. То есть на нулевом шаге будем иметь графы $G_0,G'_0$, а на $k$ шаге -- графы $G_k,G'_k$.

Пусть вершина $v$ принадлежит графу $G_k$.
Пусть $S_k(v)$ означает множество вершин графа $G_k$ подобных вершине $v$, а $S'_k(v)$ означает множество вершин графа $G'_k$ подобных (в расширенном смысле) вершине $v$.

На нулевом шаге для каждой вершины $i$ графа $G_0$ составляем "семейство" -- пару $(S_0(i),S'_0(i))$. Полный список "семейств", в общем случае, будет содержать повторы. Эти повторы можно исключить, либо оставить. Это не принципиально и на оценке времени не скажется.

На следующем шаге (первом) для каждой вершины $i$ графа $G_1$ составляем "семейство" $(S_0(i)\cap S_1(i),S'_0(i)\cap S'_1(i))$.

А на $k$ шаге для каждой вершины $i$ графа $G_k$ составляем "семейство" $(S_0(i)\cap\ldots\cap S_k(i),S'_0(i)\cap\ldots\cap S'_k(i))$.

Это так?

-- 17 июл 2011, 12:18 --

Для приведённого примера:

$S_0(1)=S_0(5)=\{1,5\}$, $S'_0(1)=S'_0(5)=\{1',5'\}$
$S_0(2)=S_0(4)=\{2,4\}$, $S'_0(2)=S'_0(4)=\{2',4'\}$
$S_0(3)=\{3\}$, $S'_0(3)=\{3'\}$

На нулевом шаге имеем "семейства":
({1, 5}, {1', 5'})
({2, 4}, {2', 4'})
({3}, {3'})

$S_1(2)=S_1(5)=\{2,5\}$, $S'_1(2)=S'_1(5)=\{1',4'\}$
$S_1(3)=S_1(4)=\{3,4\}$, $S'_1(3)=S'_1(4)=\{2',3'\}$

$S_0(2)\cap S_1(2)=\{2,4\}\cap\{2,5\}=\{2\}$, $S'_0(2)\cap S'_1(2)=\{2',4'\}\cap\{1',4'\}=\{4'\}$
$S_0(3)\cap S_1(3)=\{3\}\cap\{3,4\}=\{3\}$, $S'_0(3)\cap S'_1(3)=\{3'\}\cap\{2',3'\}=\{3'\}$
$S_0(4)\cap S_1(4)=\{2,4\}\cap\{3,4\}=\{4\}$, $S'_0(4)\cap S'_1(4)=\{2',4'\}\cap\{2',3'\}=\{2'\}$
$S_0(5)\cap S_1(5)=\{1,5\}\cap\{2,5\}=\{5\}$, $S'_0(5)\cap S'_1(5)=\{1',5'\}\cap\{1',4'\}=\{1'\}$

На первом шаге имеются "семейства":
({2}, {4'})
({3}, {3'})
({4}, {2'})
({5}, {1'})

И т.д.

[bin]

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

[ha]

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

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

А предварительные версии тут никому не интересны.

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

Предварительная версия в данном контексте - это когда автор не утверждает, что он решил задачу. Когда он утверждает, что решил задачу - это окончательная версия. И препринты в этом смысле должны быть окончательной версией.

Ну и цитата с блога http://experimentalmath.info/

Цитата:

It is all too easy to just ignore such difficulties. Unfortunately, as the authors conclude, “garbage doesn’t just go away.” All scientists need to speak up more to address nonsense and pseudo-science. What’s more, “We all need a better understanding of what science really is, how to recognize real science when we see it, and how to separate it from the garbage.”

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

Цитата:

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

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

А про это прошу поподробнее! В переписке мы, помнится, так и не договорились, computer sci. - это часть математики или нет? Про то, что программирование - часть computer sci., вроде никто не спорит.

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

Цитата:

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

Я прочел множество книг по математики и в них почему-то не было тривиальных ошибок.

Сравнили книгу с препринтом? Но в переписке, помню, Вы отказались подтвердить, что в книге В. А. Горбатов Фундаментальные основы дискретной математики. Информационная математика. — М.: Наука. Физматлит, 2000 нет ошибок (и, возможно, тривиальных) - речь о решении задачи четырех красок в этом учебнике, получившем одобрение Мин.образования. А Вы уверены, что в одностраничном решении той же задачи В. Л. Чечулиным нет тривиальных ошибок? (Его доказательство тоже в книге - в сборнике). Так что Вы лукавите: есть ряд спорных книг по математике, и Вам они известны.

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

Цитата:

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

Так что не надо опускать математику до своего уровня.

Еще одна спорная книга, на которую я Вам указывал в переписке: Клайн М. Математика. Утрата определённости. — М.: Мир, 1984. Там как раз показывается, как математики, настроенные подобно Вам, опустили математику через ее самоизоляцию. Т.о. Вы валите с больной головы на здоровую. Привычный Вам уровень математики - это решать только такие задачи, которые хорошо решаются - "не надо опускать математику до своего уровня".

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

Цитата:

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

Я уже привел контрпример к выводу 2. Зачем мне еще раз доказывать свои способности?

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

Цитата:

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

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

Все остальные, как показывает приведенная мною цитата, считают, то теория Лакатоса применима исключительно к 17-18 веку, а вы демонстрируете не знание базовых основ модельного подхода, считая, что если она работает 2 века, то работает везде.

[bin]

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

Ну и цитата с блога http://experimentalmath.info/

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

-- Пн июл 18, 2011 14:57:17 --

Намедни Вы признали:

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

Этот алгоритм вроде правильный. Теперь попробуйте его доказать.

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

-- Пн июл 18, 2011 15:09:34 --

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

-- Пн июл 18, 2011 15:25:53 --

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

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

Теория сложности вычислений - это часть computer sci., как и программирование. Но речь была не про то, что "доказательства в ней должны следовать всем требованиям строгости устоявшимся в математике", а про то, что программирование наиболее явно свидетельствует о природной склонности людей, и даже лучших специалистов, делать везде, где только возможно, ошибки, и даже тривиальные. Это "зашито" в человеческой природе и с этим приходится считаться при решении сложных задач, и без толку взывать "не делайте ошибок" даже в лучшей бригаде программистов (куда нередко входят и чистые математики) - все равно сделают! Поэтому реалисты всегда планируют комплексы сложных мероприятий по устранению ошибок. А у Вас нереалистичный подход, применимый только для хорошо решающихся задач.

-- Пн июл 18, 2011 15:35:16 --

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

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

Нет, я не просил, это Вы заявили "Я прочел множество книг по математики и в них почему-то не было тривиальных ошибок" (это прозвучало как "все книги"), а теперь согласились, что не все книги по математике без ошибок, поменяв таким образом квантор

[bin]

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

Клайн разве считает, что в математике нужны доказательства с тривиальными ошибками?

А я разве говорил, что в математике нужны доказательства с ошибками? Речь о самоизоляции математики, которую отметил Клайн. Эта самоизоляция проистекает в том числе и от патологического страха допустить ошибку, укоренившегося у большинства современных математиков. Перефразируя известную пословицу, можно сказать, что не ошибается только тот, кто не пытается решать труднорешаемые задачи. При решении трудных задач ошибки неизбежны, что, как отмечено выше, демонстрируется и всей практикой программирования. А значит, и надо подходить как в программировании: методом последовательного исправления версий. Что, кстати, математики и делают, посмотрите препринт http://arxiv.org/abs/0907.3965 - там уже 43 версии! Вот так и надо работать, а не стенать по поводу ошибок в промежуточных версиях.

-- Пн июл 18, 2011 16:39:09 --

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

Я уже привел контрпример к выводу 2. Зачем мне еще раз доказывать свои способности?

А я разве сказал, что Вам нужно доказывать свои способности? Эта тема не для доказывания Ваших способностей. Меня интересует решение подзадачи поиска изоморфизма по списку подобных вершин. Если Вы такого решения не предъявляете, то на слово Вам верить здесь никто не обязан.

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

Все остальные, как показывает приведенная мною цитата, считают, то теория Лакатоса применима исключительно к 17-18 веку, а вы демонстрируете не знание базовых основ модельного подхода, считая, что если она работает 2 века, то работает везде.

Я уже спрашивал, откуда та цитата? Вы не ответили. Но если бы все так считали, как Вы, то эта книга никогда бы не стала такой известной. Кому сейчас нужна модель для 18 века, кроме узкого круга историков? С тем же успехом я могу сейчас с сайта ЦБ РФ взять курсы доллар-рубль за 3 дня июля прошлого года и назвать это моделью. Данная модель будет применима только к означенным дням год назад. И кому нужна такая "модель"?

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

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

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

[bin]

(Оффтоп)

PS Про проблемы (в том числе и проблемы проверки доказательств) в методологии современной математики могу также порекомендовать прекрасную статью: Брайан Дэвис, Куда движется математика? - перевод из Notices of the American Mathematical Society, декабрь 2005, vol. 52, №11 - (там и книга Лакатоса помянута).

[whitefox]

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

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

Тогда Ваш алгоритм можно представить так:
1. $i:=0$
2. Для каждого $j\in V(G_0)$ выполнить $U(j):=V(G'_0)$
3. Для каждого $j\in V(G_i)$ при помощи оракула построить $S'_i(j)$
4. Для каждого $j\in V(G_i)$ выполнить $U(j):=U(j)\cap S'_i(j)$
5. Выбрать произвольную вершину $v\in V(G_i)$
6. Выбрать произвольную вершину $u'\in U(v)$
7. Соответствие $v\leftrightarrow u'$ включить в $map$
8. Построить графы $G_{i+1},G'_{i+1}$
9. Если $(V(G_{i+1})=\varnothing)\vee (V(G'_{i+1})=\varnothing)$, то выдать $map$ и остановиться
10. $i:=i+1$
11. Перейти к пункту 3

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

[bin]

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

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

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

Тогда Ваш алгоритм можно представить так:
1. $i:=0$
2. Для каждого $j\in V(G_0)$ выполнить $U(j):=V(G'_0)$
3. Для каждого $j\in V(G_i)$ при помощи оракула построить $S'_i(j)$
4. Для каждого $j\in V(G_i)$ выполнить $U(j):=U(j)\cap S'_i(j)$
5. Выбрать произвольную вершину $v\in V(G_i)$
6. Выбрать произвольную вершину $u'\in U(v)$
7. Соответствие $v\leftrightarrow u'$ включить в $map$
8. Построить графы $G_{i+1},G'_{i+1}$
9. Если $(V(G_{i+1})=\varnothing)\vee (V(G'_{i+1})=\varnothing)$, то выдать $map$ и остановиться
10. $i:=i+1$
11. Перейти к пункту 3

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

Все вроде так. Вот черновик начала доказательства, что в нем не хватает, как лучше доказать?

Т.к. на шаге 8 новые графы получаются удалением вершины,то $(V(G_{n})=\varnothing)\vee (V(G'_{n})=\varnothing)$. Т.о. алгоритм делает не более $n$ шагов по циклу. Оракул должен быть полиномиальным по времени, остальные действия также полиномиальны, следовательно, алгоритм будет полиномиальным.

Если $G_{0}\cong G'_{0}$ и вершины $u,v'$ подобны, то $G_{0}-u\cong G'_{0}-v'$ (Харари, Теория графов, С.202). Вершины, принадлежащие множеству $U(v):=U(j)\cap S'_i(j)$ , будут подобными c вершиной $v$ и в случае графа $G_{i}$ и в случаях $G_{i-1},G_{i-2},...,G_{0}$. Т.о. если в изоморфных графах $G_{i},G'_i$ удаляются подобные вершины $v,u'(u'\in U(v))$, то пара вершин $v,u'$ будет парой подобных вершин для всех графов последовательностей $G_0,...,G_{i}; G'_0,...,G'_{i}$.

Далее можно продолжить Улучшением 1, что установленная очередь удалений однозначно задает последовательность удаления подобных ребер, однако из этого продолжения возникает похожий алгоритм, который представляется более легким для доказательства.

Алгоритм 2.Пронумеруем все семейства подобных вершин и пометим каждую вершину номером своего семейства. Выберем пару подобных вершин $u,v'$ и обойдем из них графы в ширину, строя остовные деревья $T,T'$, при этом, просматривая ближайших соседей очередной вершины, будем сначала добавлять в дерево вершины с наименьшей меткой.

Доказательство. Расстояния между корнем дерева и любой вершиной в исходном графе и в дереве будут равны. Вершины с равными расстояниями от корня образуют уровень дерева, значение которого равно этому расстоянию. Из двух вершин одного уровня назовем левой ту, которая была раньше добавлена в дерево. Уровень вершин деревьев будет зависеть от расстояния до корня и не будет зависеть от нумерации вершин. Подобные вершины $p,p'$ имеют попарно подобных соседей $q_{i},q'_{i}$. Во время просмотра соседи добавляются к деревьям синхронно парами подобных вершин $q_{i},q'_{i}$ и отмечаются как просмотренные, поэтому если у подобных вершин $p,p'$ только часть соседей не просмотрена, то эта часть будет состоять из попарно подобных вершин $t_{i},t'_{i}$. Таким образом, на любом уровне последовательность меток вершин от левой к правой для обоих деревьев $T,T'$ будет одинаковой. И действительно, на первом уровне лежит одна корневая вершина - корни деревьев подобны, на втором уровне - все соседи корня, попарно подобные соседям корня второго дерева. Пусть на $i$-ом уровне последовательности меток будут одинаковы, тогда вершины $p,p'$, занимающие $j$-ое место от крайне левой на $i$-ом уровне, будут иметь попарно подобных соседей. Во время роста дерева для каждого уровня в левое поддерево (образованное левой вершиной) будет добавляться максимально возможное количество не просмотренных ранее вершин (т.е. дерево будет упорядочено). Т.о. ветвями и листьями поддеревьев $p,p'$ станут соседи этих вершин, не просмотренные ранее, причем эти непросмотренные соседи $t_{k},t'_{k}$ попарно подобны для графа, а в дереве их степени будут совпадать. Т.е. вершины $p,p'$ дадут на уровне $i+1$ одинаковые подпоследовательности меток вершин и степеней. Т.о. $T\cong T'$(об изоморфизме упорядоченных деревьев см. классическую работу: Дж. Е. Хопкрофт, П. Е. Тарьян, Изоморфизм планарных графов, Кибернетический сборник, вып.12, М.: 1975; Hopcroft J., Tarjan R., Isomorphism of planar graphs, Proc 4d Annual Symp. on the Theory of Computing, Shaker Heigts, 1972, 131) и подграфы, образованные ребрами, не вошедшими в остов и всеми вершинами своего графа, будут изоморфны, причем хотя бы один из изоморфизмов деревьев и подграфов совпадает, этот изоморфизм, получаемый простым наложением одного дерева на другое, будет искомым изоморфизмов графов. Все проделанные операции полиномиальны по времени.

Что не хватает, как лучше доказать?

[whitefox]

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

Оракул должен быть полиномиальным по времени

Обычно полагают, что вызов оракула занимает один такт. Что Вы понимаете под "полиномиальным оракулом"?

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

Вершины, принадлежащие множеству $U(v):=U(j)\cap S'_i(j)$ , будут подобными c вершиной $v$ и в случае графа $G_{i}$ и в случаях $G_{i-1},G_{i-2},...,G_{0}$

Полагаю, что здесь должно быть $U(v):=U(v)\cap S'_i(v)$.

Также нужно показать, что для изоморфных графов $U(v)$ всегда не пусто. А так как для не изоморфных графов такое возможно, то в алгоритм нужно добавить ещё один шаг:

4'. Для каждого $j\in V(G_i)$ если $U(j)=\varnothing$, то выдать $map$ и остановиться

Шаги 3, 4 и 4' можно объединить в один цикл.

[bin]

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

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

Оракул должен быть полиномиальным по времени

Обычно полагают, что вызов оракула занимает один такт. Что Вы понимаете под "полиномиальным оракулом"?

Верное замечание.

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

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

Вершины, принадлежащие множеству $U(v):=U(j)\cap S'_i(j)$ , будут подобными c вершиной $v$ и в случае графа $G_{i}$ и в случаях $G_{i-1},G_{i-2},...,G_{0}$

Полагаю, что здесь должно быть $U(v):=U(v)\cap S'_i(v)$.

Да, опечатка.

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

Также нужно показать, что для изоморфных графов $U(v)$ всегда не пусто. А так как для не изоморфных графов такое возможно, то в алгоритм нужно добавить ещё один шаг:

4'. Для каждого $j\in V(G_i)$ если $U(j)=\varnothing$, то выдать $map$ и остановиться

Шаги 3, 4 и 4' можно объединить в один цикл.

Ok. Для изоморфных графов $U(v)$ всегда не пусто, т.к. в случае таких графов существуют отображения подобных вершин, дающие изоморфизм, и эти отображения входят в $U(v)$ для каждого $G_{i}$. Это понятно, но вот как бы это убедительнее показать? Из $G_{0}-u\cong G'_{0}-v'$ следует, что последовательно удаляя смежные подобные ребра (т.е. ребро, удаляемое в графе $G_{i}$ , инцидентно той же вершине, что ребро, удаляемое в графе $G_{i+1}$, т.е. следуем порядку удаления, заданным обходом в ширину исходных графов), мы получим две последовательности попарно изоморфных графов и в конце получим два изоморфных графа, состоящих каждый из $n$ изолированных вершин. А какое мнение об алгоритме 2?

[whitefox]

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

А какое мнение об алгоритме 2?

Ну, раз Вы спросили, отвечу:
ни алгоритм 1, ни алгоритм 2 не нужен для решения поставленной Вами задачи.

А именно следующей задачи:
решить за полиномиальное время проблему изоморфизма графов $G,G'$, имея доступ к оракулу, получающему на вход $G,G',v\in V(G),\mathfrak U\subseteq V(G')$ и выдающему $u'\in\mathfrak U$ подобную $v$ если существует, и отвечающему "нет" в противном случае.

Решение этой задачи следует из предложенного Вами расширения понятия "подобия вершин графа":

Цитата:

According to Harary’s definition: “Two points [vertices – MT] $u$ and $v$ of the graph $G$ are $similar$ if for some automorphism $\alpha$ of $G$, $\alpha(u) = v$.” [5], p.171. We expand this definition for vertex $u$ of the graph $G$ and vertex $v$ of the graph $G'$:
Definition 1. If $G\cong G'$ and $v\leftrightarrow u$ is possible mapping, then $u$ and $v$ are similar.

В частности, из этого определения следует, что для вершины $v$ графа $G$ найдется подобная вершина $u'$ графа $G'$ тогда и только тогда, когда графы $G,G'$ изоморфны.

И поэтому, заявленная задача может быть решена следующим простым алгоритмом, имеющим доступ к оракулу, отвечающему только "да/нет" на вопрос: "подобна ли вершина $v$ графа $G$ вершине $u'$ графа $G'$".

Полагаем, что как вершины графа $G$ так и вершины графа $G'$ занумерованы номерами от $1$ до $n$.
1. $i:=0$
2. $i:=i+1$
3. $j:=0$
4. $j:=j+1$
5. вызываем оракул для вершин $i\in V(G), j\in V(G')$
6. если ответ оракула "да", то выдать "изоморфны" и остановиться
7. если $j<n$, то перейти к пункту 4
8. если $i<n$, то перейти к пункту 2
9. выдать "не изоморфны" и остановиться

Причём внешний цикл, по большому счёту, не нужен. Так как в графе $G$ достаточно проверить только одну вершину.

[bin]

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

И поэтому, заявленная задача может быть решена следующим простым алгоритмом, имеющим доступ к оракулу, отвечающему только "да/нет" на вопрос: "подобна ли вершина $v$ графа $G$ вершине $u'$ графа $G'$".

Это было бы верно, если бы у нас был такой оракул, то мы могли бы спихнуть на него ответ на вопрос, изоморфны ли графы. Однако, 1) и в случае положительного ответа такого оракула, что какая-то пара вершин подобна, а значит, графы изоморфны, остается открытым вопрос "как в этом случае найти какой-либо изоморфизм за полиномиальное время?"; 2) речь в нашем случае идет о другом оракуле, который отвечает верно только в случае изоморфных графов, а в случае неизоморфных врет, т.е. на какие-то пары вершин он может ответить "да", хотя графы неизоморфны и о подобии говорить не приходится. Отдельный терминологический вопрос "можно ли такого оракула называть оракулом?" сути не меняет - можем назвать нашу процедуру по поиску подобных вершин псевдо-оракулом, а сами вершины, пока не установлен изоморфизм, псевдо-подобными. И вообще "оракул" - временное название, которое появилось в данном обсуждении отдельной подзадачи, в статье я это слово не применяю, и после решения подзадачи от слова "оракул" придется отказаться хотя бы потому, что, как Вы верно заметили, ответ оракула должен занимать всего один такт. И т.о. мои вопросы остаются в силе.

[bin]

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

Также нужно показать, что для изоморфных графов $U(v)$ всегда не пусто.

Пусть мы знаем какой-нибудь изоморфизм исходных графов, используем его для удалений, но вместо удаления пары подобных вершин будем удалять только все ребра, инцидентные этим вершинам. Получим последовательности графов, где известный нам изоморфизм будет удовлетворять каждой паре $G_i,G'_i$ из этих последовательностей. Т.о. для каждой вершины $v$ найдется такая подобная вершина $u'$, что отображение $v\leftrightarrow u'$ входит в этот изоморфизм. Следовательно, $u'\in S'_i(v), i=0,...,n$ и $U(v)$ будет всегда не пусто.

[whitefox]

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

1) и в случае положительного ответа такого оракула, что какая-то пара вершин подобна, а значит, графы изоморфны, остается открытым вопрос "как в этом случае найти какой-либо изоморфизм за полиномиальное время?"

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

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

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

Вот Вам пример такого оракула -- оракул всегда отвечающий "да". Какую пользу можно из него извлечь?

[whitefox]

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

Вот Вам пример такого оракула -- оракул всегда отвечающий "да". Какую пользу можно из него извлечь?

Это возражение снимается. Извините.

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

Отдельный терминологический вопрос "можно ли такого оракула называть оракулом?"

А почему нет?
Этот оракул (назовём его Q) эквивалентен комбинации трёх других оракулов

$$Q=Q_1Q_2\vee \bar{Q}_1Q_3$$

Где:
$Q_1$ -- оракул отвечающий на вопрос изоморфны ли графы $G,G'$
$Q_2$ -- указанный мной оракул
$Q_3$ -- произвольный оракул.