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

[bin]

Уважаемый whitefox,
Что Вы понимаете под словами "полный инвариант класса подобных вершин"? Лемма 1 не исключает возможности существования двух неизоморфных графов, где найдется пара вершин с равными W-матрицами. Более того, Лемма 1 не исключает возможности существования двух неизоморфных графов, где все W-матрицы будут попарно равны. Лемма 1 исключает только возможность существования пары неподобных вершин с равными W-матрицами для изоморфных графов.

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

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

Да, но для одного и того же графа.

[whitefox]

Уважаемый bin.

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

Что Вы понимаете под словами "полный инвариант класса подобных вершин"?

Полный инвариант класса подобных вершин это любая величина $\alpha$, обладающая свойством: вершины $i$ и $p$ подобны тогда и только тогда, когда равны $\alpha_i$ и $\alpha_p$.

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

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

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

Да, но для одного и того же графа.

Вспомните, пожалуйста, что я писал в своём первом посте:

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

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

[bin]

Уважаемый whitefox,

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

Вспомните, пожалуйста, что я писал в своём первом посте:

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

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

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

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 в сообщении #429061 писал(а):

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

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

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

"Из дальнейшего доказательства"! А не "Здесь"! Не в цитированном Вами куске.

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

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

Почему может случиться? Дальнейшее доказательство показывает, что такого случиться не может. Дальнейшее! Чтобы утверждать, что $r(h)=h$, где $r(i)=p$ нам не нужно знать подобны ли эти вершины.

[whitefox]

Уважаемый bin.

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

"Из дальнейшего доказательства"! А не "Здесь"! Не в цитированном Вами куске.

Надо ли понимать Вас так, что у Вас доказательство утверждения $(W_i=W_p)\Rightarrow(\textit{вершины }i\textit{ и }p\textit{ подобны})$ всё же имеется, но только "в дальнейшем"?
Тогда где оно?
И почему Вы его используете "здесь", а доказываете только "в дальнейшем"?
А обратили ли Вы внимание, что данное утверждение эквивалентно Лемме 1?
И Вы таким образом ходите по порочному кругу, выводя доказательство Леммы 1 из самой Леммы 1.

[bin]

Уважаемый whitefox,
Ваша цитата из моей статьи, о каковой цитате речь:

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}$.

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

[whitefox]

Уважаемый bin.

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

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

В процитированном фрагменте нас очень волнует подобие вершин. А буде это не так, мы сразу столкнёмся с проблемой:

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

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

Более того, вполне может случиться, что $W_i=W_p$, а вершины $i$ и $p$ не подобны.

[bin]

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

[whitefox]

Уважаемый bin.

(Оффтоп)

Такие вот пассажи:

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

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

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

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

ума не могу приложить,что Вас так взволновало в этом, процитированном Вами, фрагменте?!

В дальнейшем буду утверждение $(W_i=W_p)\Rightarrow(\textit{вершины }i\textit{ и }p\textit{ подобны})$ упоминать как Утверждение А.
Обратите, пожалуйста, внимание на то, как строится соответствие $r$.
Возможны два пути:

• Первый (по которому Вы идёте) предполагает выбирать соответствие $r$ из максимально-возможной совокупности перестановок множества $V(G)$, ограниченной только условием $r(i)=p$. На этом пути мы обязательно столкнёмся с трудностью:
  whitefox в сообщении #429257 писал(а):

  вполне может случиться, что $W_i=W_p$, а вершины $i$ и $p$ не подобны.

  Дабы эту трудность преодолеть мы вынуждены привлечь Утверждение А. Только делать это нужно явно, и нужно привести его доказательство.
  К сожалению, первый путь плох тем, что Утверждение А эквивалентно Лемме 1. И мы попадаем в порочный круг -- выводим Лемму 1 из самой Леммы 1.
• Второй путь предполагает ограничить свободу выбора соответствия $r$ множеством автоморфизмов графа $G$. На этом пути, отмеченная мной, трудность появиться уже не может. Только теперь нам придётся доказывать существование автоморфизма $r$ со свойством $r(i)=p$.

(Оффтоп)

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

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

Вы, что же, серьёзно считаете будто доказательство, существенным образом основанное на Утверждение А, но даже не упоминающее о нём, можно назвать строгим?

[whitefox]

(Оффтоп)

Мы с Вами здесь не в пинг-понг играем (пост налево, пост направо). А ведём конструктивную дискуссию (я так полагаю). А это, знаете ли, не базарный спор. В конструктивной дискуссии победителей не бывает. У неё одна цель -- установить истину. Обвинять оппонента в отсутствии аргументов это, по меньшей мере, "не спортивно". Тем более, что свои аргументы я предлагал Вам не однократно. Если что-то осталось не понято -- достаточно переспросить, а не кидаться голословными обвинениями.

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

[bin]

