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

[bin]

maxal в сообщении #365866 писал(а):

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

-- Sun Oct 24, 2010 15:06:09 --

Например, в один из этих:
Journal of Graph Algorithms and Applications
Journal of Graph Theory
Journal of the ACM

Искреннее спасибо за совет, но Вы меня недооцениваете
Хотя я и не обязан соблюдать лояльность по отношению к каким-либо журналам, но соблюду и не буду называть имен: в один из указанных Вами журналов я посылал статью еще до архива и там-то я получил великий отзыв: "Мне кажется, что какая-нибудь пара строгорегулярных графов окажется контр-примером". Ну еще кучку благоглупостей типа "не понял описания алгоритма, но скажу"- сразу возник конкретный вопрос, что именно непонятного в описании алгоритма: первые строки, например, инициализация переменных, последние - вывод результата. Это, надеюсь, было понятно? Беда в том, что журналы "не вступают в переписку с авторами отклоненных статей", поэтому, какую бы глупость Вам рецензент ни написал, оспорить Вы не сможете!

Только в одном журнале из 7 редактор, а не рецензент, "досконально проанализировал" и сообщил контрпример, что я и отметил в благодарностях - в результате появились W-матрицы. Но далее и этот журнал устранился. Если учесть, что время на ожидание рецензии от 2 месяцев до полугода, то поиск места, где бы "досконально проанализировали", вырастает в непростую проблему.

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

