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

[ha]

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

[bin]

ha
действительно! Что на такое ничто, как у Вас, ответить? А Вы еще спрашивали, в чем различие между Вашей методологией и Лакатосом! У меня может и не отшлифованное, но обоснование, а у Вас "верую - ибо это абсурдно" (Credo quia absurdum) и никаких обоснований, в том числе и того, что у меня "ошибка". Воистинну научный подход. Пока что это у Вас ничего получается. Опровергнуть аргументированно не можете, а согласиться вера не позволяет Самоизоляция математики на марше. Ура

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

[bin]

Т: Если $G_{0}\cong G_{0}'$, и мы можем находить список подобных вершин за полиномиальное время, то мы можем найти изоморфизм за полиномиальное время.
Доказательство. $G_{0}\cong G'_{0}$ , вершины $u,v'$ подобны $\Rightarrow G_{0}-u\cong G'_{0}-v'$ (Харари, Теория графов, С.202). Будем последовательно удалять подобные вершины из графов, получим последовательности:

$$ G_{0},G_{1},...,G_{n-1}$$

$$ G'_{0},G'_{1},...,G'_{n-1}$$

Для этого мы каждый раз после удаления вершины определяем новые списки подобных вершин для полученных графов. Т.к. по условию мы можем находить эти списки за полиномиальное время, то вычисление данных последовательностей займет полиномиальное время. Изоморфизм графов, состоящих из одной вершины $G_{n-1},G'_{n-1}$, тривиален. Пусть мы нашли изоморфизм $G_{i}\cong G'_{i}$, тогда, зная этот изоморфизм, мы добавляем к нему новое отображение для удаленных вершин $u\leftrightarrow v'$ и получаем изоморфизм $G_{i-1}\cong G'_{i-1}$. Т.о. двигаясь от $G_{n-1},G'_{n-1}$ , мы доходим до $G_{0},G'_{0}$ за полиномиальное время. ЧТД.

[ha]

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

Ваш последний пост уже является доказательством. Только оно не правильное. Контрпример из 3 вершин сможете построить?

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

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

[whitefox]

Хорошая попытка.
Жаль неудачная.

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

Контрпример из 3 вершин сможете построить?

[Toucan]

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

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

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

[bin]

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

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

А причем здесь Р1? Возможно, данную теорему я использую для модификации Р1. Про «никаких СЛУ» – не совсем так. Если помните, я нахожу подобие вершин этими СЛУ. Но в данном доказательстве способ, которым мы находим подобие, не учитывается. Зачем Вы валите все в одну кучу, да еще столь примитивным образом? При внимательном рассмотрении этот Ваш прием оказывается совершенно беспомощным. Он может быть рассчитан только на читателя, который не помнит деталей. Это называется бросить тень мелким замечанием, сделанным между прочим. Такой прием иногда используют в желтой прессе, но для солидного научного обсужденния подобные приемы просто неприличны.

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

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

ha, ну почитайте Вы, наконец, Лакатоса! Это позволит избавиться от детского максимализма. В частности, на с. 54 Вы прочтете:

Цитата:

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

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

Как же возникают математические знания? Уже на с.17 Лакатос отмечает:

Цитата:

Полья подчеркивает: «Вы должны угадать математическую теорему, прежде чем вы ее докажете»

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

Цитата:

Альфа. Но ведь это еще хуже, чем раньше. Вместо одной догадки мы теперь имеем по меньшей мере три! И вы называете это «доказательством»!
Учитель. Я допускаю, что традиционное название «доказательство» для этого мысленного эксперимента, пожалуй, не совсем подходит. Я не думаю, что этот эксперимент устанавливает истинность догадки.
Дельта. Ну а что же он тогда делает? Что же, по-вашему, доказывает математическое доказательство?
Учитель. Это тонкий вопрос, на который мы попытаемся ответить позже. До тех пор я предлагаю сохранить освященный временем технический термин «доказательство» для мысленного эксперимента, или квазиэксперимента, который предлагает разложение первоначальной догадки на вспомогательные догадки или леммы, таким образом впутывая ее, может быть, в совершенно далекую область знания. (С.16-17)

Цитата:

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

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

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

Цитата:

Альфа. Так, вы теперь снимете свое доказательство?
Учитель. Нет. Критика не всегда будет необходимо разрушением. Я просто исправлю мое доказательство, чтобы оно устояло против этой критики. (С.19)

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

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

Ваш последний пост уже является доказательством. Только оно не правильное. Контрпример из 3 вершин сможете построить?

Конечно, не смогу;) Перебрал все графы с тремя вершинами – благо их немного, но что Вы имеете в виду, не понял. Поучитесь у Лакатоса, как надо представлять и обосновывать контрпримеры! Заметьте при этом, что

Цитата:

Подозрение — это еще не критика. (С.18)

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

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

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

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

Если уж даже такую проблему автор не может решить, то куда ему до решения задачи изоморфизма графов?

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

