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

[bin]

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

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

Не понял вопроса: а в чем проблема? Возьмем цикл $C_6$, где все подобны, после удаления пары подобных, получим цепь, где концевые вершины не подобны другим. И очень хорошо. Что тут доказывать?

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

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

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

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

Ok! Не требую опровержений, а прошу обсуждения

-- Чт июл 14, 2011 17:14:50 --

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

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

Нет, это не так. Перичитайте мои ответы. Вчера Вы привели контрпример - я согласился, ранее Вы нашли ошибку в Р1 - я согласился и т.д.

-- Чт июл 14, 2011 17:25:45 --

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

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

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

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

Ранее я уже ответил на это и подобные подозрения: http://dxdy.ru/post466454.html#p466454

-- Чт июл 14, 2011 17:32:05 --

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

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

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

-- Чт июл 14, 2011 17:41:54 --

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

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

Какую конкретно критику Вы имеете в виду? И где у меня "пофигизм"? Я нередко специально отмечаю, что предлагаю для предварительного обсуждения. А Вы постоянно пытаетесь уличить меня, делая вид, что это не рабочий черновик, а окончательная версия.

-- Чт июл 14, 2011 17:49:38 --

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

А зачем мне вам помогать?

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

-- Чт июл 14, 2011 17:54:51 --

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

Цитата:

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

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

Откуда цитата? В ней не сказано, что "его модель к 20 веку не относится". ИМХО, его модель и к 21 веку относится.

-- Чт июл 14, 2011 18:03:53 --

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

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

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

[bin]

PS модель Лакатоса: XVII—XVIII вв. – это только материал для модели, обучающая выборка в терминах AI, применимость модели всегда шире обучающей выборки, иначе модель не будет иметь никакого практического смысла.

[whitefox]

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

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

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

Не понял вопроса: а в чем проблема? Возьмем цикл $C_6$, где все подобны, после удаления пары подобных, получим цепь, где концевые вершины не подобны другим. И очень хорошо. Что тут доказывать?

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

-- 14 июл 2011, 18:37 --

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

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

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

Ранее я уже ответил на это и подобные подозрения: post466454.html#p466454

Это не подозрение, и даже не критика -- это факт. В своём ответе Вы его обходите стороной.

[ha]

Цитата:

И где у меня "пофигизм"?

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

Цитата:

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

А предварительные версии тут никому не интересны. Если у вас окончательной версии нет - так и запишем, что автор признал полное отсутствие доказательства.

Цитата:

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

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

Цитата:

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

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

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

Я вам про математику, а вы мне про программирование. Подмена достойная бульварной газеты. Я прочел множество книг по математики и в них почему-то не было тривиальных ошибок. Так что не надо опускать математику до своего уровня. Ради вас никто планку понижать не будет. Не можете доказывать без ошибок - так не посылайте статьи в математические журналы и не хвалитесь, что решили великую проблему. Можете исследовать для себя сколько угодно, а математикам занимающихся делом - не мешайте.

PS А ваш новый вариант легко опровергается контрпримером из 4 вершин. Сможете построить? Или эта задачка слишком сложна для вас: "Перебрал все графы с тремя вершинами – благо их немного, но что Вы имеете в виду, не понял."?

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

[bin]

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

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

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

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

Не понял вопроса: а в чем проблема? Возьмем цикл $C_6$, где все подобны, после удаления пары подобных, получим цепь, где концевые вершины не подобны другим. И очень хорошо. Что тут доказывать?

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