PS. Не для саморекламы (которую так не любят на некоторых сайтах, например, в википедии), а чтобы было понятно: я не новичок в плане публикаций: у меня их около сотни, и среди них такие, как в легендарном BYTE, не говоря о ДАН и Известиях РАН и т.д. Но когда Вы предлагаете решение открытой проблемы, сложность публикации возрастает на порядки...
PPS. Извините, что не сразу отвечаю по сути Вашего утверждения: "рецензенты досконально проанализируют вашу статью и либо примут к публикации, либо откажут, указав на ошибки". Оно не выполняется в последней части, т.е. за 2 года скитания по редакциям я понял, что "рецензенты [как-то по минимуму] проанализируют вашу статью и либо примут к публикации, либо откажут" , но вот на ошибки Вам навряд ли укажут! Кстати, из того журнала, где мне отказали, через пол-года прислали на рецензию статью по теории графов, но не по их изоморфизму. Я оказался, сославшись на то, что я занимаюсь computer sci. и мне нравятся статьи с листингами, а в той была чистая математика. А мог бы... (Они всех рецензентов так по "рандому" выбирают?

[maxal]

bin
Недооценивание тут не причем. Просто отправка статьи в уважаемый журнал - это стандартный способ привелечения к ней внимания для последующего признания. Если в одном журнале вам не повезло, попробуйте в другом. Если критично время, найдите журнал с гарантированным временем реферирования, оговоренном в редакционной политике. Если такового подходящего нет, пошлите статью на приличную реферируемую конференцию (например, STOC, FOCS или SODA) - там время реферирования обычно в районе 3-х месяцев; а будучи принята на такую конференцию, у статьи потом будет больше шансов быть принятой в журнал.
Далее, не повезло в одном журнале, попробуйте счастья в другом (по возможности учтя претензии рецензентов предыдущего).
Да, и если рецензенты придираются к мелочам, вылижите статью так, чтобы у них не было и шанса придраться к чему-то.

В любом случае от стенаний на форумах (в том числе тут) престижа вашей статье не прибавится.

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

[bin]

maxal
Стенание - неподходящее слово. Для чего еще нужны форумы, если на них нельзя будет услышать полезный совет или обсудить проблему? А проблема не маленькая - система научного рецензирования постоянно подвергается обоснованной критике, а в экстремальных случаях, к которым относятся открытые проблемы, эта система сбоит. Вдруг кто-то еще из читателей этой темы сталкивался с подобной ситуацией? Может такое быть? Думаю, может. И тогда обмен опытом может оказаться полезным. Со своей стороны могу поделиться, например, следующим know-how. То, что Вы пишете про отправку статьи - стандартный общеизвестный путь. В случае экстремальных тем лучше сделать предварительный шаг: написать письмо глав.реду с заголовком и абстрактом статьи и спросить, заинтересует ли такая статья. Это сильно экономит время - проверил.

[bin]

maxal,
Вам могло показаться, что я только спорю и не прислушиваюсь к советам. Чтобы Вам это не показалось, сообщу, что прислушался и послал статью в один очень авторитетный журнал Интересно отметить, что это один из семи журналов, отказавших мне ранее В тот раз ни один из рецензентов не нашел значительных ошибок, но один из них написал, что для столь важной проблемы к убедительности доказательства предъявляются особые требования и что по его мнению мое тогдашнее доказательство не было столь убедительным. В этот раз я предварительно написал гл.редактору (очень известному человеку в computer sci.), что после того, как моя статья была отвергнута его журналом, я 11 апреля 2010 г. выложил ее в arxiv и получил ряд сообщений об ошибках и ряд конструктивных идей по их ликвидации. Я учел все критические замечания, и месяц назад выложил вторую версию этого препринта. С тех пор я не получил ни одного замечания, что позволяет надеяться, что на этот раз доказательство верное и достаточно убедительное. На что гл. редактор ответил согласием снова рассмотреть исправленную статью. И сейчас она находится в фазе «рецензирование». Каков бы ни был результат, я очень благодарен редактору за доверие. А также всем, кто внес конструктивную критику: в благодарностях в статье я перечислил их поименно. Каков бы ни был результат, вполне возможно, что кто-то ( в том числе и на этом форуме) сможет предложить более простой и убедительный вариант доказательства. Буду очень благодарен! Моя цель решить задачу (и хорошо, если совместно), а не детское желание заявить, что все я сделал сам без чьей- либо помощи (такое в современной науке почти невозможно)

[whitefox]

Уважаемый, bin.
Доказательство Вашей леммы 1 содержит ошибку.
Кроме того, неплохо бы пройтись по Вашей статье бритвой Оккамы.
Например:

Цитата:

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 4. If $G\cong G'$ and $v\leftrightarrow u$ is possible mapping, then $u$ and $v$ are
$similar$.

Нет никакой необходимости вводить понятие расширенного подобия для вершин пары графов. Достаточно рассматривать группу автоморфизмов графа $G_1$, являющегося объединением графов $G$ и $G'$. Классы подобных вершин этого графа совпадут с классами расширенно-подобных вершин пары графов $G$ и $G'$. Кроме всего прочего, это позволит исключить условие $G\cong G'$ из формулировки леммы 1, так как группа автоморфизмов любого графа не пуста.


Цитата:

Lemma 1. Part 2. We now prove that if $G\cong G'$ and $W_i = W_j'$ , then $i$ and $j$ are
similar. Suppose that vertices $i,j$ are not similar, i.e. no one isomorphicmapping
consists $i\leftrightarrow j$.

Зачем Вам "противное" доказательство? Ведь в своём выводе Вы нигде не используете посылку $\textit{вершины }i\textit{ и }j\textit{ не подобны}$.

Ваш, весьма остроумный, алгоритм совершенно не нужен для доказательства полиномиальности проблемы изоморфизма графов. Всё что требуется -- это доказать часть 2 леммы 1. Нужный Вам вывод последует от сюда почти автоматически.
Судите сами:
Определяемая для каждой вершины графа величина $W$ является инвариантом класса подобных вершин, что следует из части 1 леммы 1. Для определённости назовём $W$ индексом подобия.


Замечание: Хотя Вы и определяете величину $W$ как матрицу, Xaositect справедливо отметил, что её матричная структура нигде не используется. Зачем тогда плодить сущности без необходимости? Будем считать $W$ просто величиной.

Обозначим через $W(G)$ мультимножество всех индексов подобия графа $G$. Легко показать, что $W(G)$ является инвариантом графа $G$. Если бы лемма 1 была справедлива, то из неё следовало бы, что индекс подобия является полным инвариантом класса подобных вершин. От куда уже, в свою очередь, выводится, что $W(G)$ -- полный инвариант графа $G$. А так как $W(G)$ вычисляется за полиномиальное от числа вершин время, то это и означает полиномиальную сложность проблемы изоморфизма графов.


Замечание: Прежде чем удалите свой алгоритм, исправьте в нём опечатку.
Цитата:

$j := GetSimilar (k,\mathfrak{S'},mark');$ {get unmarked vertex $j$ such that $W_i = W_j'$}

А должно быть: $j := GetSimilar (i,\mathfrak{S'},mark');$

Теперь по ошибке в доказательстве леммы 1.
Часть 1 безусловно верна, а вот с частью 2 проблема.

Цитата:

So $W_i=W_p$ and so by definition of W-matrix (Definition 3) we have:

$$\bar w_h=\bar w_{r(h)},$$

$$sort(\bar a_h)=sort(\bar a_{r(h)}),$$

where $i=r(p),p=r(i)$; vector $\bar a_h=(k_{h1},k_{h2},\dots,k_{hn})$ is hth row of matrix $A^{-1}$.

Здесь неявным образом используется посылка $(W_i=W_p)\Rightarrow(\textit{вершины }i\textit{ и }p\textit{ подобны})$, которая никак не доказывается. А ведь это фактически доказываемое утверждение. Не удивительно, что после этого легко получаем окончательный вывод. Ссылка на определение величины $W$ никак не помогает, и потому должна быть отсечена бритвой Оккамы. Представляется, что это затруднение не устранимо, так как часть 2 леммы 1 полагаю ложной. Если кому не лень -- может попробовать найти контрпример. Достаточно предъявить граф у которого разные классы подобных вершин имеют один и тот же индекс подобия.

Впрочем задача определения классов подобия столь же сложна как и проблема изоморфизма. Поэтому при поиске контрпримера к лемме 1 лучше использовать ещё один индекс подобия, более сильный чем $W$, но тоже полиномиальный. Бесконечную последовательность индексов подобия возрастающей силы и полиномиальной сложности можно построить так:

Легко показать, что величина $\bar w$ является инвариантом класса подобных вершин. Назовём её индексом подобия уровня 0 и обозначим $W^{(0)}$.
Индекс подобия $W$ назовём индексом подобия уровня 1 и обозначим $W^{(1)}$.
Если уже построен индекс подобия уровня k $W^{(k)}$, то индекс подобия уровня (k+1) $W^{(k+1)}$ построим, заменив в определении величины $W$ все величины $\bar w_i$ на соответствующие $W_i^{(k)}.$

Очевидно, что все эти индексы имеют полиномиальную сложность, и обладают следующим свойством:

$$(W_i^{(k+1)}=W_j^{(k+1)})\Rightarrow(W_i^{(k)}=W_j^{(k)}).$$

Поэтому для опровержения леммы 1 достаточно предъявить граф у которого две вершины имеют одинаковые индексы подобия уровня 1 $W^{(1)}$, но разные индексы подобия уровня 2 $W^{(2)}$.

[bin]

Уважаемый whitefox,

Прежде чем перейти к конкретным ответам по сделанным Вами замечаниям, отмечу, что так называемая Бритва Оккама (почему-то Вы дважды называете "Оккамы", но я буду использовать более распространенную транскрипцию, рекомендуемую, например, Википедией) не является законом, а всего лишь принципом, способствующим понижению избыточности. Многочисленные исследования показывают, что естественные языки, такие, как русский, на котором мы здесь с Вами общаемся, или как английский, на котором написана моя статья, имеют далеко не нулевую избыточность. (Т.о., ни с русским, ни с английским Бритву полностью не совместить :). Более того, даже распространенные искусственные языки имеют некоторую избыточность. В отношении моей статьи охотно допускаю, что я, как и многие авторы, внес значительную дополнительную избыточность, и все может быть сформулировано более лаконично на некотором формальном языке. Однако практика показывает, что слишком лаконичные тексты плохо воспринимаются подавляющим большинством читателей, поэтому даже научные публикации, ориентированные на узкий круг специалистов, как правило, ради читабельности не злоупотребляют лаконизмом. Тем более не стоит экономить на объеме, когда речь идет об открытой проблеме. Однако охотно допускаю, что приведенные мной утверждения и их доказательства могут быть переформулированы более компактно с той же или большей ясностью и, таким образом, изначальный текст может быть улучшен. Но если такая переформулировка и состоится, ее факт сам по себе не будет означать, что первоначальное доказательство неверное, хоть и более избыточно ;)

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

1. Начну с основного - с отмеченной Вами "проблемы" в Лемме 1. Все тривиально:
$W_i=||\bar s^{(i)}_{mt}||$, $W_p=||\bar s^{(p)}_{mt}||$
$W_i=W_p \Rightarrow \bar s^{(i)}_{mt} = \bar s^{(p)}_{mt}$ , (1)
по определению равенства матриц (NB: некоторые фундаментальные свойства матриц где-то используются :).
Если $\bar s^{(i)}_{mt} \neq \bar z $, то $\bar s^{(i)}_{mt} = \bar w_h$ по определению 3 (NB: ссылка на определение не бесполезна :)
Аналогично: если $\bar s^{(p)}_{mt} \neq \bar z $, то $\bar s^{(p)}_{mt} = \bar w_q$, (2)
причем речь идет об одном и том же графе, где между номерами вершин $h$ и $q$ существует соответствие $r: q=r(h) $, т.е. иными словами, матрицы $W_i $ и $W_p $ сформированы из одного и того же набора w-векторов.
Перепишем (2):
$\bar s^{(p)}_{mt} = \bar w_q = \bar w_{r(h)} $,
учитывая (1) получим:
$ \bar w_h = \bar w_{r(h)} $.
Вот и все, что IMHO стоило сказать по этой "проблеме". Я не представляю, где Вы сумели усмотреть в процитированном Вами фрагменте, что "неявным образом используется посылка $(W_i=W_p)\Rightarrow(\textit{вершины }i\textit{ и }p\textit{ подобны})$" ? В отношении Вашего заявления "Достаточно предъявить граф у которого разные классы подобных вершин имеют один и тот же индекс подобия" могу только предложить опровергнуть теорему Пифагора: достаточно предъявить треугольник у которого сумма всех углов не равна двум прямым ;))

2. Ваше методологическое замечание в отношении той же Леммы 1 ("Зачем Вам "противное" доказательство? Ведь в своём выводе Вы нигде не используете посылку $\textit{вершины }i\textit{ и }j\textit{ не подобны}$") мне совершенно непонятно. Имею полное право доказывать от противного вне зависимости, буду ли я использовать "противную посылку" в дальнейшем.

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

4. При цитировании фрагмента "Lemma 1. Part 2." Вы допустили опечатку - в статье "isomorphic mapping" написано в два слова, а не в одно, как в Вашей цитате.

5. Xaositect сказал, что матричная структура W-матрицы нигде не используется применительно к первой версии статьи, здесь же речь о второй, сильно переработанной версии.

[whitefox]

Уважаемый bin.

Спасибо, что указали на мои опечатки. Если встретите ещё -- не стесняйтесь. Буду признателен.

Не желаете пользоваться Бритвой Оккама? Что ж -- Ваше суверенное право. Настаивать не буду.

(Оффтоп)

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

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

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

О какой подмене терминологии Вы говорите? Приведите, пожалуйста, примеры.

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

я не буду обсуждать замену "подобия" на теоретико-групповую терминологию

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

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

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

Эта гипотеза легко доказывается. И если Вы убеждены в справедливости Леммы 1, то Вам ничего больше доказывать не нужно. Всё уже будет доказано.

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

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

Утверждение 1 вполне очевидно и сомнений не вызывает. Но доказательство корректности Вашего алгоритма основано не столько на нём, сколько на Лемме 1. А вот она-то, как раз, вызывает сомнения.

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

Начну с основного - с отмеченной Вами "проблемы" в Лемме 1. Все тривиально:
$W_i=||\bar s^{(i)}_{mt}||$, $W_p=||\bar s^{(p)}_{mt}||$
$W_i=W_p \Rightarrow \bar s^{(i)}_{mt} = \bar s^{(p)}_{mt}$ , (1)
по определению равенства матриц (NB: некоторые фундаментальные свойства матриц где-то используются :).

Вы сравниваете массивы. Что именно фундаментально-матричное Вы в этом усматриваете?

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

Если $\bar s^{(i)}_{mt} \neq \bar z $, то $\bar s^{(i)}_{mt} = \bar w_h$ по определению 3 (NB: ссылка на определение не бесполезна :)

Если бы была польза от ссылки на определение матрицы $W$, то Вам не понадобилось бы даже доказывать Лемму 1. Просто сослались бы на это определение и этим всё было бы доказано.

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

Аналогично: если $\bar s^{(p)}_{mt} \neq \bar z $, то $\bar s^{(p)}_{mt} = \bar w_q$, (2)
причем речь идет об одном и том же графе, где между номерами вершин $h$ и $q$ существует соответствие $r: q=r(h) $, т.е. иными словами, матрицы $W_i $ и $W_p $ сформированы из одного и того же набора w-векторов.

А вот существование этого автоморфизма $r$, обладающего указанными свойствами, Вы как раз и не доказываете. Именно в этом суть моего возражения.

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

Я не представляю, где Вы сумели усмотреть в процитированном Вами фрагменте, что "неявным образом используется посылка $(W_i=W_p)\Rightarrow(\textit{вершины }i\textit{ и }p\textit{ подобны})$" ?

У Вас имеется посылка $(W_i=W_p)$ и имеется заключение $(\textit{вершины }i\textit{ и }p\textit{ подобны})$, чтобы вывод был правильным нужна ещё посылка $(W_i=W_p)\Rightarrow(\textit{вершины }i\textit{ и }p\textit{ подобны})$. Вот её-то Вы неявно и используете.

(Оффтоп)

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

В отношении Вашего заявления "Достаточно предъявить граф у которого разные классы подобных вершин имеют один и тот же индекс подобия" могу только предложить опровергнуть теорему Пифагора: достаточно предъявить треугольник у которого сумма всех углов не равна двум прямым ;))