Уважаемый whitefox,
Почему Вы решили, что я искажаю имя именно С++? Кроме него, есть еще и просто С, и C# Имею также полное право говорить о некотором гипотетическом языке, которому выбрать имя по своему усмотрению. Это в традициях обсуждений языков. Так, например, в свое время в солидном американском журнале был критический анализ Виртовских языков, в котором известный и уважаемый автор заявил, что после Паскаля и Модулы нас, видимо, ждет Пасдула. И никто на него за это не обижался. Почему Вы также считаете, что попытка сравнения языков означает холливар? Имею кучу примеров, опровергающих столь примитивный взгляд. Но, повторюсь, подобное обсуждение нужно вести не в этой теме. Далее, я со своей стороны точно не собираюсь играть здесь в пинг-понг. Однако разговор с Вами действительно пошел по третьему кругу из-за того, что Вы настаиваете на необоснованном заявлении, которое называете Утверждением А. Вы прекрасно знаете, что уже в элементарной геометрии на уровне средней школы широко используется подход, при котором в начале решения задачи делается некоторое построение, а потом производится анализ того, что получилось. Высказывать какие-то подозрения типа Утверждения А до анализа, мягко говоря, не принято, потому что преждевременно. У меня также сделано построение, но его анализ, приведенный в статье, Вы обсуждать не хотите, вместо этого Вы постоянно пытаетесь приписать моему построению допущения, которых там нет. Если Вы спросите: может случиться, что вершины не подобны? то в построении ответа на этот вопрос не найдете, так как в части своего построения я этот вопрос не рассматриваю и требования подобия не ввожу, поэтому на Ваш вопрос о подобии ответит не обсуждаемое здесь по третьему кругу построение, а его дальнейший анализ, приведенный в статье. После знакомства с этим анализом окажется, что так случиться не могло. Но этот вывод будет сделан только в конечном результате анализа. И никакого порочного круга в таком традиционно проведенном доказательстве нет.

Еще раз повторю: имею полное право взять вершины с равными W-матрицами и посмотреть, каким вершинам соответствуют попарно равные элементы этих матриц, и только на основании этого осмотра записать соответствие r. Никаких слов о подобии при этом сказано не было!

[whitefox]

Уважаемый bin.

(Оффтоп)

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

Почему Вы решили, что я искажаю имя именно С++? Кроме него, есть еще и просто С, и C# Имею также полное право говорить о некотором гипотетическом языке, которому выбрать имя по своему усмотрению. Это в традициях обсуждений языков. Так, например, в свое время в солидном американском журнале был критический анализ Виртовских языков, в котором известный и уважаемый автор заявил, что после Паскаля и Модулы нас, видимо, ждет Пасдула. И никто на него за это не обижался. Почему Вы также считаете, что попытка сравнения языков означает холливар? Имею кучу примеров, опровергающих столь примитивный взгляд. Но, повторюсь, подобное обсуждение нужно вести не в этой теме.

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

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

Ну насчёт "необоснованного" Вы погорячились.
В конце концов, Вы и сами его утверждали:

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

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

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

Да, но для одного и того же графа.

Причём, сделали это в обоснование корректности построения соответствия $r$:

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

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

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

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

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

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

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

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

Вашу статью я изучал очень внимательно и неоднократно. И что-то не припомню, чтобы Вы анализировали корректность построения соответствия $r$. А именно, что при выбранном способе построения соответствия $r$ исключён случай $(W_i=W_p)\&(\textit{вершины }i\textit{ и }p\textit{ не подобны})$. Если я ошибаюсь -- приведите, пожалуйста, цитату. Согласен её обсудить.

(Оффтоп)

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

вместо этого Вы постоянно пытаетесь приписать моему построению допущения, которых там нет.

В том-то и дело, что нет, хотя быть должны.

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

Еще раз повторю: имею полное право взять вершины с равными W-матрицами и посмотреть, каким вершинам соответствуют попарно равные элементы этих матриц, и только на основании этого осмотра записать соответствие r. Никаких слов о подобии при этом сказано не было!

Взять-то Вы конечно можете, только не забывайте о необходимости привести доказательство корректности выбора, то есть, что вершины $i$ и $p$ подобны. Если у Вас такое доказательство есть -- приведите, пожалуйста, цитату. Я такого доказательства в Вашей статье не встречал.

[whitefox]

Правильно ли я Вас понял, что называя Утверждение А необоснованным, Вы тем самым утверждаете его ложность

[bin]

Уважаемый whitefox,

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

Ну школярам позволительно делать ошибки

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

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

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

Еще раз повторю: имею полное право взять вершины с равными W-матрицами и посмотреть, каким вершинам соответствуют попарно равные элементы этих матриц, и только на основании этого осмотра записать соответствие r. Никаких слов о подобии при этом сказано не было!

Взять-то Вы конечно можете, только не забывайте о необходимости привести доказательство корректности выбора, то есть, что вершины $i$ и $p$ подобны.

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

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

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

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

[whitefox]

Уважаемый bin.
Я уже неоднократно, на разные лады, пытался обратить Ваше внимание на существенный пробел в доказательстве Леммы 1

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

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

А именно на то, что у Вас отсутствует обоснование корректности применяемого метода построения соответствия $r$. Без этого обоснования Ваше доказательство не может считаться строгим.
В ответ всегда слышал: "это видно из дальнейшего анализа".
Каждый раз заново пересматривал Вашу статью, но ничего подобного не видел.
Ну раз я от природы такой не внимательный, то помогите мне -- приведите цитату с этим обоснованием.

(Оффтоп)

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

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

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

[whitefox]

(Оффтоп)

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

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

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