2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 11, 12, 13, 14, 15, 16, 17 ... 26  След.
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение14.07.2011, 17:07 
Аватара пользователя


22/09/09

1907
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 писал(а):
А у вас есть примеры обратного? Ученые которые не разбирались в проблеме, совершали тривиальные ошибки одну за другой и при этом решили сложную математическую проблему, которую никто до этого не мог решить?
Вы знаете хоть одного программиста у которого транслятор не находил бы тривиальных ошибок. И хоть одну бета версию нетривиальной программы, где бы ни нашлось менее тривиальных ошибок? :D

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение14.07.2011, 18:14 
Аватара пользователя


22/09/09

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

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение14.07.2011, 18:15 
Заслуженный участник
Аватара пользователя


19/12/10
1546
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
Это не подозрение, и даже не критика -- это факт. В своём ответе Вы его обходите стороной.

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение14.07.2011, 21:38 


02/09/08
143
Цитата:
И где у меня "пофигизм"?

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

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

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

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

Цитата:
ha в сообщении #468204 писал(а):
А у вас есть примеры обратного? Ученые которые не разбирались в проблеме, совершали тривиальные ошибки одну за другой и при этом решили сложную математическую проблему, которую никто до этого не мог решить?
Вы знаете хоть одного программиста у которого транслятор не находил бы тривиальных ошибок. И хоть одну бета версию нетривиальной программы, где бы ни нашлось менее тривиальных ошибок? :D

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

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

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

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение14.07.2011, 22:05 
Аватара пользователя


22/09/09

1907
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
Это не подозрение, и даже не критика -- это факт. В своём ответе Вы его обходите стороной.
Я еще подумаю над этим вопросом и, может, попрошу уточнить. Однако мой ответ на этот вопрос никак не связан с вышеприведенным доказательством, поэтому обсуждения могут идти независимо.

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение14.07.2011, 23:05 
Аватара пользователя


22/09/09

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

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

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

ha в сообщении #468465 писал(а):
А ваш новый вариант легко опровергается контрпримером из 4 вершин.
Жду контрпримера. А также напомню, что Вы утверждали, что решение этой задачи не составит для Вас труда. Только вот решения не видно. whitefox честно сказал, что не знает решения, а Вы делаете вид, что знаете.

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

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

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение14.07.2011, 23:48 
Заслуженный участник
Аватара пользователя


19/12/10
1546
bin в сообщении #468481 писал(а):
Мощность $S$ , может, и уменьшится, но все его элементы останутся изоморфизмами для $G_1,G'_1$
Кроме того в $S$ могут добавиться новые элементы, и хотя все они будут изоморфизмами для $G_1,G'_1$, но не изоморфизмами для $G_0,G'_0$.

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение15.07.2011, 00:33 
Аватара пользователя


22/09/09

1907
whitefox в сообщении #468508 писал(а):
bin в сообщении #468481 писал(а):
Мощность $S$ , может, и уменьшится, но все его элементы останутся изоморфизмами для $G_1,G'_1$
Кроме того в $S$ могут добавиться новые элементы, и хотя все они будут изоморфизмами для $G_1,G'_1$, но не изоморфизмами для $G_0,G'_0$.
Простите, не понял: как что-то может добавиться в $S$, если мы туда ничего не добавляем?? Про изменение $S$ я имею в виду возможность, что после удаления $u\leftrightarrow v'$ может из двух элементов получится один и тот же. Только и всего.

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение15.07.2011, 07:20 
Заслуженный участник
Аватара пользователя


19/12/10
1546
bin в сообщении #468513 писал(а):
Простите, не понял: как что-то может добавиться в $S$, если мы туда ничего не добавляем?? Про изменение $S$ я имею в виду возможность, что после удаления $u\leftrightarrow v'$ может из двух элементов получится один и тот же. Только и всего.
Ваш алгоритм ничего не знает о множестве $S_0$, а если бы знал, то просто выбрал бы произвольный элемент, и на этом закончил бы работу. Поэтому единственный законный способ построить множество $S_1$ -- это включить в него абсолютно все изоморфизмы графов $G_1,G'_1$, приписав к каждому пару $u\leftrightarrow v'$.

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение15.07.2011, 14:31 
Аватара пользователя


22/09/09

1907
whitefox в сообщении #468537 писал(а):
bin в сообщении #468513 писал(а):
Простите, не понял: как что-то может добавиться в $S$, если мы туда ничего не добавляем?? Про изменение $S$ я имею в виду возможность, что после удаления $u\leftrightarrow v'$ может из двух элементов получится один и тот же. Только и всего.
Ваш алгоритм ничего не знает о множестве $S_0$, а если бы знал, то просто выбрал бы произвольный элемент, и на этом закончил бы работу. Поэтому единственный законный способ построить множество $S_1$ -- это включить в него абсолютно все изоморфизмы графов $G_1,G'_1$, приписав к каждому пару $u\leftrightarrow v'$.
Можно сделать еще одно улучшение. Пронумеруем семейства подобных вершин и каждую вершину будем метить еще одной меткой - номером семейства. Введем правило: вершина может войти в новое семейство (тогда у нее меняется номер), но вершины разных семейств не могут объединиться в одно семейство (т.е. если после удаления какой-то вершины две вершины, принадлежавшие до удаления разным семействам, оказались подобными, они продолжают числиться как неподобные). Удалять можно вершины, у которых метки семейств совпадают. Так как исходные графы изоморфны, то такие удаления будут всегда возможны. Перенумерация семейств - дело техники (достаточно тривиальна).

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение16.07.2011, 08:48 
Заслуженный участник
Аватара пользователя


19/12/10
1546
bin в сообщении #468670 писал(а):
Введем правило: вершина может войти в новое семейство (тогда у нее меняется номер)
Поясните, пожалуйста, в каких случаях вершина может войти в новое семейство? И какой номер у неё при этом меняется -- номер семейства?

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение16.07.2011, 13:56 
Аватара пользователя


22/09/09

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

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение16.07.2011, 20:04 
Заслуженный участник
Аватара пользователя


19/12/10
1546
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')
Так должен работать Ваш алгоритм?

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение16.07.2011, 23:18 


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

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

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение17.07.2011, 01:02 
Аватара пользователя


22/09/09

1907
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 Сейчас также думаю и над другим вариантом: остовное дерево, где просмотр в ширину дополнительно регулируется номером семейства. Два дерева от двух графов при наложении дадут изоморфизм...

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 380 ]  На страницу Пред.  1 ... 11, 12, 13, 14, 15, 16, 17 ... 26  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group