Мой призыв искать контрпример к Вашей Лемме 1 был обращён к людям убеждённым в не полиномиальности проблемы изоморфизма графов. А к кому обращён Ваш призыв? Или, может, Вы сомневаетесь в истинности теоремы о сумме углов треугольника? Кстати, правильно сомневаетесь -- в неевклидовой геометрии эта теорема не верна.

(Оффтоп)

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

Ваше методологическое замечание в отношении той же Леммы 1 ("Зачем Вам "противное" доказательство? Ведь в своём выводе Вы нигде не используете посылку $\textit{вершины }i\textit{ и }j\textit{ не подобны}$") мне совершенно непонятно. Имею полное право доказывать от противного вне зависимости, буду ли я использовать "противную посылку" в дальнейшем.

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

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

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

Да внимательно я изучал Вашу статью и особенно алгоритм. Если бы не внимательно, то и указанную опечатку не заметил бы.
Функция $GetSimilar (i,\mathfrak{S'},mark')$ в качестве своего первого аргумента должна принимать именно $i$ -- номер вершины первого графа, а номер блока разбиения $k$ в эту функцию совсем не передаётся, вместо этого второй аргумент принимает копию блока $\mathfrak{U}_k'$.

[bin]

Уважаемый whitefox,
И Вам спасибо за найденную опечатку - действительно, вызов GetSimilar должен иметь первым параметром i. Нужно будет исправить и описание этой функции. Сделаю в следущей версии статьи.
Рад, что императивные толкования ряда принципов Вы сменили на рекомендательные: Бритва Оккама, докзательство от противного.

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

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

IMHO чрезмерное увлечение Бритвой Оккама точно не способствует прояснению мысли автора, увлекшись Бритвой, нетрудно дойти до полного абсурда. Так, чтобы быть последовательным, нужно сменить и язык на менее избыточный: в пределе, исполняемый код - инструкции CPU менее избыточны, чем даже ассемблер с его мнемониками Если же говорить серьезно, то Вы пока не доказали, что текст статьи искусственно усложнен. Напротив, ниже я проиллюстрирую, что некоторые Ваши "упрощения" на деле обернутся тем самым искусственным усложнением.

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

Вы сравниваете массивы. Что именно фундаментально-матричное Вы в этом усматриваете?

Всего лишь то, что двумерные массивы я сравниваю как матрицы. Как еще можно сравнивать массивы, спросите Вы? - Да очень по-разному! Например, одномерные массивы-строки на стандартном Паскале можно определить как:

type string=array [0..maxlen] of char;

где первый элемент с индексом 0 указывает на длину строки. Для тестирования строк s1,s2 на равенство устанавливаются особые правила, отличные от других "обычных" массивов:
1) строки должны быть одинаковой длины, т.е. s1[0]=s2[0]
2) s1[ i ]=s2[ i ], i=1,...,s1[0]
Если, например, мы запишем в s1 строку "голова-хвост1", а в s2 строку "голова-хвост2" и скусим хвосты, установив s1[0]:=6; s2[0]:=6; то строки окажутся равными, в то же время, если мы будем сравнивать s1,s2 как обычные массивы, т.е по правилу: массивы равны, если s1[ i ]=s2[ i ], i=0,...,maxlen, то получим, что они не равные. Это общеизвестные вещи, и мне очень странно, что приходится это объяснять. Когда я говорю, что W - это матрица, то всем должно быть понятно, как обнаружить равенство матриц, когда Вы предлагаете заменить слово матрица на "просто величину", то придется специально объяснять правила равенства таких "величин", имеющих внутреннюю структуру. Вот Вам один из примеров подмены, против которой я возражаю. Пример этот IMHO очень показательный, поскольку кажущеесе упрощение обернется на деле усложнением. Поэтому, когда Вы повторяете:

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

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