Благодарю за разъяснение. Пусть нам известно подмножество $S$ изоморфизмов графов $G_0,G'_0$, для которого выполняется $u\leftrightarrow v'$. Попарно подобные вершины соединены попарно подобными ребрами $(u,p_i)$, $(v',p'_i)$. При удалении пары подобных ребер (одно ребро $(u,p_i)$ из $G$, другое $(v',p'_i)$ из $G'$) $S$ не изменится. Если удалим все такие ребра, связывающие с соседями, то получим изолированные вершины $u,v'$, при том же $S$. Удалим эти вершины и удалим отображение $u\leftrightarrow v'$ из каждого элемента $S$. Мощность $S$ , может, и уменьшится, но все его элементы останутся изоморфизмами для $G_1,G'_1$.ЧТД. Я ответил на Ваш вопрос?

-- 14 июл 2011, 18:37 --

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

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

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

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

Ранее я уже ответил на это и подобные подозрения: post466454.html#p466454

Это не подозрение, и даже не критика -- это факт. В своём ответе Вы его обходите стороной.

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

[bin]

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

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

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

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

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

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

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

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

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

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

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

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

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

А ваш новый вариант легко опровергается контрпримером из 4 вершин.

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

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

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

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

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

[whitefox]

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

Мощность $S$ , может, и уменьшится, но все его элементы останутся изоморфизмами для $G_1,G'_1$

Кроме того в $S$ могут добавиться новые элементы, и хотя все они будут изоморфизмами для $G_1,G'_1$, но не изоморфизмами для $G_0,G'_0$.

[bin]

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

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

Мощность $S$ , может, и уменьшится, но все его элементы останутся изоморфизмами для $G_1,G'_1$

Кроме того в $S$ могут добавиться новые элементы, и хотя все они будут изоморфизмами для $G_1,G'_1$, но не изоморфизмами для $G_0,G'_0$.

Простите, не понял: как что-то может добавиться в $S$, если мы туда ничего не добавляем?? Про изменение $S$ я имею в виду возможность, что после удаления $u\leftrightarrow v'$ может из двух элементов получится один и тот же. Только и всего.

[whitefox]

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

Простите, не понял: как что-то может добавиться в $S$, если мы туда ничего не добавляем?? Про изменение $S$ я имею в виду возможность, что после удаления $u\leftrightarrow v'$ может из двух элементов получится один и тот же. Только и всего.

Ваш алгоритм ничего не знает о множестве $S_0$, а если бы знал, то просто выбрал бы произвольный элемент, и на этом закончил бы работу. Поэтому единственный законный способ построить множество $S_1$ -- это включить в него абсолютно все изоморфизмы графов $G_1,G'_1$, приписав к каждому пару $u\leftrightarrow v'$.

[bin]

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

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

Простите, не понял: как что-то может добавиться в $S$, если мы туда ничего не добавляем?? Про изменение $S$ я имею в виду возможность, что после удаления $u\leftrightarrow v'$ может из двух элементов получится один и тот же. Только и всего.

Ваш алгоритм ничего не знает о множестве $S_0$, а если бы знал, то просто выбрал бы произвольный элемент, и на этом закончил бы работу. Поэтому единственный законный способ построить множество $S_1$ -- это включить в него абсолютно все изоморфизмы графов $G_1,G'_1$, приписав к каждому пару $u\leftrightarrow v'$.

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

[whitefox]

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

Введем правило: вершина может войти в новое семейство (тогда у нее меняется номер)

Поясните, пожалуйста, в каких случаях вершина может войти в новое семейство? И какой номер у неё при этом меняется -- номер семейства?

[bin]

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

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

Введем правило: вершина может войти в новое семейство (тогда у нее меняется номер)

Поясните, пожалуйста, в каких случаях вершина может войти в новое семейство? И какой номер у неё при этом меняется -- номер семейства?

Да, меняется номер семейства (наверное, удачнее сказать метка семейства, чтобы не путать с номерами вершин). Если было какое-то семейство вершин, и на очередном шаге эти вершины стали неподобными, то семейство может быть разбито на два или несколько семейств подобных вершин, а обратное действие запрещено: если часть вершин из нескольких семейств стали подобными - их нельзя объединить в одно семейство. Например, пусть было семейство (1,2,3,4), а появились два семейства (1,2) и (3,4), то вершины 1,2 сохраняют свою метку семейства, а 3,4 получают новую уникальную метку нового семейства. А вот если были семейства (1,2) и (3,4), и все эти вершины стали подобными, то они все равно числятся неподобными, т.е. сохраняют присвоенные им ранее метки семейств. Те же действия и те же метки и для вершин второго графа.

[whitefox]

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

Например, пусть было семейство (1,2,3,4), а появились два семейства (1,2) и (3,4), то вершины 1,2 сохраняют свою метку семейства, а 3,4 получают новую уникальную метку нового семейства.

Почему так, а не наоборот -- (3,4) сохраняют метку, а (1,2) получают новую? Есть в этом какой-то смысл, или выбор совершено произволен?

-- 16 июл 2011, 20:35 --

Пусть $G$ цепь с вершинами 1, 2, 3, 4, 5.
А $G'$ цепь с вершинами 1', 2', 3', 4', 5'.
семейство 1: (1, 5); (1', 5')
семейство 2: (2, 4); (2', 4')
семейство 3: (3); (3').
На первом шаге установим соответствие 1-5'.
Получим семейства:
семейство 1: (5); (1')
семейство 2: (2); (4')
семейство 3: (3); (3')
семейство 4: (4); (2')
На втором шаге установим соответствие 2-4'.
Получим семейства:
семейство 1: (5); (1')
семейство 2:
семейство 3: (3); (3')
семейство 4: (4); (2')
Так должен работать Ваш алгоритм?

[ha]

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

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

[bin]

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

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

Например, пусть было семейство (1,2,3,4), а появились два семейства (1,2) и (3,4), то вершины 1,2 сохраняют свою метку семейства, а 3,4 получают новую уникальную метку нового семейства.

Почему так, а не наоборот -- (3,4) сохраняют метку, а (1,2) получают новую? Есть в этом какой-то смысл, или выбор совершено произволен?

Выбор произволен.

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

-- 16 июл 2011, 20:35 --

Пусть $G$ цепь с вершинами 1, 2, 3, 4, 5.
А $G'$ цепь с вершинами 1', 2', 3', 4', 5'.
семейство 1: (1, 5); (1', 5')
семейство 2: (2, 4); (2', 4')
семейство 3: (3); (3').
На первом шаге установим соответствие 1-5'.
Получим семейства:
семейство 1: (5); (1')
семейство 2: (2); (4')
семейство 3: (3); (3')
семейство 4: (4); (2')
На втором шаге установим соответствие 2-4'.
Получим семейства:
семейство 1: (5); (1')
семейство 2:
семейство 3: (3); (3')
семейство 4: (4); (2')
Так должен работать Ваш алгоритм?

Чисто оформительски я бы предложил 1-1', при желании мы потом можем сделать подстановку, которая сути не изменит:

$$ \left(\begin{array}{ccccc} 1' & 2' & 3' & 4' & 5'\\ 5' & 4' & 3' & 2' & 1'\end{array}\right),$$

но продолжаю в Ваших обозначениях, надеюсь ничего не напутал. Прежде всего на всякий случай напомню, что каждая вершина имеет две метки: очередь на удаление и номер семейства. Очередь на удаление не меняется: 1) 1-5'; 2) 2-4'; 3) 3-3'; 4) 4-2'; 5) 5-1' не реализуется, т.к. $n-1$ достигнуто. Итак, (шаги обозначаем звездочкой "*''):
семейство 1: (1,5), (1',5')
семейство 2: (2,4), (2',4')
семейство 3: (3), (3')
(См. рис.: О- очередь, С - семейство)
* Удаляем согласно очереди 1) 1-5' и получаем:
семейство 1: (5), (1')
семейство 2: (2), (4')
семейство 3: (3), (3')
семейство 4: (4), (2')
(Семейства 1,2 согласно правилу объединять запрещено.)
* Удаляем согласно очереди 2) 2-4' и получаем:
семейство 1: (5), (1')
семейство 3: (3), (3')
семейство 4: (4), (2')
(Семейства 1,3 согласно правилу объединять запрещено. При желании семейства можно перенумеровать, чтобы была сплошная нумерация, но для наглядности мы этого делать не будем.)
* Удаляем согласно очереди 3) 3-3' и получаем:
семейство 1: (5), (1')
семейство 4: (4), (2')
(Семейства 1,4 согласно правилу объединять запрещено.)
* Удаляем согласно очереди 4) 4-2' и получаем:
семейство 1: (5), (1')
* Стоп. Имеем изоморфизм:

$$ \left(\begin{array}{ccccc} 1 & 2 & 3 & 4 & 5\\ 5' & 4' & 3' & 2' & 1'\end{array}\right)$$

-- Вс июл 17, 2011 01:07:24 --

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

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

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

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

-- Вс июл 17, 2011 01:14:15 --

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