fixfix
2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 13, 14, 15, 16, 17, 18, 19 ... 26  След.
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение22.07.2011, 10:13 
Заблокирован


20/07/11

169
Вообще говоря, интересно проверить эффективность алгоритма (а заодно и его "правильность") на высокосимметричных молекулярных системах, например, с максимально возможной симметрией Ih: без труда можно построить такие системы, содержащие 1000-и атомов.

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


19/12/10
1546
2drozdov_mihail
В контексте проблемы изоморфизма вопрос эффективности ставится в следующей форме:
принадлежит эта задача классу $\textrm P$ или нет?

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

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


22/09/09

1907
whitefox в сообщении #470382 писал(а):
Для решения проблемы изоморфизма графов сам изоморфизм находить не обязательно.
Теоретически не обязательно, а практически желательно. Для проверки алгоритма, например. Если посмотреть аналогичные работы - почти во всех не останавливаются на вопросе "изоморфны ли графы?", но и пытаются найти какой-то изоморфизм.

Судя по отсутствию конретной критики, претензий к доказательствам предложенных двух алгоритмов поиска изоморфизма по списку псевдо-подобных вершин не осталось? Тогда стоит обсудить функцию Comp, которая заменяет оракула. В придачу к сказанному там добавлю:
1) Напомню следующий фрагмент из первой версии препринта:
Цитата:
Consider, what effect for solutions of system (1) may be caused by a change of one of absolute terms. Let the absolute term $B_{i}$ be increased by $\Delta B>0$. Then the process of solutions changing may be described by following model. Firstly, note that the sum of solutions increases by $\Delta B$, because of Property 2. Consider, how this increment is distributed. First of all, the increase of $B_{i}$ causes increase of $x_{i}$ by $\Delta x_{i}=\Delta B/(d_{i}+1)$. Further, $i$-adjacent vertex $k$ also increases its own weight by $\Delta x_{i}/(d_{k}+1)$. However, the first approximation of increment of $x_{k}$ is only part of the increment of $x_{i}$:$$ \Delta x_{k}=\frac{\Delta x_{i}}{d_{k}+1}=\frac{\Delta B}{(d_{i}+1)(d_{k}+1)}<\frac{\Delta B}{d_{i}+1}=\Delta x_{i}.$$ At the same time, increase of neighbors number, i.e. increase of $d_{i}$, causes decrease of the weight's increment of every of these neighbors. Also, every increase of weight of every $i$-adjacent vertex, causes additional increase of weight of vertex $i$, but this addition is smaller part $\Delta x_{k}/(d_{i}+1).$ Similar situation we observe for vertices that are more remote from $i$ vertex. For example, for $k$-adjacent vertex $p$ that is not $i$-adjacent vertex, the first approximation of increment of its weight is $\Delta x_{k}/(d_{p}+1).$ The vertex $p$ may be connected with a few $i$-adjacent vertices that vertices have equal weight $x_{k}$ (maximum allowed for $k$-adjacent vertex), but in this case the increment for vertex $p$ will be less than the increment for vertex $k:$ $$ \frac{d_{p}\Delta x_{k}}{d_{p}+1}<\Delta x_{k}.$$ From here we get the following property 4 of system (1).
Property 4. The increase of $B_{i}$ by $\Delta B$ increases every solution $x_{j}$ (where $j=1,{\ldots{}},n$) of system (1) by $\Delta x_{j}$, where $0<\Delta x_{j}<\Delta B.$

2) Arthur Rubin прислал мне следующее доказательство:
Цитата:
Clean description of property 4, with proof:
Property 4: If $B\ensuremath{\ge}0$ (coordinatewise),
(a): $x\ensuremath{\ge}0$ (coordinatewise)
(b): If, in addition, $B\ensuremath{\neq}0$, then $\Delta x>0$(coordinatewise)
(c): $\max (x)\ensuremath{\le}\max (B)$
(d): If, in addition, $B$ is not constant, than $\max (x) <\max (B)$
Proof: Let $M$ be the modified incidence matrix, so that equation (1) can be written as $x = Mx + b$. Clearly $M$ is substocastic (all entries are non-negative, and all row sums are less than 1), so that the normal power series expansion $\left(I-M\right)^{-1}=\sum_{n=0}^{\infty}M^{n}$ converges. In addition, as the graph is connected, for any two vertices, there is a path between them. Let $k$ be the maximum of those path lengths. Then $\sum_{n=0}^{k}M^{n}$ has all entries positive.