у меня возникает впечатление, что как раз подобные "упрощения" способны сделать любое доказательство и неправильным и переусложненным.

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

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

А где тут я говорю про автоморфизм? Ни про какой автоморфизм, т.е. про соответствия вершин с сохранением связности, речи на данном этапе не идет! Я всего лишь отметил самоочевидный факт, что n предметов можно распределить по n ящикам, так чтобы в каждом ящике оказалось по одному предмету. Два варианта такого распределения являются соответствием r, задаваемым, например, таблично: 1ый ящик: вариант 1 - предмет номер 5, вариант 2 - предмет номер 3; 2ой ящик: ...

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

Мой призыв искать контрпример к Вашей Лемме 1 был обращён к людям убеждённым в не полиномиальности проблемы изоморфизма графов.

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

[whitefox]

Уважаемый bin.
Рад, что Вы сменили праведный гнев на милость, и согласились со мной хотя бы по одному пункту.

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

И Вам спасибо за найденную опечатку - действительно, вызов GetSimilar должен иметь первым параметром i.

Если так пойдёт и дальше, то, возможно, вы признаете мою правоту и по Лемме 1.

(Оффтоп)

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

Рад, что императивные толкования ряда принципов Вы сменили на рекомендательные

Ну насчёт императивного толкования -- это Вам показалось. Я и в своём первом посте давал всего лишь рекомендации.

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

