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

[bin]

Уважаемый whitefox,

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

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

Вот именно, что на разные лады - не прошла одна подмена, Вы тут же делаете другую подмену

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

А именно на то, что у Вас отсутствует обоснование корректности применяемого метода построения соответствия $r$.

Что Вы понимаете под "корректности применяемого метода построения" на этот раз? Я же уже отметил самоочевидный факт, что n предметов всегда можно разложить по n ящикам, чтобы в каждом ящике оказалось по одному предмету. Вы сомневаетесь, что в случае равенства W-матриц ($W_i=W_p$) всегда найдутся такие $r$, для которых будет выполнятся $\bar w_h=\bar w_{r(h)}$, т.е. Вы считаете, что возможен случай, когда $\bar w_h \neq \bar w_{r(h)}$ для всех $r$, для которых $i=r(p)$? И как же быть с равенством матриц в таком случае?

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

Поэтому неразумно "школьное доказательство" принимать за эталон математической строгости.

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

[whitefox]

Уважаемый bin.

(Оффтоп)

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

Вот именно, что на разные лады - не прошла одна подмена, Вы тут же делаете другую подмену

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

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

Что Вы понимаете под "корректности применяемого метода построения" на этот раз?

Тоже, что и раньше -- соответствие $r$ корректно, если вершины $i$ и $p$ подобны.

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

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

Модифицированный принцип Дирихле?

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

Вы сомневаетесь, что в случае равенства W-матриц ($W_i=W_p$) всегда найдутся такие $r$, для которых будет выполнятся $\bar w_h=\bar w_{r(h)}$, т.е. Вы считаете, что возможен случай, когда $\bar w_h \neq \bar w_{r(h)}$ для всех $r$, для которых $i=r(p)$?

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

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

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

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

Я так понял, что моё возражение:

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

у Вас отсутствует обоснование корректности применяемого метода построения соответствия $r$. Без этого обоснования Ваше доказательство не может считаться строгим.

Вы опровергнуть не можете?

[bin]

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

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

Вы сомневаетесь, что в случае равенства W-матриц ($W_i=W_p$) всегда найдутся такие $r$, для которых будет выполнятся $\bar w_h=\bar w_{r(h)}$, т.е. Вы считаете, что возможен случай, когда $\bar w_h \neq \bar w_{r(h)}$ для всех $r$, для которых $i=r(p)$? И как же быть с равенством матриц в таком случае?

Вы не ответили по существу. В посте ранее я спросил:

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

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

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

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

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

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

[whitefox]

Уважаемый bin.

(Оффтоп)

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

Прежде всего у Вас отсутствует достаточное обоснование Вашего возражения.

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

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

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

То Вы должны это утверждение опровергнуть, а не требовать от оппонента (рецензента) обоснования его возражения.

И всё же,чисто из спортивного интереса, хотелось бы знать, что именно необоснованного в моём возражении Вы находите? Может быть это:

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

у Вас отсутствует обоснование корректности применяемого метода построения соответствия $r$

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

А может необоснованным Вам кажется следующее:

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

Без этого обоснования Ваше доказательство не может считаться строгим.

Здесь аргументация основывается на общепринятом правиле -- не может считаться строгим доказательство использующее методы необоснованные должным образом. И эту часть моего возражения Вы могли бы легко опровергнуть -- показать, что отсутствие обоснования корректности применяемого метода построения соответствия $r$, не нарушает строгости Вашего доказательства Леммы 1.

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

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

но Ваше "возражение" я уже не раз опровергал выше.

А цитату с таким "опровержением" Вы просто забыли привести?

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

Так, например, в предыдущем посте я спросил:

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

Вы сомневаетесь, что в случае равенства W-матриц ($W_i=W_p$) всегда найдутся такие $r$, для которых будет выполнятся $\bar w_h=\bar w_{r(h)}$, т.е. Вы считаете, что возможен случай, когда $\bar w_h \neq \bar w_{r(h)}$ для всех $r$, для которых $i=r(p)$? И как же быть с равенством матриц в таком случае?