Proof of specific properties, noting that $\left(I-M\right)x=b$, so $x=\left(I-M\right)^{-1}b$. (a): $\left(I-M\right)^{-1}\geq0$ (coordinate-wise), by inspection (b): $\left(I-M\right)^{-1}=\sum_{n=0}^{\infty}M^{n}\geq\sum_{n=0}^{k}M^{n}$, so all components are greater than 0. (c) The increment from $B$ to the vector with all components $\max (B)$ satisfies the initial property of this Proposition, so (a) applies to that property. But, by Property 3, the the increment corresponding to the vector with all components $\max (B)$ is that same vector, so that (a) reads that $x \ensuremath{\le} $ the vector which is all $\max (\Delta B)$, component-wise. Hence $\max(x)\ensuremath{\le}\max(B)$. (d) Using property (b) for the increment, leads to $\max(x)<\max(B)$ if $B$ is not a constant vector. QED

This seems stronger than your existing Property 4.
An alternative formulation would be: $\min(B)\ensuremath{\le}\min(x)\ensuremath{\le}\max(x)\ensuremath{\le}\max(B)$, and if any inequality is proper, then all are.

3) Будем задавать начальный вес, равный единице, вершине, которую мы назовем вершиной-источником, а остальным вершиным графа зададим начальные веса, равные нулю. Решив СЛУ, мы увидим, что все вершины графа приобрели положительный вес, причем он убывает с изменением расстояния от вершины-источника. Если два соседа вершины-источника имеют одинаковые степени и одинаковый вес, они могут оказаться подобными, но если у них разный вес, то они точно не могут быть подобными. Функцию Comp мы можем использовать для поиска автоморфизма между указанной в ее параметрах парой вершин одного из графов. Будем искать тождественную подстановку 1-1,... Очевидно, что только пары подобных вершин дадут подходящие биграфы в функции Comp. И никакое несовпадающее решение не приведет к пустому множеству пересечений ребер подходящих биграфов. Т.к. Comp работает с отсортированными координатами векторов решений, то результат ее работы не зависит от нумерации вершин графа. Значит, Comp будет выдавать правильный список подобных вершин, когда на ее входе указаны две подобные вершины (для изоморфных графов).

-- Пт июл 22, 2011 19:05:04 --

drozdov_mihail в сообщении #470463 писал(а):
Вообще говоря, интересно проверить эффективность алгоритма (а заодно и его "правильность") на высокосимметричных молекулярных системах, например, с максимально возможной симметрией Ih: без труда можно построить такие системы, содержащие 1000-и атомов.
Как я уже разъяснял здесь ранее, данная работа имеет чисто теоретическую цель, и поэтому об эффективности речи не идет. Некоторые реализации предыдущих версий алгоритма работали очень медленно, поэтому там число вершин было ограничено 60 (иначе в случае обнаружения бага реализации искать его под отладчиком было бы нереально долго). Версия для практических задач компьютерной химии была опубликована в Известиях РАН (ссылка в препринте). Та версия показала высокую эффективность для молекул с числом атомов углерода до 100 (вполне достаточно для классической орг. химии, но не для химии ВМС). К доказательству той версии претензий нет, т.к. она формально реализует алгоритм с возвратом (наихудшего случая - экспоненты - при этом на практике не наблюдается :D ). Еще одна важная для химии особенность той версии - гетероатомы различаются.

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


19/12/10
1546
2bin
Некоторое время меня не будет.
Прошу не считать моё молчание за согласие.

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение25.07.2011, 11:34 


02/09/08
143
bin в сообщении #469326 писал(а):
ha в сообщении #469269 писал(а):
Ну и цитата с блога http://experimentalmath.info/
Уточните, пожалуйста, ссылку, на указанной странице я такой цитаты не нашел. Похоже, Вы указали индексную страницу сайта вместо того, чтобы указать конкретный блог на этом сайте.