IMHO чрезмерное увлечение Бритвой Оккама точно не способствует прояснению мысли автора, увлекшись Бритвой, нетрудно дойти до полного абсурда. Так, чтобы быть последовательным, нужно сменить и язык на менее избыточный: в пределе, исполняемый код - инструкции CPU менее избыточны, чем даже ассемблер с его мнемониками

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

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

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

Такую цель я себе и не ставил. Нисколько не оспариваю Ваше право, как автора, писать статью так как Вы считаете нужным. ИМХО, статья действительно искусственно усложнена. И, в первую очередь, лишним для целей статьи считаю Ваш остроумный алгоритм. Разбираться в его работе -- одно удовольствие. К сожалению, для доказательства он не нужен.

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

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

Вы сравниваете массивы. Что именно фундаментально-матричное Вы в этом усматриваете?

Всего лишь то, что двумерные массивы я сравниваю как матрицы.

Скажу честно -- введённые Вами структуры $W$ меня очаровали. Не помню, давали ли Вы им какое-либо название. Я их называю "индексы подобия" и, с Вашего позволения, буду их так называть в своих постах.
На множестве индексов подобия определена всего лишь одна операция -- сравнение. А на множестве матриц таких операций определено великое множество.
Любой математик, встретив в тексте слово "матрица", сразу же, на уровне подсознания, связывает данный объект с указанным множеством операций. А то, что под термином "матрица" Вы понимаете двухмерный массив -- ему будет невдомёк.
Дабы избежать такой двусмысленности, я и возражаю против использования термина "матрица" по отношению к индексам подобия. ИМХО, лучше их определять как "величины" -- тут двусмысленности возникнуть не может.

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

Например, одномерные массивы-строки на стандартном Паскале можно определить как:

type string=array [0..maxlen] of char;

где первый элемент с индексом 0 указывает на длину строки. Для тестирования строк s1,s2 на равенство устанавливаются особые правила, отличные от других "обычных" массивов:
1) строки должны быть одинаковой длины, т.е. s1[0]=s2[0]
2) s1[ i ]=s2[ i ], i=1,...,s1[0]
Если, например, мы запишем в s1 строку "голова-хвост1", а в s2 строку "голова-хвост2" и скусим хвосты, установив s1[0]:=6; s2[0]:=6; то строки окажутся равными, в то же время, если мы будем сравнивать s1,s2 как обычные массивы, т.е по правилу: массивы равны, если s1[ i ]=s2[ i ], i=0,...,maxlen, то получим, что они не равные. Это общеизвестные вещи, и мне очень странно, что приходится это объяснять.

К чему весь этот ликбез? Я, например, Паскалю предпочитаю С или даже С++. Только, давайте, не будем начинать холливар по этому поводу.

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