ha, с того самого момента, как Вы приняли участие в этом обсуждении, Вы пытаетесь играть роль «адвоката дьявола». Это вполне почетная роль, нужность которой подтверждается богатой исторической традицией. Но, к сожалению, роль эта дается Вам очень плохо. Ужасающее незнание базовых принципов научной методологии, помноженное на Ваш низкий уровень в отношении культуры ведения научной дискуссии, заставляют постоянно отвлекаться от темы на вопросы регламента. Чувствуешь себя как в каком-нибудь парламенте среди прожженных политиканов, а не как в научном сообществе среди коллег. Приходится напомнить, что модератор сделал Вам не первое замечание за недопустимые для научного обсуждения выражения. Прошу Вас, сделайте из этого выводы и вернитесь в тему обсуждения! Такое обсуждение, если Вы в нем хотите участвовать, не требует от Вас «излишнего» дружелюбия к собеседникам и оппонентам, но элементарные нормы приличия, обязательные для воспитанных людей, можно соблюдать? Все-таки мы не в подворотне бутылку портвеша на троих распиваем!

whitefox

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

Хорошая попытка.
Жаль неудачная.

Спасибо за "хорошая"! А почему неудачная. У Вас есть опровержение? - Тогда ознакомьте, пожалуйста!

[whitefox]

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

Спасибо за "хорошая"! А почему неудачная. У Вас есть опровержение? - Тогда ознакомьте, пожалуйста!

Пусть $G$ -- цепь длины два с вершинами $1,2,3$.
А $G'$ -- такая же цепь с вершинами $1',2',3'$.
Пусть на первом шаге алгоритм установит соответствие 1-1', на втором шаге -- соответствие 2-3', и на третьем -- 3-2'.
Полученное отображение не является изоморфизмом графов $G$ и $G'$.

[bin]

whitefox
Да, спасибо. А что сразу было так не написать? Сэкономили бы время и себе, и мне. Вы, похоже, тоже считаете, что эта тема для детской игры Угадайка. Тогда давайте я отвечу в стиле ha: сможете сообразить, какое тривиальное улучшение я могу сразу предложить для преодоления этого тривиального контрпримера? Жду Вашего решения

PS Полезно отметить, что в отношении моих двух предыдущих догадок такой незамедлительной реакции опровержением не последовало до сих пор. Из этого следует очевидный вывод, что когда можете, то опровергаете, а когда не можете, то, по выражению классика, «развозите манную кашу по чистому столу». С сожалением должен отметить , что ваши (с ha) игры слишком тривиальны для решения (или нерешения) столь великой проблемы. И Вам тоже стоит почитать Лакатоса!

PPS В отношении P1 и Вы, и ha высказали только подозрения. Что не есть критика. Теперь попробуйте найти связь между моей "неудачной" (пока) теоремой и P1 (в P1 условия более жесткие). А далее еще открыт вопрос в отношении предложенного способа поиска подобных вершин. Пока критики я не услышал, а слышал только подозрения.

[whitefox]

(Лакатос)

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

И Вам тоже стоит почитать Лакатоса! ;-)

Спасибо за совет. Лакатоса перечитал. Только что.

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

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

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

Контрпример действительно тривиальный. И, следуя рекомендациям Лакатоса, Вы бы его не пропустили:

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

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

Ваш последний пост уже является доказательством. Только оно не правильное. Контрпример из 3 вершин сможете построить?

Конечно, не смогу;) Перебрал все графы с тремя вершинами – благо их немного, но что Вы имеете в виду, не понял.

А вот улучшения ни тривиального, ни супер нетривиального, и при этом полиномиального, я предложить не могу. Подозреваю, что и Вы не можете.
Проблема в том, что вершины подобные для графов $G_0$ и $G'_0$ могут оказаться не подобными для графов $G_1$ и $G'_1$, и наоборот.

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

Полезно отметить, что в отношении моих двух предыдущих догадок такой незамедлительной реакции опровержением не последовало до сих пор. Из этого следует очевидный вывод, что когда можете, то опровергаете, а когда не можете, то, по выражению классика, «развозите манную кашу по чистому столу».

Реакции не последовало потому, что опровергать нечего. По причине отсутствия доказательства.

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

С сожалением должен отметить , что ваши (с ha) игры слишком тривиальны для решения (или нерешения) столь великой проблемы.

Слишком тривиальны Ваши ошибки поэтому их опровержения тоже тривиальны.

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

В отношении P1 и Вы, и ha высказали только подозрения. Что не есть критика.

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

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

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

-- 14 июл 2011, 09:22 --

(Критика)

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

Пока критики я не услышал, а слышал только подозрения.

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

[ha]

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

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

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

А причем здесь Р1? Возможно, данную теорему я использую для модификации Р1.

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

Цитата:

Про «никаких СЛУ» – не совсем так. Если помните, я нахожу подобие вершин этими СЛУ. Но в данном доказательстве способ, которым мы находим подобие, не учитывается. Зачем Вы валите все в одну кучу, да еще столь примитивным образом?

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

Цитата:

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

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

Цитата:

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

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