Там блог один. Вот прямая ссылка - http://experimentalmath.info/blog/2011/ ... -of-doubt/.
Цитата:
-- Пн июл 18, 2011 14:57:17 --
Намедни Вы признали:
ha в сообщении #469026 писал(а):
Этот алгоритм вроде правильный. Теперь попробуйте его доказать.
Так что кое-какие результаты и с Вашей точки зрения я получил. Т.о. Вы не можете утверждать, что "реально у меня нет ничего и близко похожего". И мой метод постепенных исправлений по результатам обсуждений и переписки, как видим, работает, и работал бы еще лучше, если бы Вы меньше шумели не по делу, а больше бы говорили по делу :D

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

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

Цитата:
-- Пн июл 18, 2011 15:09:34 --

Гораздо большее смятение в ряды обывателей вносят теории и гипотезы из естественных наук. Это оборотная сторона научно-технического прогресса и с этим ничего не поделать, да и не нужно - обыватели жаждут такого смятения :-) Что касается GI, то подавляющее большинство обывателей ничего не знает об этой проблеме и наше обсуждение навряд ли читает.

Да, это проблема меньшего масштаба. Тем не менее людей интересующихся математикой достаточно много.

Цитата:
-- Пн июл 18, 2011 15:25:53 --
ha в сообщении #469269 писал(а):
Теория сложности вычислений - это часть математики. А задача изоморфизма графов ей принадлежит. Поэтому доказательства в ней должны следовать всем требованиям строгости устоявшимся в математике, а не программировании.
Теория сложности вычислений - это часть computer sci., как и программирование. Но речь была не про то, что "доказательства в ней должны следовать всем требованиям строгости устоявшимся в математике", а про то, что программирование наиболее явно свидетельствует о природной склонности людей, и даже лучших специалистов, делать везде, где только возможно, ошибки, и даже тривиальные. Это "зашито" в человеческой природе и с этим приходится считаться при решении сложных задач, и без толку взывать "не делайте ошибок" даже в лучшей бригаде программистов (куда нередко входят и чистые математики) - все равно сделают! Поэтому реалисты всегда планируют комплексы сложных мероприятий по устранению ошибок. А у Вас нереалистичный подход, применимый только для хорошо решающихся задач.

Это "зашито" в программировании. А в математике и в теории сложности вычислений в частности ситуация другая.

Цитата:
-- Пн июл 18, 2011 15:35:16 --
ha в сообщении #469269 писал(а):
вы просили показать существование чего-либо без ошибок, а теперь говорите, что не все книги по математике без ошибок.
Нет, я не просил, это Вы заявили "Я прочел множество книг по математики и в них почему-то не было тривиальных ошибок" (это прозвучало как "все книги"), а теперь согласились, что не все книги по математике без ошибок, поменяв таким образом квантор ;-)
[/quote]
Для меня это как "все книги" не звучит. Так что дело лишь в вашем неправильном понимании.

-- Пн июл 25, 2011 13:30:01 --

bin в сообщении #469338 писал(а):
ha в сообщении #469269 писал(а):
Клайн разве считает, что в математике нужны доказательства с тривиальными ошибками?
А я разве говорил, что в математике нужны доказательства с ошибками?

Да, вы утверждаете, что ваши доказательства имеют ценность не смотря на то, что они переполнены тривиальными ошибками.
Цитата:
Речь о самоизоляции математики, которую отметил Клайн. Эта самоизоляция проистекает в том числе и от патологического страха допустить ошибку, укоренившегося у большинства современных математиков. Перефразируя известную пословицу, можно сказать, что не ошибается только тот, кто не пытается решать труднорешаемые задачи. При решении трудных задач ошибки неизбежны, что, как отмечено выше, демонстрируется и всей практикой программирования.

А практика математики демонстрирует, что важна не трудность задачи, а трудность решения.

Цитата:
А значит, и надо подходить как в программировании: методом последовательного исправления версий. Что, кстати, математики и делают, посмотрите препринт http://arxiv.org/abs/0907.3965 - там уже 43 версии! Вот так и надо работать, а не стенать по поводу ошибок в промежуточных версиях.

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

Цитата:
ha в сообщении #469269 писал(а):
Все остальные, как показывает приведенная мною цитата, считают, то теория Лакатоса применима исключительно к 17-18 веку, а вы демонстрируете не знание базовых основ модельного подхода, считая, что если она работает 2 века, то работает везде.
Я уже спрашивал, откуда та цитата? Вы не ответили. Но если бы все так считали, как Вы, то эта книга никогда бы не стала такой известной. Кому сейчас нужна модель для 18 века, кроме узкого круга историков?