Когда я говорю, что W - это матрица, то всем должно быть понятно, как обнаружить равенство матриц, когда Вы предлагаете заменить слово матрица на "просто величину", то придется специально объяснять правила равенства таких "величин", имеющих внутреннюю структуру. Вот Вам один из примеров подмены, против которой я возражаю. Пример этот IMHO очень показательный, поскольку кажущеесе упрощение обернется на деле усложнением.

Структуры сравниваются абсолютно так же как массивы -- поэлементно, зато не возникает никаких ложных ассоциаций. А вместо усложнения имеем упрощение так как не нужно объяснять правила введения нулевых векторов.

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

А где тут я говорю про автоморфизм? Ни про какой автоморфизм, т.е. про соответствия вершин с сохранением связности, речи на данном этапе не идет! Я всего лишь отметил самоочевидный факт, что n предметов можно распределить по n ящикам, так чтобы в каждом ящике оказалось по одному предмету. Два варианта такого распределения являются соответствием r, задаваемым, например, таблично: 1ый ящик: вариант 1 - предмет номер 5, вариант 2 - предмет номер 3; 2ой ящик: ...

При построении биекции $r$, Вы слишком свободно манипулируете векторами $\bar w_h$ -- допустима любая их перестановка. Но это не правильно -- можно использовать лишь перестановки, сохраняющие матрицу $A^{-1}$. Если же Вы считаете допустимой любую перестановку, то это нужно доказывать.

[bin]

Уважаемый whitefox,

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

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

Мне показалось, что как раз Вы сменили гнев и пафос убежденности в не полиномиальности проблемы изоморфизма графов Я же всегда открыт для конструктивной критики, однако 30 лет работы в системе РАН приучили меня к очень критичному отношению к всевозможной критике. Без детального обоснования верить не привык

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

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

Если Вы настаиваете, мы, конечно, оставим Оккама, но про то, что "избыточность языка опять не к месту", не могу с Вами согласиться. Именно к месту - и это, если хотите, это одна из открытых проблем, как и изоморфизм графов. В это самое время по Интернету идет множество споров об оптимальной формализации статей по computer sci. и математике. Если хотите, могу дать ссылки, например, на англовики - там, как и в моем случае, этот вопрос отнюдь не праздный. И Ваша оговорка по Фрейду "Впрочем, если бы Вы изложили своё доказательство на формальном языке, то мы бы сейчас не дискутировали -- его смог бы проверить даже безмозглый компьютер" не случайна Что касаемо "безмозглого компьютера", то он с легкость доказывает теорему о четырех красках, однако скандал по этому поводу не утихает Все не так просто, как хотелось бы...

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

Нисколько не оспариваю Ваше право, как автора, писать статью так как Вы считаете нужным.

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

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

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

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

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

К чему весь этот ликбез? Я, например, Паскалю предпочитаю С или даже С++. Только, давайте, не будем начинать холливар по этому поводу.

Отвечу сначала на первый вопрос: ликбез к тому, чтобы всем и каждому, кто будет читать эту тему, продемонстрировать, что бывает недостаточно сказать "величина" для того, чтобы сравнивать на равенство. Можно еще было поговорить, как сравнивать бинарные деревья в зависимости от контекста задачи и т.д. Про холливар "C/C++ vs Pascal" - это моя любимая тема. В последнее время с востребованием многопоточного программирования акции С++ сильно упали, даже всевозможные ТВВ от Интела не сильно помогают, но Ok не будем уходить от темы. Статья написана с применением Pascal-like псевдокода, реализация алгоритма сделана на ОО Паскале (Delphi-7), поэтому я и далее буду при необходимости использовать всем понятный Паскаль.

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

Скажу честно -- введённые Вами структуры $W$ меня очаровали. Не помню, давали ли Вы им какое-либо название. Я их называю "индексы подобия" и, с Вашего позволения, буду их так называть в своих постах.
На множестве индексов подобия определена всего лишь одна операция -- сравнение. А на множестве матриц таких операций определено великое множество.
Любой математик, встретив в тексте слово "матрица", сразу же, на уровне подсознания, связывает данный объект с указанным множеством операций. А то, что под термином "матрица" Вы понимаете двухмерный массив -- ему будет невдомёк.
Дабы избежать такой двусмысленности, я и возражаю против использования термина "матрица" по отношению к индексам подобия. ИМХО, лучше их определять как "величины" -- тут двусмысленности возникнуть не может.

Спасибо! Что очаровали - это очень важно для статьи! Как бы математики не лицемерили, но элегантность не менее важна, чем формальное следование стандартным канонам И сразу подчеркну сделанное разграничение: чистая матиематика и computer sci. - разные дисциплины: первая - теоретическая, вторая - экспериментальная. Могу привести авторитетные мнения на этот счет. Но не желая отходить от темы, пока ограничусь замечанием на Ваше "Любой математик, встретив в тексте слово "матрица", сразу же, на уровне подсознания, связывает данный объект с указанным множеством операций" - в том-то и проблема, что чистому математику и алгоритмику бывает труднее найти взаимопонимание, чем физику и лирику Но возвращаясь к понятию матрица - полистав учебники по матричной/линейной алгебре, во многих увидим, как вводится понятие "матрица": матрица - это таблица. И уже дальше авторы учебника начинают вводить свойства для тех или иных матриц. У наших W-матриц пока интересно только одно свойство - равенство, но ведь ничто не мешает чистому математику изучить и другие свойства таких матриц

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