Вы не ответили по существу.

Простите великодушно. Я принял это за шутку.
Ответ-то очевиден, он заложен в самом вопросе.
Нет не считаю. Теперь Вы удовлетворены?
Со своей стороны замечу, что утверждал нечто иное:

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

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

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

В посте ранее я спросил:

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

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

Вы опять же не ответили по существу.

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

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

Т.о., оказывается, что Ваше возражение – чистой воды демагогия

Демагогия это Ваш последний пост. Вместо ответа по существу на моё возражение -- отвечаете по принципу "сам дурак".

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

Вы всеми силами «на разные лады» уклоняетесь от ответа на неудобные Вам вопросы.

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

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

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

В том-то и дело, что не упоминаете. Хотя в дальнейшем выводе используете.

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

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

Вот Вам образчик демагогии.

Ответе, пожалуйста, на следующий вопрос: можете ли Вы опровергнуть моё возражение

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

у Вас отсутствует обоснование корректности применяемого метода построения соответствия $r$. Без этого обоснования Ваше доказательство не может считаться строгим.

[bin]

Уважаемый whitefox,
Наконец услышал от Вас нечто новое по существу:

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

А с той самой стати, что при дальнейшем выводе Вы это самое подобие используете.

Укажите точно: где при дальнейшем выводе используется это самое подобие?

(Оффтоп)

(Раз Вам недостаточно просто знака вопроса, отметил двумя смайликами - этот вопрос не риторический, так же как и другие конкретные вопросы к Вам. Обычно это бывает ясно из контекста.)

Некоторые другие пассажи я откоментирую после получения ответа на заданный вопрос.

[whitefox]

Уважаемый bin.

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

Укажите точно: где при дальнейшем выводе используется это самое подобие?

Цитата:

By Conclusion 2, it follows that the permutation $r$ for the graph $G$ and the permutation $t$ for the graph $G'$ give isomorphic mapping of these graphs such that vertices $i,j$ are similar.

А это возможно только если подобны вершины $i$ и $p$.

[bin]

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

Цитата:

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

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

[Pavlovsky]

http://www.dharwadker.org/tevet/isomorphism/
Thus, we have a polynomial-time algorithm for solving the graph isomorphism problem, showing that the graph isomorphism problem is in P.

[bin]

Pavlovsky в сообщении #431447 писал(а):

http://www.dharwadker.org/tevet/isomorphism/
Thus, we have a polynomial-time algorithm for solving the graph isomorphism problem, showing that the graph isomorphism problem is in P.

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

[whitefox]

Уважаемый bin.
Вы задали вопрос:

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

Укажите точно: где при дальнейшем выводе используется это самое подобие?

(подчёркнуто мной)
Я привёл цитату из Вашей статьи

Цитата:

By Conclusion 2, it follows that the permutation $r$ for the graph $G$ and the permutation $t$ for the graph $G'$ give isomorphic mapping of these graphs such that vertices $i,j$ are similar.

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

(Оффтоп)

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

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

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

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

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

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

[bin]

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

[whitefox]

Уважаемый bin.
Пожалуйста, перестаньте флудить и заниматься демагогией.
Просто ответьте на вопрос: Можете ли Вы опровергнуть следующее возражение

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

у Вас отсутствует обоснование корректности применяемого метода построения соответствия $r$. Без этого обоснования Ваше доказательство не может считаться строгим.

[bin]

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

[whitefox]

Уважаемый bin.
Вы правы, повторяться не нужно.
Ответ на мой вопрос очевиден.

[Circiter]

2bin
Не хотел мешать вашей дискуссии с whitefox'ом. Но теперь спрошу (может быть даже это уже спрашивали, но я невнимательно читал тему в начале). Кажется, вы упоминали связь с $\mathrm{P}=\mathrm{NP}$. А что известно о $\mathrm{NP}$-тости у задачи проверки изоморфизма графов? Это до сих пор открытый вопрос или движение есть?