Во-первых, это очень интересный этап развития математики. В этих веках практический подход преобладал над теоретическим. Во-вторых, эта теория является часть более общей теории Лакатоса, которая относится к остальным естественным наукам и в этом случае она сохраняет популярность до сих пор.

Цитата:
ha в сообщении #469269 писал(а):
Хороший математик давно бы закрыл тему, поняв после первой ошибки, что у него нет доказательства.
Хорший математик никогда бы не взялся за решение такой задачи (на это и сетует Клайн), я же себя позиционирую не как математик, а как computer scientist :D Никто, кроме Вас, эту тему закрыть не предлагал (можете видеть, что пустые темы администрация этого сайта закрывает очень быстро, никого не спрашивая, а моя тема давно и в топе по количеству просмотров),

Кому-то надо быть первым. Практически никто кроме меня не читал вашу статью. Из тех кто читал, положительных отзывов нет. Это единственное, что имеет значение.
Цитата:
а значит, моя постановка вопроса и моя методология, а не Ваша, находит поддержку, в частности, и здесь.

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

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

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

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение25.07.2011, 12:43 


02/09/08
143
bin в сообщении #470617 писал(а):

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

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

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


22/09/09

1907
ha

(Оффтоп)



ha в сообщении #471039 писал(а):
Не говоря уж о том, что результат в виду простоты формулировки и не сложности доказательства должен быть давно известен специалистам. Если вы у них спросите доказательство и скопируйте его (или ссылку на статью, где он упоминается) сюда, то к вам не будет никаких претензий. Почему вы пытаетесь доказать его самостоятельно, демонстрируя уйму тривиальных ошибок (поиск в ширину? ну соедините первую вершину со всеми остальными и он вам ничего не даст) мне не понятно.
Вы специалист? Вам известно доказательство? Дайте, пожалуйста, ссылку. Ваш контрпример относится к алгоритму 2 (я подумаю над улучшением). Ошибок в алгоритме 1 и его доказательстве Вы, похоже, не нашли.
ha в сообщении #471052 писал(а):
Судя по отсутствию окончательной версии доказательства, претензий к отсутствию решения задачи поиска изоморфизма по списку подобных (какие еще псевдо?) вершин у вас не осталось.
Про (псевдо)-подобные и про два доказательства двух различных решений читайте внимательнее предыдущие сообщения.

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение25.07.2011, 13:31 


02/09/08
143
bin в сообщении #470617 писал(а):
3) Будем задавать начальный вес, равный единице, вершине, которую мы назовем вершиной-источником, а остальным вершиным графа зададим начальные веса, равные нулю.

Где будем?
Цитата:
Решив СЛУ, мы увидим, что все вершины графа приобрели положительный вес, причем он убывает с изменением расстояния от вершины-источника.

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

Никак не используется в дальнейшем. Зачем тогда писать?
Цитата:
Функцию Comp мы можем использовать для поиска автоморфизма между указанной в ее параметрах парой вершин одного из графов.

Если можем, то задача решена, больше писать ничего не нужно. Или дальнейшее это типа "доказательство"?
Цитата:
Будем искать тождественную подстановку 1-1,... Очевидно, что только пары подобных вершин дадут подходящие биграфы в функции Comp. И никакое несовпадающее решение не приведет к пустому множеству пересечений ребер подходящих биграфов.

Не запутались в отрицаниях? Пустое множество пересечений на совпадающих решениях звучит как опечатка, что бы эти пересечения и решения не значили. Что означают "подходящие биграфы"?
Цитата:
Т.к. Comp работает с отсортированными координатами векторов решений, то результат ее работы не зависит от нумерации вершин графа. Значит, Comp будет выдавать правильный список подобных вершин, когда на ее входе указаны две подобные вершины (для изоморфных графов).

В итоге получаем, что если Comp выдает для равных графов на одинаковых вершинах список подобных, то она выдает для изоморфных графов на подобных вершинах список подобных. К чему тут свойство 4 и как поможет автору подобное условное утверждение остается загадкой.

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


22/09/09

1907
ha в сообщении #471064 писал(а):
Где будем?
В доказательстве.