При построении биекции $r$, Вы слишком свободно манипулируете векторами $\bar w_h$ -- допустима любая их перестановка. Но это не правильно -- можно использовать лишь перестановки, сохраняющие матрицу $A^{-1}$. Если же Вы считаете допустимой любую перестановку, то это нужно доказывать.

Мои поздравления: только что в обсуждение введен новый термин "биекция", без которого и в статье и тут пока обходились - "Да здравствует Бритва!" Я-то совсем не против этого термина, но давайте хотя бы рувики посмотрим: "Биекция — это отображение, которое является одновременно и сюръективным и инъективным. При биективном отображении каждому элементу одного множества соответствует ровно один элемент другого множества, при этом, определено обратное отображение, которое обладает тем же свойством. Поэтому биективное отображение называют ещё взаимно-однозначным отображением (соответствием), одно-однозначным отображением." http://ru.wikipedia.org/w/index.php?tit ... d=32492153 Я про свое соответствие $r$ даже и таких условий не вводил! Это Вы уже заключили, что $r$ - биекция, а я не спорю. Но из процитированного Вами фрагмента:

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

Цитата:

So $W_i=W_p$ and so by definition of W-matrix (Definition 3) we have:

$$\bar w_h=\bar w_{r(h)},$$

$$sort(\bar a_h)=sort(\bar a_{r(h)}),$$

where $i=r(p),p=r(i)$; vector $\bar a_h=(k_{h1},k_{h2},\dots,k_{hn})$ is hth row of matrix $A^{-1}$.

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

[whitefox]

Уважаемый bin.

(Оффтоп)

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

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

Свою убежденность в не полиномиальности проблемы изоморфизма графов я нигде не декларировал. С чего Вы взяли?
Более того, я допускаю даже возможность $P=NP$.
Да, я полагаю Вашу Лемму1 ложной, но от сюда до убеждённости ещё очень далеко. И, хотя Лемма 1 эквивалентна проблеме изоморфизма, вполне допускаю существование других методов её (проблемы, а не леммы) решения.
Думаю, что и у Вашего алгоритма остался ещё потенциал для движения в этом направлении при замене Леммы 1 более адекватной.

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

Я же всегда открыт для конструктивной критики, однако 30 лет работы в системе РАН приучили меня к очень критичному отношению к всевозможной критике. Без детального обоснования верить не привык

Ладно, согласен считать, что мне показалось будто Вы с порога и без проверки отвергли моё безобидное замечание об опечатке.

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

И Ваша оговорка по Фрейду "Впрочем, если бы Вы изложили своё доказательство на формальном языке, то мы бы сейчас не дискутировали -- его смог бы проверить даже безмозглый компьютер" не случайна

Покончили с Оккамом -- переключились на Фрейда?
Старик сейчас, наверно, вертится как пропеллер.

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

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

Что касаемо четырёх красок, то там проблема в длине доказательства -- человеческой жизни не хватит на его проверку.
Не думаю, что формальное доказательство Леммы1 будет столь же длинным (это конечно если она верна).
Не хотите, чтобы Ваш вывод проверял "безмозглый компьютер" -- поручим это блондинке.
Работа чисто механическая, мозг не напрягает.

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

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

Изложу своё виденье ситуации.
После введения в Ваш алгоритм индексов подобия $W$, Вы привлекли Лемму 1 для доказательства его корректности. Но насколько Лемма 1 подходит для этой цели?
Она оказалась слишком сильной -- эквивалентна самой проблеме изоморфизма. И тем самым делает Ваш алгоритм не нужным для доказательства.
Но потенциал Вашего алгоритма не исчерпан. Нужно только ослабить Лемму 1.
Когда Ваш алгоритм для вершины $i$ графа $G$ подбирает соответствующую вершину $j$ графа $G'$, он все вершины-кандидаты пропускает через двойной фильтр:

• выполнение условия $W_i=W_j'$
• выполнение условия $j\in\mathfrak{U}_k'$