ha, ну почитайте Вы, наконец, Лакатоса! Это позволит избавиться от детского максимализма.

Ну почитайте же вы наконец критику Лакатоса. Это позволит избавиться от детского пофигизма к строгости доказательств.

Цитата:

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

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

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

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

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

Цитата:

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

Если уж даже такую проблему автор не может решить, то куда ему до решения задачи изоморфизма графов?

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

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

Цитата:

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

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

-- Чт июл 14, 2011 11:21:36 --

Цитата:

Реакции не последовало потому, что опровергать нечего. По причине отсутствия доказательства.

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

-- Чт июл 14, 2011 11:34:52 --

Цитата:

Широкую известность получила его книга "Доказательства и опровержения", в которой Лакатос предложил собственную модель формирования и развития понятий в "содержательной" математике XVII—XVIII вв.

Задумайтесь над тем, почему Лакатос жил в 20 веке, а его модель к 20 веку не относится.

[bin]

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

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

Нужно задать порядок удаления вершин обходом в ширину исходных графов: выбираем пару подобных вершин $u,v'$ и ставим на них метку 1. Т.к. эти вершины подобны, то для каждого соседа $p_i$ вершины $u$ найдется подобный сосед $p'_i$ вершины $v'$. Эти пары подобных соседей ($p_i,p'_i$) получают метки 2,3,... Отметив таким образом соседей вершин с меткой 1, переходим к вершинам с меткой 2 и помечаем их непомеченных соседей следующими неиспользованными метками и т.д., пока не отметим все вершины $n$ метками. Удаление вершин производим в порядке меток, т.е. графы $G_i,G'_i$ получаются удалением вершин с меткой $i$.

-- Чт июл 14, 2011 16:42:01 --

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

Слишком тривиальны Ваши ошибки поэтому их опровержения тоже тривиальны.

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

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

Со своей стороны могу посоветовать Вам не только читать Лакатоса, но и следовать его рекомендациям. Например, одновременно с доказательством искать и опровержение своей теоремы.

Со стороны ошибки видятся лучше. Зачем иначе нужны были бы проверяющие, рецензенты, редакторы? Зачем нужны были бы подобные обсуждения? Неужели для детского спора, кто самый умный и кто больше всех знает? Кроме того, обсуждение даже ошибочного предположения может натолкнуть на идею для его исправления. Поэтому некоторые сырые предположения стоит обсуждать. У меня 30 летний опыт работы в ведущем НИИ РАН, и могу припомнить много обсуждений с участием видных специалистов (вплоть до академиков), где в начале обсудалась полная чушь, но постепенно в ходе обсуждения из нее формировалась идея, оказавшаяся потом очень полезной.

[whitefox]

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

Нужно задать порядок удаления вершин обходом в ширину исходных графов: выбираем пару подобных вершин $u,v'$ и ставим на них метку 1. Т.к. эти вершины подобны, то для каждого соседа $p_i$ вершины $u$ найдется подобный сосед $p'_i$ вершины $v'$. Эти пары подобных соседей ($p_i,p'_i$) получают метки 2,3,... Отметив таким образом соседей вершин с меткой 1, переходим к вершинам с меткой 2 и помечаем их непомеченных соседей следующими неиспользованными метками и т.д., пока не отметим все вершины $n$ метками. Удаление вершин производим в порядке меток, т.е. графы $G_i,G'_i$ получаются удалением вершин с меткой $i$.

А доказательство, что этот алгоритм решает указанную проблему:

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

Проблема в том, что вершины подобные для графов $G_0$ и $G'_0$ могут оказаться не подобными для графов $G_1$ и $G'_1$, и наоборот.

Вы опять не привели. Так что опровергать нечего.

[bin]

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

Реакции не последовало потому, что опровергать нечего. По причине отсутствия доказательства.

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

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

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

Нужно задать порядок удаления вершин обходом в ширину исходных графов: выбираем пару подобных вершин $u,v'$ и ставим на них метку 1. Т.к. эти вершины подобны, то для каждого соседа $p_i$ вершины $u$ найдется подобный сосед $p'_i$ вершины $v'$. Эти пары подобных соседей ($p_i,p'_i$) получают метки 2,3,... Отметив таким образом соседей вершин с меткой 1, переходим к вершинам с меткой 2 и помечаем их непомеченных соседей следующими неиспользованными метками и т.д., пока не отметим все вершины $n$ метками. Удаление вершин производим в порядке меток, т.е. графы $G_i,G'_i$ получаются удалением вершин с меткой $i$.

А доказательство, что этот алгоритм решает указанную проблему:

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

Проблема в том, что вершины подобные для графов $G_0$ и $G'_0$ могут оказаться не подобными для графов $G_1$ и $G'_1$, и наоборот.

Вы опять не привели. Так что опровергать нечего.

Была предложена идея. Детализация этой идеи вполне достаточна для обсуждения.

[whitefox]

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

Была предложена идея. Детализация этой идеи вполне достаточна для обсуждения.

А раз так, то тогда, пожалуйста, не требуйте опровержений.