-- Пн июл 25, 2011 13:44:55 --

ha в сообщении #471064 писал(а):
Вчитываемся в свойство 4 - никаких расстояний там нет. Опять тривиальная ошибка.
Это опечатка. См. фрагмент перед свойством 4:
bin в сообщении #470617 писал(а):
Напомню следующий фрагмент из первой версии препринта

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение25.07.2011, 13:49 


02/09/08
143
Цитата:
Ошибок в алгоритме 1 и его доказательстве Вы, похоже, не нашли.

Если вы имеете в виду Comp - то я его подробно не читал. Сразу видно, что оно справедливо для любой $f(G)$, а значит можно его существенно упростить за счет подстановки $f(G)=M$. После чего будет либо найдено решение изоморфизма графов в десять строчек (а значит оно давным давно было бы найдено), либо найдется множество тривиальных ошибок.

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


22/09/09

1907
ha в сообщении #471064 писал(а):
Что означают "подходящие биграфы"?
Те которые не содержат неподходящее множество ребер:
bin в сообщении #464329 писал(а):
Если найдется вершина $k$, не имеющая ребер в множестве $E$, то будем называть такое множество неподходящим. Очевидно, что для неподходящего множества невозможно найти решений, удовлетворяющих Утверждению 3. Поэтому если множество ребер биграфа $H_{ij}$ образует при пересечении с множеством ребер биграфа $H_{0}$ неподходящее множество, то будем удалять биграф $H_{ij}$ из дальнейшего рассмотрения и ребро $(i,j)$ из $H_{0}$.


-- Пн июл 25, 2011 13:53:58 --

ha в сообщении #471071 писал(а):
Сразу видно, что оно справедливо для любой
Мне не видно :-) Тут два момента: 1) сведение GI к системе общих представителей (СОП), 2) конкретный алгоритм поиска СОП. Если в (2) ошибка, это не значит, что (1) неверно. BTW алгоритма (2) поиска СОП я в литературе пока не нашел.

-- Пн июл 25, 2011 13:58:24 --

ha в сообщении #471064 писал(а):
Если можем, то задача решена, больше писать ничего не нужно. Или дальнейшее это типа "доказательство"?
Да, набросок доказательства.

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение25.07.2011, 14:05 


02/09/08
143
bin в сообщении #471061 писал(а):
ha
Про (псевдо)-подобные и про два доказательства двух различных решений читайте внимательнее предыдущие сообщения.

Я их внимательно читаю. Но никаких окончательных версий не вижу.

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


22/09/09

1907
ha в сообщении #471071 писал(а):
Сразу видно, что оно справедливо для любой $f(G)$, а значит можно его существенно упростить за счет подстановки $f(G)=M$.

И какие будут отсортированные координаты при такой замене? Для регулярных графов все векторы одинаковы? При чем тут Утверждение 3? $f(G)=M$ - вырожденный случай! Какие биграфы мы получим? Полные?
bin в сообщении #470617 писал(а):
Т.к. Comp работает с отсортированными координатами векторов решений, то результат ее работы не зависит от нумерации вершин графа.


-- Пн июл 25, 2011 14:18:24 --
ha

(Оффтоп)



-- Пн июл 25, 2011 14:34:56 --

ha в сообщении #471071 писал(а):
Цитата:
Ошибок в алгоритме 1 и его доказательстве Вы, похоже, не нашли.

Если вы имеете в виду Comp - то я его подробно не читал.
Нет. Речь про
whitefox в сообщении #469517 писал(а):
Тогда Ваш алгоритм можно представить так
и далее.

-- Пн июл 25, 2011 15:07:56 --

ha в сообщении #471064 писал(а):
Цитата:
Если два соседа вершины-источника имеют одинаковые степени и одинаковый вес, они могут оказаться подобными, но если у них разный вес, то они точно не могут быть подобными.

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

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


22/09/09

1907
ha

(Оффтоп)



-- Пн июл 25, 2011 15:38:58 --

ha

(Оффтоп)


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


22/09/09

1907
ha

(Оффтоп)



-- Пн июл 25, 2011 17:27:11 --

(Оффтоп)



-- Пн июл 25, 2011 17:32:57 --

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

(Оффтоп)


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

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



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

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


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

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