И поэтому для доказательства корректности алгоритма достаточно доказать, что из указанных двух условий следует подобие вершин $i$ и $j$ (разумеется если $G\cong G'$).
Возможно эта лемма будет слабее Леммы 1 (не эквивалентна проблеме изоморфизма). И тогда, возможно, её удастся доказать (для ослабленной леммы может существовать доказательство, хотя для сильной его нет).
Заметьте, что при этом Ваш алгоритм становится безусловно необходимым для доказательства полиномиальности проблемы изоморфизма.

(Оффтоп)

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

Про холливар "C/C++ vs Pascal" - это моя любимая тема.

Выходит я угадал?

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

У наших W-матриц пока интересно только одно свойство - равенство, но ведь ничто не мешает чистому математику изучить и другие свойства таких матриц

Наши индексы подобия $W$ (мои структуры в точности равны Вашим двумерным массивам из которых выброшены нулевые векторы $\bar z$) не проходят "утиный тест" на матрицу.
Индекс подобия безусловно похож на "утку" (матрицу), вот только он не "крякает как утка" (не используются сугубо матричные операции). И поэтому, имхо, нет достаточных оснований считать его "уткой" (матрицей).

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

Мои поздравления: только что в обсуждение введен новый термин "биекция", без которого и в статье и тут пока обходились - "Да здравствует Бритва!"

Спасибо, рад что оценили.
Термин "биекция", как и ранее термин "автоморфизм", я использовал умышленно, чтобы привлечь Ваше внимание к способу которым Вы строите соответствие $r$.
Это соответствие является перестановкой множества $V(G)$ -- множества вершин графа $G$. То есть $r$ это взаимно-однозначное отображение множества $V(G)$ на себя (иными словами "биекция"). Кроме того, соответствие $r$ обязано сохранять подобие вершин (этого условия у Вас нет, но оно необходимо) следовательно это "автоморфизм" графа $G$.
А так как мы декларируем свойство $r(i)=p$, то необходимо доказать существование автоморфизма с указанным свойством.

[bin]

Уважаемый whitefox,

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

Ладно, согласен считать, что мне показалось будто Вы с порога и без проверки отвергли моё безобидное замечание об опечатке.

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

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

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

Почему не хочу? Я был бы очень не против! Проблема в том, что я недостаточно знаю современный софт для автоматического доказательства теорем, даже не могу понять: по силам ли существующим программам моя задача?

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

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

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

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

Но насколько Лемма 1 подходит для этой цели?Она оказалась слишком сильной -- эквивалентна самой проблеме изоморфизма.

Если бы Лемма утверждала, что если W-матрицы равны, то графы изоморфны - она была бы эквивалентна проблеме изоморфизма. А так она утверждает подобие вершин только в случае изоморфных графов. Это утверждение гораздо слабее.

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

Это соответствие является перестановкой множества $V(G)$ -- множества вершин графа $G$. То есть $r$ это взаимно-однозначное отображение множества $V(G)$ на себя (иными словами "биекция"). Кроме того, соответствие $r$ обязано сохранять подобие вершин (этого условия у Вас нет, но оно необходимо) следовательно это "автоморфизм" графа $G$.
А так как мы декларируем свойство $r(i)=p$, то необходимо доказать существование автоморфизма с указанным свойством.

На данном этапе доказательства это соответствие ничего не обязано. Берем любое соответствие, для которого W-матрицы вершин i,p равны. Из факта, что матрицы равны, следует, что равны их соответствующие элементы (в частности, w-вектор вершины i равен w-вектору вершины p: $r(i)=p$), значит, такие соответствия есть. Для данного шага доказательства этого достаточно. А способ построения соответствия я уже описал ранее (i=5,p=3):

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

n предметов можно распределить по n ящикам, так, чтобы в каждом ящике оказалось по одному предмету. Два варианта такого распределения являются соответствием r, задаваемым, например, таблично: 1ый ящик: вариант 1 - предмет номер 5, вариант 2 - предмет номер 3; 2ой ящик: ...

[whitefox]

Уважаемый bin.

(Оффтоп)

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

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

Матрица смежности это святое.
Она и "крякает" и "плавает" и, вообще, всем "уткам"-- "Утка".

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

Если бы Лемма утверждала, что если W-матрицы равны, то графы изоморфны - она была бы эквивалентна проблеме изоморфизма.

Этот вывод легко следует из Леммы 1.

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

На данном этапе доказательства это соответствие ничего не обязано. Берем любое соответствие, для которого W-матрицы вершин i,p равны. Из факта, что матрицы равны, следует, что равны их соответствующие элементы (в частности, w-вектор вершины i равен w-вектору вершины p: $r(i)=p$), значит, такие соответствия есть. Для данного шага доказательства этого достаточно.

Вот в этом-то и есть проблема. Вполне может случиться, что $\bar w_i=\bar w_p$, а вершины $i$ и $p$ не подобны.

[bin]

Уважаемый whitefox,

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

Этот вывод легко следует из Леммы 1.

Как?

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

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

На данном этапе доказательства это соответствие ничего не обязано. Берем любое соответствие, для которого W-матрицы вершин i,p равны. Из факта, что матрицы равны, следует, что равны их соответствующие элементы (в частности, w-вектор вершины i равен w-вектору вершины p: $r(i)=p$), значит, такие соответствия есть. Для данного шага доказательства этого достаточно.

Вот в этом-то и есть проблема. Вполне может случиться, что $\bar w_i=\bar w_p$, а вершины $i$ и $p$ не подобны.

Из дальнейшего доказательства следует, что они подобны. Равны не только $\bar w_i=\bar w_p$, но и другие пары элементов W-матриц.

[whitefox]

Уважаемый bin.

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

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

Этот вывод легко следует из Леммы 1.

Как?

Из Леммы 1 следует, что индекс подобия $W$ является полным инвариантом класса подобных вершин. Следовательно совокупность индексов подобия всех вершин графа $G$ (мультимножество $W(G)$) является полным инвариантом графа $G$.

В своей статье Вы доказываете, что индекс подобия $W$ вычисляется за полиномиальное время, следовательно и полный инвариант $W(G)$ графа $G$ также вычисляется за полиномиальное время.

А это и означает решение проблемы изоморфизма графов (найти полный инвариант графа, вычислимый за полиномиальное время).

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

Из дальнейшего доказательства следует, что они подобны. Равны не только $\bar w_i=\bar w_p$, но и другие пары элементов W-матриц.

Правильно ли я Вас понял, что Вы утверждаете следующее: "Если индексы подобия $W_i$ и $W_p$ равны, то вершины $i$ и $p$ подобны."