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

[bin]

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

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

Возьмем книгу Зыкова, Теория графов, М: Вузовская книга, 2004 и раскроем на параграфе 1.3 Инварианты (С.27):

Цитата:

Пусть $f:G\rightarrow H$ - функция, относящая каждому графу некоторый элемент $f(G)$ из множества $H$ произвольной природы [...]. Эту функцию будем называть инвариантом, если на изоморфных графах ее значения совпадают:

$$ \forall G,G':\: G\cong G'\Rightarrow f(G)=f(G')$$

Далее на С.32:

Цитата:

Матрица смежностей - не инвариант графа: при перенумеровании вершин она претерпевает перестановку [...], состоящую из перестановки строк и точно такой же перестановки столбцов.

И далее С.33-35:

Цитата:

Двоичные коды матриц смежностей одного и того же графа, отвечающих разным нумерациям его вершин, конечно, не обязаны совпадать; наименьший из этих кодов (при всевозможных $n!$ нумерациях вершин) будем называть мини-кодом [...], а наибольший - макси-кодом [...] графа $G$. Оба эти кода, очевидно, - инварианты, и, более того, по любому из них и количеству вершин легко восстанавливается одна из матриц смежностей графа, а значит, и сам граф (с точностью до изоморфизма). [...] Количество вершин можно не сообщать, если заранее известно, что у графа нет изолированных вершин.

Что же предлагает ha в качестве опровержения? - Заменить отсортированный по координатам вектор решений СЛУ матрицей смежностей. Если так, то он делает грубейшую тривиальную ошибку, предлагая явно неэквивалентную замену: отсортированный вектор решений - инвариант, а матрица смежностей - не инвариант! Или же он предлагает взять мини-код/макси-код? В таком случае Comp, в существующем на данный момент виде, станет просто ненужной: миникод - полный инвариант графа и равенство миникодов двух связных графов является необходимым и достаточным условием их изоморфизма. Опять тривиальная ошибка ha: сведение задачи к вырожденному случаю. Кроме того, общеизвестно, что в настоящее время в многочисленных приложениях теории графов используются тысячи различных инвариантов. Явной зависимости одного инварианта от другого установить не удается, более того, исследования на тестовых выборках различных графов показывают, что разные инварианты по-разному чувствуют различные особенности графов, в частности, вырождаются на разных парах графов. Поэтому о равноценной эквивалентной замене одного инварианта на другой обычно говорить не приходится. Т.о. критика ha сама не выдерживает никакой критики и построена по пословице: видя соринку в чужом доказательстве (и каждый раз неистовствуя на тему чужих ''тривиальных'' ошибок), ha в своих опровержениях не столь требователен к себе, как к другим, и у себя нередко не замечает и бревна

[ha]

Что же мы видим? Автор придумывает за меня аргументы, которых я никогда не говорил.

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

Среди этих свойств нет свойства, что $f(G)$ является инвариантом графа (см. последний пост на странице 9). В вашем доказательстве используется $f(G)=A^{-1}$, что инвариантом естественно не является. Поэтому вы сортируете каждую строку $f(G)$ и получаете уже другую матрицу. По ней вы строите ваши двудольные графы и.т.д.

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

[bin]

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

Что же мы видим? Автор придумывает за меня аргументы, которых я никогда не говорил.

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

Среди этих свойств нет свойства, что $f(G)$ является инвариантом графа (см. последний пост на странице 9). В вашем доказательстве используется $f(G)=A^{-1}$, что инвариантом естественно не является. Поэтому вы сортируете каждую строку $f(G)$ и получаете уже другую матрицу. По ней вы строите ваши двудольные графы и.т.д.

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

"пишите, что вам не понятно" - не понятно:
1) Какие аргументы я придумал, которые Вы не говорили?
2) Смотрим первое же Ваше "свойство":

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

1. Для разных графов $G$ и $G'$ значения функции различны: $f(G)\neq f(G')$.

Нужно понимать, что "разных" это неравных? Тогда это местами ложно. А если "разных" это неизоморфных, а для изоморфных значения функции равны - вот здесь и появляется инвариант. Т.о. первое же Ваше свойство не соответствует моему доказательству. Неучтенное Вами свойство: мой отсортированный вектор - инвариант, Ваша подмена матрицей смежности - подмена инварианта на неинвариант. По построению очевидно, что Comp имеет смысл только для инварианта (и то далеко не всякого) - приведите построение Comp для матриц смежности и покажите, что это будет работать так же. Как вообще будет формулироваться Утверждение 3 для матрицы смежности и как для нее строить биграфы в рамках предложенной функции? - Вы на эти вопросы так и не ответили!
О каких совпадениях решений можно говорить для неинварианта? Только о случайных.
3) Почему мы должны учитывать Ваши свойства для моего доказательства, а не мои?
4) В моем доказательстве сейчас нет упоминания об обратной матрице. Может, Вам вспомнились W-матрицы? Так они пока сняты с обсуждения и остались в предыдущей версии препринта.

-- Ср июл 27, 2011 03:40:48 --

PS Еще раз повторю:

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

Т.к. Comp работает с отсортированными координатами векторов решений, то результат ее работы не зависит от нумерации вершин графа.

Вот Вам и инвариант.

[ha]

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

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

Что же мы видим? Автор придумывает за меня аргументы, которых я никогда не говорил.

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

Среди этих свойств нет свойства, что $f(G)$ является инвариантом графа (см. последний пост на странице 9). В вашем доказательстве используется $f(G)=A^{-1}$, что инвариантом естественно не является. Поэтому вы сортируете каждую строку $f(G)$ и получаете уже другую матрицу. По ней вы строите ваши двудольные графы и.т.д.

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

"пишите, что вам не понятно" - не понятно:
1) Какие аргументы я придумал, которые Вы не говорили?

Эти:

Цитата:

Что же предлагает ha в качестве опровержения? - Заменить отсортированный по координатам вектор решений СЛУ матрицей смежностей.

Цитата:

2) Смотрим первое же Ваше "свойство":

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

1. Для разных графов $G$ и $G'$ значения функции различны: $f(G)\neq f(G')$.

Нужно понимать, что "разных" это неравных?

Да.

Цитата:

Тогда это местами ложно.

Какими еще местами?

Цитата:

А если "разных" это неизоморфных, а для изоморфных значения функции равны - вот здесь и появляется инвариант.

Обозначим условие различности графов как $A$, а условие различности значений функций $B$. Свойство утверждает $A\Rightarrow B$. Автор же из этого делает вывод "что для изоморфных значения функций равны", т.е. $\bar{A}\Rightarrow\bar{B}$. Т.е. совершает тривиальную ошибку в булевой логике. В данном случае это не имеет значения, поскольку слово "разных" не означает неизоморфных, но хорошо показывает не знание автором базовых законов булевой логики.

Цитата:

Неучтенное Вами свойство: мой отсортированный вектор - инвариант, Ваша подмена матрицей смежности - подмена инварианта на неинвариант.

Я не подменяю инвариант матрицей смежности.

Цитата:

По построению очевидно, что Comp имеет смысл только для инварианта (и то далеко не всякого) - приведите построение Comp для матриц смежности и покажите, что это будет работать так же.

Оно и не будет, а поскольку доказательство Comp работает для всех $f(G)$ удовлетворяющих условиям, то это доказательство не верно.

Цитата:

Как вообще будет формулироваться Утверждение 3 для матрицы смежности

Assertion 3. For any two graphs $G$ and $G'$, which graphs have $n$ vertices, and for any permutation $P\in S_n$, if for $n$ linear independent vectors $b$ and for $n$ vectors $b'=P^{-1}\cdot b$, and $X=f(G)b$, $X'=f(G')b'$ we have $X'=P^{-1}\cdot X$, then $P$ is the graphs isomorphism.

Цитата:

и как для нее строить биграфы в рамках предложенной функции? - Вы на эти вопросы так и не ответили!

Точно также. Первая фраза изменяется на "Выберем в качестве X[1], ..., X[n] столбцы матрицы $f(G)$, а в качестве X'[1], ..., X'[n] столбцы матрицы $f(G')$". Можете работать и со строчками, если они вам больше нравятся. Все указанные мною свойства $f(G)$ по отдельности сохраняются при транспонировании.

Цитата:

3) Почему мы должны учитывать Ваши свойства для моего доказательства, а не мои?

Потому что ваши совпадают с моими.

Цитата:

4) В моем доказательстве сейчас нет упоминания об обратной матрице.

Вы выбираете в качестве X[1],...,X[n] решения системы линейных уравнений с матрицей $A$ на произвольных линейно независимых векторах. В частности можно взять последовательные единичные вектора. В таком случае X[1],...,X[n] будут столбцами матрицы $f(G)=A^{-1}$.

Цитата:

Может, Вам вспомнились W-матрицы? Так они пока сняты с обсуждения и остались в предыдущей версии препринта.

Нет, они мне не вспомнились.

[bin]

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

Цитата:

А если "разных" это неизоморфных, а для изоморфных значения функции равны - вот здесь и появляется инвариант.

Обозначим условие различности графов как $A$, а условие различности значений функций $B$. Свойство утверждает $A\Rightarrow B$. Автор же из этого делает вывод "что для изоморфных значения функций равны", т.е. $\bar{A}\Rightarrow\bar{B}$. Т.е. совершает тривиальную ошибку в булевой логике. В данном случае это не имеет значения, поскольку слово "разных" не означает неизоморфных, но хорошо показывает не знание автором базовых законов булевой логики.

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

(Оффтоп)

То, что вместо слово "неравные" Вы использовали слово "разные", выглядит не случайным. В математике принято использовать точно определенные термины. Разве Вы это не знаете? Почему же Вы используете слово, смысл которого в данном контексте не однозначен? Чтобы спровоцировать недоуменные вопросы и очередной раз, поступить по пословице, переложить (в переносном смысле) "с больной головы на здоровую"?

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

Оно и не будет, а поскольку доказательство Comp работает для всех $f(G)$ удовлетворяющих условиям, то это доказательство не верно.

А разве я где-то утверждал, что функция, которую я использую, единственная? Нет. И я вполне допускаю, что можно подобрать другие, подходящие для Comp, функции. Но если такое предположение и верно, то отсюда вовсе не следует, что Comp работает неверно или что доказательство неверно. Если Вы хотите всерьез использовать другую функцию - Вам следует доказать Утверждения 1,2,3 для нее. И не надо забывать, что речь идет о функции вида $f(G,b)$ , т.е. у нее 2 аргумента, а не один как Вы написали. Именно для такой функции и сформулированы Утверждения 1,2,3. При этом, для Comp играет решающее значение, чтобы изменение начального веса одной из вершин вызывало изменение весов всех других вершин того же графа, иначе перебор пересечений множеств ребер биграфов теряет смысл. Выше я уже сказал:

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

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

Что по-Вашему неверно (1) или (2) Вы так и не ответили.

[ha]

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

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

Цитата:

А если "разных" это неизоморфных, а для изоморфных значения функции равны - вот здесь и появляется инвариант.

Обозначим условие различности графов как $A$, а условие различности значений функций $B$. Свойство утверждает $A\Rightarrow B$. Автор же из этого делает вывод "что для изоморфных значения функций равны", т.е. $\bar{A}\Rightarrow\bar{B}$. Т.е. совершает тривиальную ошибку в булевой логике. В данном случае это не имеет значения, поскольку слово "разных" не означает неизоморфных, но хорошо показывает не знание автором базовых законов булевой логики.

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

Делаете - вы пытаетесь меня убедить, что из свойства 1 следует, что $f(G)$ - инвариант. А это - простейшая логическая ошибка связанная с незнанием булевой логики. Ни из какого понимания свойства 1 не следует, что $f(G)$ - инвариант.

Я формализую фразы в точности в том смысле, в котором они написаны. А если вы подразумеваете не то, что пишите - то вам нужно научится ясно излагать свои мысли.

И формализуете фразы вопреки смыслу именно вы. Не смотря на совершенно четко сформулированные свойства и определение $f(G)$ вы постоянно вкладываете в них не правильный смысл. То вы добавляете к ним, что $f(G)$ - инвариант, то второй аргумент. После чего начинайте вопить о том, что я предлагаю странные вещи. Типичный софистический прием, применение которого говорит не в пользу Вашей логики.

Цитата:

То, что вместо слово "неравные" Вы использовали слово "разные", выглядит не случайным. В математике принято использовать точно определенные термины. Разве Вы это не знаете? Почему же Вы используете слово, смысл которого в данном контексте не однозначен? Чтобы спровоцировать недоуменные вопросы и очередной раз, поступить по пословице, переложить (в переносном смысле) "с больной головы на здоровую"?

Потому что при этом меньше отрицаний и мне кажется очевидным равенство "разные=неравные" в контексте этой задачи. Это вроде не первое мое использование этого слова в этом смысле. Ну а последний аргумент - умный человек естественно выведет свойства 1 и 2 попытавшись доказать Утверждения 1, 2 и 3 для $f(G)$, что является тривиальной задачей.

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

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

Оно и не будет, а поскольку доказательство Comp работает для всех $f(G)$ удовлетворяющих условиям, то это доказательство не верно.

А разве я где-то утверждал, что функция, которую я использую, единственная? Нет. И я вполне допускаю, что можно подобрать другие, подходящие для Comp, функции. Но если такое предположение и верно, то отсюда вовсе не следует, что Comp работает неверно или что доказательство неверно. Если Вы хотите всерьез использовать другую функцию - Вам следует доказать Утверждения 1,2,3 для нее. [/quote]
Утверждения 1, 2, 3 тривиально следуют из свойств 1 и 2 функции $f(G)$. Достаточно заменить в их доказательствах $A^{-1}$ на $f(G)$.

Цитата:

И не надо забывать, что речь идет о функции вида $f(G,b)$ , т.е. у нее 2 аргумента, а не один как Вы написали.

Не надо забывать, что у нее один аргумент, а не два, как вы написали.

Цитата:

Именно для такой функции и сформулированы Утверждения 1,2,3.

Утверждение 3 сформулировано мною для функции $f(G)$ от одной переменной. В утверждениях 1 и 2 все аналогично. Матрица $A^{-1}$ заменяется на $f(G)$.

Цитата:

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

Поэтому-то ее доказательство и не верно. Никакой ссылки на это свойство (или какие-либо другие свойства) в доказательстве нет. Значит
1) вы доказываете (после указанной мною замены первой строчки доказательства) правильность работы Comp для всех функций $f(G)$, удовлетворяющих перечисленным мною свойствам.
2) А раз Comp хотя бы для одной функции $f(G)$ (в частности $f(G)=M$) работает не верно, то
3) отсюда (из пунктов 1 и 2) следует, что доказательство не верно.
С какими из этих пунктов вы не согласны?

Цитата:

Выше я уже сказал:

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

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

Что по-Вашему неверно (1) или (2) Вы так и не ответили.

Доказательства по первому пункту вы не предоставили, опровергать нечего. $f(G)$ опровергает второй пункт. Так что ваши продвижения равны в точности нулю.

[bin]

ha

(Оффтоп)

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

Делаете - вы пытаетесь меня убедить, что из свойства 1 следует, что $f(G)$ - инвариант. А это - простейшая логическая ошибка связанная с незнанием булевой логики. Ни из какого понимания свойства 1 не следует, что $f(G)$ - инвариант.

Нет. Не пытаюсь я Вас тут не в чем убеждать, а пытаюсь понять, что Вы хотели сказать. Факт, что я не говорил, что из Вашего свойства следует, а факт в том, что Ваша формулировка не достаточно понятна. Кто угодно может применить слово "разный" к неизоморфным графам, подразумевая, что "разный" означает "неизоморфный". Это Ваша ошибка, что Вы увидели слово "следует" во фразе, где этого слова не было. При этом меня искренне умиляет упорство, с которым Вы пытаетесь доказать, что я абсолютно ничего не знаю, Вам даже отсутствующие слова начинают мерещиться. Специально, чтобы успокоить Вас напишу, что я не знаю даже таблицы умножения и утверждаю, что дважды два будет пять. Удоволетворены, наконец? Я уже на все согласен, чтобы положить конец флуду о моих личных качествах. Ну хотите, я еще заявлю, что число $\pi$ равно 4?

И снова Вы попугайничаете, сравним:

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

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

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

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

Своих слов у Вас уже не осталось, так что мои за свои повторяете? Это широко известный метод детсадовской риторики говорить оппоненту "сам такой". Вот каков Ваш уровень ведения дискуссии.

При этом Вы уже не первый раз нарушаете правила форума: "Развитие оффтопика в теме нарушает правила форума".

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

Ну а последний аргумент - умный человек естественно выведет свойства 1 и 2 попытавшись доказать Утверждения 1, 2 и 3 для $f(G)$, что является тривиальной задачей.

Еще один демагогический прием: если человек умный, то сам выведет (подразумевается, что если не выведет, значит, дурак). И не повторяйте тут опять $\bar{A}\Rightarrow\bar{B}$. Ваша идея предложить другую функцию - вот и доказывайте ее, а не увиливайте с помощью дешовых приемов "если человек умный, то сам выведет".

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

Я всегда готов предоставить более точные определения и формулировки по вашему запросу

Предоставляйте.

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

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

Оно и не будет, а поскольку доказательство Comp работает для всех $f(G)$ удовлетворяющих условиям, то это доказательство не верно.

Цитата:

А разве я где-то утверждал, что функция, которую я использую, единственная? Нет. И я вполне допускаю, что можно подобрать другие, подходящие для Comp, функции. Но если такое предположение и верно, то отсюда вовсе не следует, что Comp работает неверно или что доказательство неверно. Если Вы хотите всерьез использовать другую функцию - Вам следует доказать Утверждения 1,2,3 для нее.

Утверждения 1, 2, 3 тривиально следуют из свойств 1 и 2 функции $f(G)$. Достаточно заменить в их доказательствах $A^{-1}$ на $f(G)$.

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

(Оффтоп)

Посмотрите на свою ошибку в оформлении моей цитаты в Вашем сообщении.

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

Цитата:

И не надо забывать, что речь идет о функции вида $f(G,b)$ , т.е. у нее 2 аргумента, а не один как Вы написали.

Не надо забывать, что у нее один аргумент, а не два, как вы написали.

У меня два.

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

Цитата:

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

Поэтому-то ее доказательство и не верно. Никакой ссылки на это свойство (или какие-либо другие свойства) в доказательстве нет.

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

[ha]

(Оффтоп)

Цитата:

Это Ваша ошибка, что Вы увидели слово "следует" во фразе, где этого слова не было.

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

Цитата:

При этом меня искренне умиляет упорство, с которым Вы пытаетесь доказать, что я абсолютно ничего не знаю, Вам даже отсутствующие слова начинают мерещиться. Специально, чтобы успокоить Вас напишу, что я не знаю даже таблицы умножения и утверждаю, что дважды два будет пять. Удоволетворены, наконец? Я уже на все согласен, чтобы положить конец флуду о моих личных качествах. Ну хотите, я еще заявлю, что число $\pi$ равно 4?

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

Цитата:

Своих слов у Вас уже не осталось, так что мои за свои повторяете? Это широко известный метод детсадовской риторики говорить оппоненту "сам такой". Вот каков Ваш уровень ведения дискуссии.

Не можете ответить на свои слова? Не нравится собственный уровень ведения дискуссии? Так может вам начать с себя?

Цитата:

При этом Вы уже не первый раз нарушаете правила форума: "Развитие оффтопика в теме нарушает правила форума".

Если я повторяя ваши слова нарушаю правила форума, значит вы тоже их нарушаете.

Цитата:

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

Я всегда готов предоставить более точные определения и формулировки по вашему запросу

Предоставляйте.

Так уже предоставил. Что-то еще не понятно в свойствах 1 и 2?

Цитата:

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

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

Оно и не будет, а поскольку доказательство Comp работает для всех $f(G)$ удовлетворяющих условиям, то это доказательство не верно.

Цитата:

А разве я где-то утверждал, что функция, которую я использую, единственная? Нет. И я вполне допускаю, что можно подобрать другие, подходящие для Comp, функции. Но если такое предположение и верно, то отсюда вовсе не следует, что Comp работает неверно или что доказательство неверно. Если Вы хотите всерьез использовать другую функцию - Вам следует доказать Утверждения 1,2,3 для нее.

Утверждения 1, 2, 3 тривиально следуют из свойств 1 и 2 функции $f(G)$. Достаточно заменить в их доказательствах $A^{-1}$ на $f(G)$.

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

Я уже писал:

Цитата:

1) вы доказываете (после указанной мною замены первой строчки доказательства) правильность работы Comp для всех функций $f(G)$, удовлетворяющих перечисленным мною свойствам.
2) А раз Comp хотя бы для одной функции $f(G)$ (в частности $f(G)=M$) работает не верно, то
3) отсюда (из пунктов 1 и 2) следует, что доказательство не верно.

Цитата:

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

Цитата:

И не надо забывать, что речь идет о функции вида $f(G,b)$ , т.е. у нее 2 аргумента, а не один как Вы написали.

Не надо забывать, что у нее один аргумент, а не два, как вы написали.

У меня два.

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

Цитата:

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

Приведите новое доказательство целиком. Мне не понятно в какое именно место доказательства вы обосновываете с помощью этого аргумента. Плюс сформулируйте, что эта "зависимость весов всех вершин друг от друга" означает в строгих математических терминах. Значит ли это, что все координаты во всех векторах $X[i]$ не нулевые? В таком случае, это будет означать, что в $f(G)$ все элементы отличны от нуля. Тогда можно взять $f(G)=M+E_1$ и алгоритм (по вашему доказательству) останется верным, где $E_1$ - матрица, у которой все элементы равны 1.

[bin]

ha

(Оффтоп)

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

Цитата:

Это Ваша ошибка, что Вы увидели слово "следует" во фразе, где этого слова не было.

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

Согласен, что вопрос можно закрыть. Спасибо, за "пока в порядке с булевой логикой" - я пишу программы не один год и даже не один десяток лет, и раз они работают, то с булевой логикой там порядок, т.к. и Вы программы пишете, считаю, и у Вас с булевой логикой порядок :-) Мы, по обоюдному согласию, закрываем эту подтему, но в скобках думаю стоит отметить, что в нашем недоразумении дело было не в булевой логике, которая безусловно является базой и с которой никто не спорит, а в переводе высказываний естественного языка на формальный уровень булевой логики. Этой проблеме в отношении импликации посвещено много авторитетных источников, и тут бывает очень не тривиально. Сошлюсь только на два источника: Альфред Тарский, Введение в логику и методологию дедуктивных наук. М.: Иностранная литература, 1948, и Н.И. Кондаков, Логический словарь справочник, М: Наука, 1975. В двух словах, в логике различаются понятия материальной и формальной импликации, отмечается ряд парадоксов, связанных с этим. Если захотите продолжать эту тему, то открывайте новую безотносительно к этой теме GI. (Может быть, я в той теме и приму участие.)

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

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

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

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

Если я, повторяя ваши слова нарушаю правила форума, значит вы тоже их нарушаете.

Нет, в правилах попугайства не предусмотрено. Но вот теперь ИМХО, и Вы правил не нарушаете, т.к. оформили ответ на оффтопик офтопиком :-) Кому из читателей будет интересно - тот прочтет, а кто не прочтет наш обмен мнениями по-частному, для заявленной темы, вопросу - ничего не потеряет.

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

Так уже предоставил. Что-то еще не понятно в свойствах 1 и 2?

Мне не понятно, прежде всего, как будет выглядеть доказательство Утверждения 1.

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

Т.е. это не мешает моей функции иметь один аргумент? Так о чем тогда спор?

Ничего не мешает, я только не понимаю, почему мою функцию с 2-мя аргументами Вы подменяете своей, у которой всего 1 аргумент?

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

Цитата:

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

Приведите новое доказательство целиком. Мне не понятно в какое именно место доказательства вы обосновываете с помощью этого аргумента. Плюс сформулируйте, что эта "зависимость весов всех вершин друг от друга" означает в строгих математических терминах. Значит ли это, что все координаты во всех векторах $X[i]$ не нулевые? В таком случае, это будет означать, что в $f(G)$ все элементы отличны от нуля. Тогда можно взять $f(G)=M+E_1$ и алгоритм (по вашему доказательству) останется верным, где $E_1$ - матрица, у которой все элементы равны 1.

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

Говоря другими словами, для системы общих представителей, нужна некоторая "общность", зависимость друг от друга, а иначе у нас будет система произвольно выбранных представителей

-- Пн авг 01, 2011 02:34:07 --

PS

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

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

Это было сделано, см.:

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

1)

Цитата:

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

[...]

$$ \frac{d_{p}\Delta x_{k}}{d_{p}+1}<\Delta x_{k}.$$

2)

Цитата:

$\min(B)\ensuremath{\le}\min(x)\ensuremath{\le}\max(x)\ensuremath{\le}\max(B)$, and if any inequality is proper, then all are.

3) Будем задавать начальный вес, равный единице, вершине, которую мы назовем вершиной-источником, а остальным вершиным графа зададим начальные веса, равные нулю. Решив СЛУ, мы увидим, что все вершины графа приобрели положительный вес, причем он убывает с изменением расстояния от вершины-источника.

[ha]

(Оффтоп)

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

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

Конечно можно. С чего это для самоочевидных ошибок должны существовать самоочевидные исправления? Если кто-то строит короткое доказательство открытой проблемы на том, что из A=>B следует B=>A (к примеру думаю из тысяч любительских доказательств теоремы Ферма такие найдутся), то это не значит, что у открытой проблемы есть короткое решение.

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

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

Так уже предоставил. Что-то еще не понятно в свойствах 1 и 2?

Мне не понятно, прежде всего, как будет выглядеть доказательство Утверждения 1.

Assertion 1 . Пусть $G\cong G'$ и пусть $P$ - матрица перестановки. Пусть $b, b'$ - произвольные вектора размерности $n=|G|=|G'|$. Определим вектора
$X=f(G)b$ и $X'=f(G')b'$. Тогда из $b'=P^{-1}b$ следует $X'=P^{-1}X$.
Доказательство. По свойству 2 $f(G')=P^T\cdot f(G) \cdot P = P^{-1}\cdot f(G) \cdot P$. Отсюда $X'=f(G')\cdot b'=P^{-1}\cdot f(G) \cdot P \cdot P^{-1} \cdot b = P^{-1}\cdot f(G)\cdot b = P^{-1}\cdot X$.

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

Ах да, у вас там в выкладках еще ошибки. Вы в начале доказываете $P^{-1}\cdot D \cdot P = D'$, а потом пишите $D=P^{-1}\cdot D' \cdot P$, хотя должно быть наоборот. Аналогично далее сделаны ошибки с парой $A$ и $A'$ и с парой $M$ и $M'$. Ошибки в итоге сокращаются, так что сам факт остается верным.

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

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

Т.е. это не мешает моей функции иметь один аргумент? Так о чем тогда спор?

Ничего не мешает, я только не понимаю, почему мою функцию с 2-мя аргументами Вы подменяете своей, у которой всего 1 аргумент?

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

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

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

Т.е. ваше "доказательство" пока ничего не доказывает (раз вы обосновать не можете). Именно это я и доказываю.

Цитата:

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

Моя замена ничего не предполагает. Будете пользоваться свойствами $f(G)$ связанные со связностью графа - добавим их в список. Про ребра биграфа - это уж вам решать. Как их определите, так и будет.

Цитата:

Говоря другими словами, для системы общих представителей, нужна некоторая "общность", зависимость друг от друга, а иначе у нас будет система произвольно выбранных представителей

-- Пн авг 01, 2011 02:34:07 --

PS

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

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

Это было сделано, см.:

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

1)

Цитата:

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

[...]

$$ \frac{d_{p}\Delta x_{k}}{d_{p}+1}<\Delta x_{k}.$$

2)

Цитата:

$\min(B)\ensuremath{\le}\min(x)\ensuremath{\le}\max(x)\ensuremath{\le}\max(B)$, and if any inequality is proper, then all are.

3) Будем задавать начальный вес, равный единице, вершине, которую мы назовем вершиной-источником, а остальным вершиным графа зададим начальные веса, равные нулю. Решив СЛУ, мы увидим, что все вершины графа приобрели положительный вес, причем он убывает с изменением расстояния от вершины-источника.

1) то, что написано в статье в этом месте не имеет отношения к математическим доказательствам.
2) В терминах $f(G)$ это означает, что коэффициенты матрицы лежат между 0 и 1. В частности, подходит $f(G)=(M+E_1)/2$.
3) Вы этого не доказали и у меня большие сомнения, что это вообще верно. Среди достаточно больших случайных графов (вершин под 100-1000) с достаточно большим расстоянием наверняка найдется контрпример. Хотите сэкономить время на придумывании неверных доказательств этого факта с тривиальными ошибками - воспользуйтесь компьютером и сделайте эту проверку. Можете еще попытаться построить контрпример непосредственно.

[bin]

Начну с конца:

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

1) то, что написано в статье в этом месте не имеет отношения к математическим доказательствам.
2) В терминах $f(G)$ это означает, что коэффициенты матрицы лежат между 0 и 1. В частности, подходит $f(G)=(M+E_1)/2$.
3) Вы этого не доказали и у меня большие сомнения, что это вообще верно. Среди достаточно больших случайных графов (вершин под 100-1000) с достаточно большим расстоянием наверняка найдется контрпример. Хотите сэкономить время на придумывании неверных доказательств этого факта с тривиальными ошибками - воспользуйтесь компьютером и сделайте эту проверку. Можете еще попытаться построить контрпример непосредственно.

1) Имеет.
2) "коэффициенты матрицы лежат между 0 и 1" - между! но не равны 0. Т.о. все элементы матрицы $A^{-1}$ ненулевые, т.е. элементы $k_{ij}, k_{ji}$ определяют зависимости весов вершин $i,j$ друг от друга, и этим доказано (3).
3) 100-1000 здесь не имеют значения, см. (2).

В ответ на мой вопрос:

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

Про равенство нулю тоже интересный вопрос: нужно ли в Вашей замене для решений равных нулю делать ребро биграфа?

Вы написали:

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

Про ребра биграфа - это уж вам решать. Как их определите, так и будет.

У меня нулей в решениях быть не может, см. выше. А нули в Ваших решениях - это независимость веса данных вершин от вершины-источника, какое $b_i$ на нуль не умножай - будет нуль. Поэтому ребра для нулевых решений добавлять не нужно. Но тут для многих графов мы получим невыполнимость условия теоремы Холла для трансверсали (контрпример из цепи в три вершины сами построите? ). Что уж тут говорить об общей трансверсали. Т.о. Ваша функция не подходит. Может $M^n$ подойдет? Т.о. мои доказательства не обобщаются на Вашу функцию:

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

Я ввел свою функцию и показываю, что ваши доказательства обобщаются на нее.

(Оффтоп)

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

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

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

Конечно можно. С чего это для самоочевидных ошибок должны существовать самоочевидные исправления? Если кто-то строит короткое доказательство открытой проблемы на том, что из A=>B следует B=>A (к примеру думаю из тысяч любительских доказательств теоремы Ферма такие найдутся), то это не значит, что у открытой проблемы есть короткое решение.

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

Цитата:

A common joke in the mathematical community is to say that "trivial" is synonymous with "proved" — that is, any theorem can be considered "trivial" once it is known to be true. Another joke concerns two mathematicians who are discussing a theorem; the first mathematician says that the theorem is "trivial". In response to the other's request for an explanation, he then proceeds with twenty minutes of exposition. At the end of the explanation, the second mathematician agrees that the theorem is trivial. These jokes point out the subjectivity of judgments about triviality. The joke also applies when the first mathematician says the theorem is trivial, but is unable to prove it himself. (wikipedia:Triviality)

[bin]

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

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

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

[ha]

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

Начну с конца:

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

1) то, что написано в статье в этом месте не имеет отношения к математическим доказательствам.
2) В терминах $f(G)$ это означает, что коэффициенты матрицы лежат между 0 и 1. В частности, подходит $f(G)=(M+E_1)/2$.
3) Вы этого не доказали и у меня большие сомнения, что это вообще верно. Среди достаточно больших случайных графов (вершин под 100-1000) с достаточно большим расстоянием наверняка найдется контрпример. Хотите сэкономить время на придумывании неверных доказательств этого факта с тривиальными ошибками - воспользуйтесь компьютером и сделайте эту проверку. Можете еще попытаться построить контрпример непосредственно.

1) Имеет.

Не имеет. А то вы считаете, что имеет говорит лишь о вашем не понимании того, что такое математическое доказательство.

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

2) "коэффициенты матрицы лежат между 0 и 1" - между! но не равны 0. Т.о. все элементы матрицы $A^{-1}$ ненулевые, т.е. элементы $k_{ij}, k_{ji}$ определяют зависимости весов вершин $i,j$ друг от друга, и этим доказано (3).

"и этим доказано (3)" - тривиальная ошибка. Берем матрицу 2x2 с элементами $\big(\begin{array}{cc}0.1 & 0.2\\0.2 & 0.1\end{array}\big)$ и полный граф из 2 вершин. Элементы между 0 и 1, но веса возрастают с расстоянием. Поэтому эти вещи никак не связаны друг с другом.

На пример $f(G)=(M+E_1)/2$ вы таки не ответили. Я уж не говорю о том, что это свойство никак в "доказательстве" не используется, а потому не имеет никакого значения.

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

3) 100-1000 здесь не имеют значения, см. (2).

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

[bin]

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

Пусть графы $G,G'$ изоморфны. Для выбранной пары вершин $(i,j),\: i\in V,\: j\in V'$ с равными степенями строим биграф $H_{ij}=(V,V',E)$, где $V$ - множество вершин графа $G$, $V'$- множество вершин графа $G'$ , и вершина $p\in V$ соединена ребром с вершиной $q\in V'$, если у вершин $p,q$ одинаковая степень и для элементов матриц $A^{-1},\: A'^{-1}$: $k_{ip}=k'_{jq}$. Число ребер биграфа не будет превосходить $n^{2}$. Очевидно, что для единичных векторов $e_{i},\: e_{j}$ решения СЛУ $X_{i},\: X_{j}$ будут совпадать, т.е. $X_{i}[p]=X_{j}[q]$, если существует ребро $(p,q)$ в биграфе $H_{ij}$. Обратное также верно: если $X_{i}[p]\neq X_{j}[q]$, то не существует ребра $(p,q)$ в биграфе $H_{ij}$. Каждая из вершин $i,j$ в биграфе $H_{ij}$ будет инцидентна только одному ребру (и это ребро $(i,j)$), так как в силу формулы (5) версии 2 препринта:

$$ \begin{cases} \begin{array}{cc} 1\text{<}k_{ij}<2 & if \: i=j,\\ 0<k_{ij}<1 & otherwise.\end{array}\end{cases}(5)$$

(ha предложил уточнение для верхней границы $k_{ii}$, однако в данном случае это не принципиально).
Из (5) также видно, что все $k_{ij}\neq0$.

Пусть функция $T(E)$ возращает трансверсаль (подмножество ребер биграфа $H$), если такая трансверсаль существует (любую трансверсаль, если их несколько), и пустое множество в противном случае.

Алгоритм.
1) Для указанной на входе пары вершин $(i,j),\: i\in V,\: j\in V'$ построим биграф $H_{ij}$, как описано выше.
2) Будем перебирать все его ребра за исключением ребра $(i,j)$, для каждого ребра $(p,q)$ построим биграф $H_{pq}$, как описано выше. Если $T(E_{ij}\bigcap E_{pq})\neq\varnothing$, то меняем ребра $E_{ij}:=E_{ij}\bigcap E_{pq}$ , иначе удаляем ребро $(p,q)$ из $H_{ij}$.
3) Если $T(E_{ij})\neq\varnothing$, то полученная трансверсаль будет единственной, и она будет представлять изоморфное отображение заданных графов.
Конец алгоритма.

Докажем корректность алгоритма. При этом будем считать, что на входе задана пара подобных вершин. Доказательство разобъем на четыре достаточно независимых друг от друга части.

1) Прежде всего покажем корректность постановки задачи об общих представителях. (В тривиальных хрестоматийных случаях такое доказательство является зачастую излишним, поскольку в задаче о браках, например, то, что различные представители являются действительно представителями, а не посторонними персонами, следует из условия самой задачи.) Итак, веса всех вершин линейно зависимы от начальных весов всех вершин, т.к. все $k_{ij}\neq0$. Поэтому любое уравнение СЛУ накладывает одинаковые по жесткости условия на распределение весов (по Свойству 2 суммы начальных $(B)$ и конечных весов равны, поэтому речь идет о перераспределении начальных весов). (Например, если бы какое-то $k_{ij}=0$, то по $i$-ому уравнению СЛУ величина $x_{i}$ не зависела бы от начального веса вершины $j$.) Поэтому, пользуясь терминологией теории распознавания образов, можно утверждать, что во всех уравнениях все признаки $(k_{ij})$ одинаково информативны. И поэтому в пространстве данных признаков (весов) любая вершина графа $G$ может быть представителем всех вершин этого графа или изоморфного ему $(G')$. Это очень важный, хотя и не очевидный момент, поэтому, хотя "лирические'' отступления не приняты в доказательствах, но в данном случае по причине неочевидности такое отступление выглядит уместным. Еще в прошлом веке журнал Scientific American опубликовал впечатляющую корреляцию рождаемости в одной из скандинавских стран от поголовья аистов, тем самым проиллюстрировав, насколько больной является практическая проблема выявления действительных (а не мнимых) зависимостей. В нашем случае существует строгая очевидная зависимость. Без такой зависимости содержательная постановка вопроса об общих представителях была бы некорректной.

Отметим также, что для вершин с равными степенями $k_{ij}=k_{ji}$ (препринт версия 2, формула 6) и, как уже отмечалось, все $k_{ij}\neq0$. Поэтому, если вершина $i$ подобна вершине $j$, а вершина $p$ подобна вершине $q$, $(i,p\in V,\: j,q\in V')$, то для каждой вершины $u\in V$ найдется такая вершина $v\in V'$, что ребро $(u,v)\in E_{ij}$ и $(u,v)\in E_{pq}$ и таким образом $T(E_{ij}\bigcap E_{pq})\neq\varnothing$.

2) Докажем, что если $T(E_{ij})\neq\varnothing$, то эта полученная в результате работы алгоритма трансверсаль будет единственной. Как было отмечено выше: каждая из вершин $p,q$ в биграфе $H_{pq}$ будет инцидентна только одному ребру $(p,q)$. Поэтому в пересечении $E_{ij}\bigcap E_{pq}$ для вершин $p,q$ останется только это ребро, и при замене ребер $E_{ij}:=E_{ij}\bigcap E_{pq}$ в биграфе $H_{pq}$ вершины $p,q$ будут инцидентны только одному ребру $(p,q)$. Перебрав все ребра $E_{ij}$ , мы получаем биграф $H_{ij}$ , в котором каждой вершине инцидентно только одно ребро.

3) Докажем, что если в результате работы алгоритма $T(E_{ij})\neq\varnothing$, то она будет представлять изоморфное отображение заданных графов. Как было отмечено выше: $X_{i}[p]=X_{j}[q]$, если существует ребро $(p,q)$ в биграфе $H_{ij}$. При этом $T(E_{ij})$ будет общей для $E_{ij}$ и для $E_{pq}$, т.е. для каждого ребра $(u,v)\in E_{ij}$ найдется ребро $(u,v)\in E_{pq}$. Возьмем перестановку $P$, заданную этими ребрами (т.е. для каждого ребра $(p,q)$ полагаем $p\rightarrow q$) и $n$ линейно независимых векторов $e_{1},...,e_{n}$. Пусть $b_{p}=e_{p},\: p=1,...,n;\: b'=P^{-1}\cdot b$, тогда получим $X'=P^{-1}\cdot X$ и по Утверждению 3 $P$ будет изоморфизмом.

4) Пусть порядок перебора первых $n$ ребер биграфа $H_{ij}$ совпал с отображениями, дающими изоморфизм графов: $i\leftrightarrow j,\: r_{1}\leftrightarrow r'_{1},...,r_{n-1}\leftrightarrow r'_{n-1}$. Тогда $T(E_{ij})=\{(i,j),(r_{1},r'_{1}),...,(r_{n-1},r'_{n-1})\}$ будет общей для $E_{r_{1}r'_{1}},...,E_{r_{n-1}r_{n-1}}$. Пусть далее в переборе следует ребро $(p,q)$, образованное парой неподобных вершин $(p,q)$, таких, что $k_{ip}=k'_{jq}$. Тогда $T(E_{ij}\bigcap E_{pq})=\varnothing$, иначе $T(E_{ij}\bigcap E_{pq})$ было бы общей для $E_{r_{1}r'_{1}},...,E_{r_{n-1}r_{n-1}}$ и существовал бы изоморфизм, в который бы входило отображение $p\leftrightarrow q$, а тогда бы вершины $p,q$ были бы подобны, что противоречит сделанному выше условию. Пусть далее в переборе следует ребро $(p,q)$, образованное парой подобных вершин $(p,q)$. Если $T(E_{ij}\bigcap E_{pq})\neq\varnothing$, то будет найден другой изоморфизм, иначе ребро $(p,q)$ будет удалено. В силу свойств коммутативности и ассоциативности операции пересечения, результат не зависит от порядка перебора ребер биграфа $H_{ij}$.
Конец доказательства корректности алгоритма.

Из доказанного следует, что задача изоморфизма графов может быть сведена к частному случаю задачи поиска общих представителей.
Работа алгоритма для неизоморфных графов и неподобных вершин на его входе не рассматривается, поэтому результат должен быть проверен функцией Verify. Очевидно, что подавая на вход алгоритма пары вершин $(1,j),\: j=1,...,n$, в случае изоморфных графов, мы натолкнемся на пару подобных вершин, для которых алгоритм сработает доказанным выше образом. В случае неизоморфных графов возможны непредсказуемые результаты, все они будут забракованы функцией Verify. Как было отмечено выше, число ребер $H_{ij}$ не превосходит $n^{2}$, следовательно, число биграфов $H_{pq}$ не превосходит $n^{2}$. Построение каждого биграфа имеет полиномиальную вычислительную сложность. Следовательно, алгоритм закончит работу за полиномиальное время. Алгоритм можно модифицировать, добавив условие выхода из шага 2, как только будет найдено $n$ биграфов с общей трансверсалью. Однако оценку сложности для наихудшего случая такая модификация не улучшит.

[ha]

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

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

Пусть графы $G,G'$ изоморфны. Для выбранной пары вершин $(i,j),\: i\in V,\: j\in V'$ с равными степенями строим биграф $H_{ij}=(V,V',E)$, где $V$ - множество вершин графа $G$, $V'$- множество вершин графа $G'$ , и вершина $p\in V$ соединена ребром с вершиной $q\in V'$, если у вершин $p,q$ одинаковая степень и для элементов матриц $A^{-1},\: A'^{-1}$: $k_{ip}=k'_{jq}$.
Число ребер биграфа не будет превосходить $n^{2}$. Очевидно, что для единичных векторов $e_{i},\: e_{j}$ решения СЛУ $X_{i},\: X_{j}$ будут совпадать, т.е. $X_{i}[p]=X_{j}[q]$, если существует ребро $(p,q)$ в биграфе $H_{ij}$. Обратное также верно: если $X_{i}[p]\neq X_{j}[q]$, то не существует ребра $(p,q)$ в биграфе $H_{ij}$. Каждая из вершин $i,j$ в биграфе $H_{ij}$ будет инцидентна только одному ребру (и это ребро $(i,j)$), так как в силу формулы (5) версии 2 препринта:

$$ \begin{cases} \begin{array}{cc} 1\text{<}k_{ij}<2 & if \: i=j,\\ 0<k_{ij}<1 & otherwise.\end{array}\end{cases}(5)$$

(ha предложил уточнение для верхней границы $k_{ii}$, однако в данном случае это не принципиально).
Из (5) также видно, что все $k_{ij}\neq0$.

Пусть функция $T(E)$ возращает трансверсаль (подмножество ребер биграфа $H$), если такая трансверсаль существует (любую трансверсаль, если их несколько), и пустое множество в противном случае.

Я так понимаю, что $T(E)$ либо возвращает ребра в полном паросочетании, либо пустое множество, если его нет.

Цитата:

Алгоритм.
1) Для указанной на входе пары вершин $(i,j),\: i\in V,\: j\in V'$ построим биграф $H_{ij}$, как описано выше.
2) Будем перебирать все его ребра за исключением ребра $(i,j)$, для каждого ребра $(p,q)$ построим биграф $H_{pq}$, как описано выше. Если $T(E_{ij}\bigcap E_{pq})\neq\varnothing$, то меняем ребра $E_{ij}:=E_{ij}\bigcap E_{pq}$ , иначе удаляем ребро $(p,q)$ из $H_{ij}$.

Не дано никакого определения $E_{ij}$. Я так понимаю, что в начале $E_{ij}=H_{ij}$, а потом уменьшаются. В таком случае удалять ребра надо не из H, а из E.

Цитата:

3) Если $T(E_{ij})\neq\varnothing$, то полученная трансверсаль будет единственной, и она будет представлять изоморфное отображение заданных графов.
Конец алгоритма.

Докажем корректность алгоритма. При этом будем считать, что на входе задана пара подобных вершин. Доказательство разобъем на четыре достаточно независимых друг от друга части.

1) Прежде всего покажем корректность постановки задачи об общих представителях.

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

Цитата:

(В тривиальных хрестоматийных случаях такое доказательство является зачастую излишним, поскольку в задаче о браках, например, то, что различные представители являются действительно представителями, а не посторонними персонами, следует из условия самой задачи.) Итак, веса всех вершин линейно зависимы от начальных весов всех вершин, т.к. все $k_{ij}\neq0$.

Линейно зависимыми могут быть векторы. Никаких векторов я тут не вижу. Скорее всего имеется в виду, что веса являются линейными функциями от начальных весов. Но это верно вне зависимости от $k_{ij}\neq0$. $f(x) = 0$ является линейной функцией от $x$. Налицо либо боязнь нуля, либо не понимание линейной алгебры.

Цитата:

Поэтому любое уравнение СЛУ накладывает одинаковые по жесткости условия на распределение весов (по Свойству 2 суммы начальных $(B)$ и конечных весов равны, поэтому речь идет о перераспределении начальных весов).

Что такое "одинаковые по жесткости условия"? В любом случае эта фраза тут похоже не несет математического смысла.

Цитата:

(Например, если бы какое-то $k_{ij}=0$, то по $i$-ому уравнению СЛУ величина $x_{i}$ не зависела бы от начального веса вершины $j$.) Поэтому, пользуясь терминологией теории распознавания образов, можно утверждать, что во всех уравнениях все признаки $(k_{ij})$ одинаково информативны.

Это не является математическим утверждением. Поэтому, я так понимаю, и следующая фраза тоже не является математическим утверждением. По крайней мере никакого определения пространства весов и понятия "представителя" нету.

Цитата:

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

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

Цитата:

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

Отметим также, что для вершин с равными степенями $k_{ij}=k_{ji}$ (препринт версия 2, формула 6) и, как уже отмечалось, все $k_{ij}\neq0$.

Цитата:

Поэтому, если вершина $i$ подобна вершине $j$, а вершина $p$ подобна вершине $q$, $(i,p\in V,\: j,q\in V')$, то для каждой вершины $u\in V$ найдется такая вершина $v\in V'$, что ребро $(u,v)\in E_{ij}$ и $(u,v)\in E_{pq}$ и таким образом $T(E_{ij}\bigcap E_{pq})\neq\varnothing$.

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

Цитата:

2) Докажем, что если $T(E_{ij})\neq\varnothing$, то эта полученная в результате работы алгоритма трансверсаль будет единственной. Как было отмечено выше: каждая из вершин $p,q$ в биграфе $H_{pq}$ будет инцидентна только одному ребру $(p,q)$. Поэтому в пересечении $E_{ij}\bigcap E_{pq}$ для вершин $p,q$ останется только это ребро, и при замене ребер $E_{ij}:=E_{ij}\bigcap E_{pq}$ в биграфе $H_{pq}$ вершины $p,q$ будут инцидентны только одному ребру $(p,q)$. Перебрав все ребра $E_{ij}$ , мы получаем биграф $H_{ij}$ , в котором каждой вершине инцидентно только одно ребро.

Верно.

Цитата:

3) Докажем, что если в результате работы алгоритма $T(E_{ij})\neq\varnothing$, то она будет представлять изоморфное отображение заданных графов. Как было отмечено выше: $X_{i}[p]=X_{j}[q]$, если существует ребро $(p,q)$ в биграфе $H_{ij}$. При этом $T(E_{ij})$ будет общей для $E_{ij}$ и для $E_{pq}$,

Не будет. Это выполнено только для ребер $(p,q)$ в $E_{ij}$.

Цитата:

т.е. для каждого ребра $(u,v)\in E_{ij}$ найдется ребро $(u,v)\in E_{pq}$. Возьмем перестановку $P$, заданную этими ребрами (т.е. для каждого ребра $(p,q)$ полагаем $p\rightarrow q$)

Для каждого ребра из какого графа? Логично предположить, что из $T(E_{ij})$.

Цитата:

и $n$ линейно независимых векторов $e_{1},...,e_{n}$. Пусть $b_{p}=e_{p},\: p=1,...,n;\: b'=P^{-1}\cdot b$, тогда получим $X'=P^{-1}\cdot X$ и по Утверждению 3 $P$ будет изоморфизмом.

Верно.

Цитата:

4) Пусть порядок перебора первых $n$ ребер биграфа $H_{ij}$ совпал с отображениями, дающими изоморфизм графов: $i\leftrightarrow j,\: r_{1}\leftrightarrow r'_{1},...,r_{n-1}\leftrightarrow r'_{n-1}$. Тогда $T(E_{ij})=\{(i,j),(r_{1},r'_{1}),...,(r_{n-1},r'_{n-1})\}$ будет общей для $E_{r_{1}r'_{1}},...,E_{r_{n-1}r_{n-1}}$. Пусть далее в переборе следует ребро $(p,q)$, образованное парой неподобных вершин $(p,q)$, таких, что $k_{ip}=k'_{jq}$. Тогда $T(E_{ij}\bigcap E_{pq})=\varnothing$, иначе $T(E_{ij}\bigcap E_{pq})$ было бы общей для $E_{r_{1}r'_{1}},...,E_{r_{n-1}r_{n-1}}$ и существовал бы изоморфизм, в который бы входило отображение $p\leftrightarrow q$, а тогда бы вершины $p,q$ были бы подобны, что противоречит сделанному выше условию. Пусть далее в переборе следует ребро $(p,q)$, образованное парой подобных вершин $(p,q)$. Если $T(E_{ij}\bigcap E_{pq})\neq\varnothing$, то будет найден другой изоморфизм, иначе ребро $(p,q)$ будет удалено.

Не вижу смысла в таких сложностях. Если порядок совпадает, то после n шагов никаких других ребер кроме $\{(i,j),(r_{1},r'_{1}),...,(r_{n-1},r'_{n-1})\}$ не останется в силу "Как было отмечено выше: каждая из вершин $p,q$ в биграфе $H_{pq}$ будет инцидентна только одному ребру $(p,q)$."

Цитата:

В силу свойств коммутативности и ассоциативности операции пересечения, результат не зависит от порядка перебора ребер биграфа $H_{ij}$.

Тривиальная ошибка. Коммутативность и ассоциативность пересечения никак не связаны с зависимостью результата от порядка перебора ребер биграфа $H_{ij}$. Более того, существование нескольких изоморфизмов это прямо опровергает - в разном порядке получатся разные изоморфизмы, т.е. разный результат.

Более того, это доказательство по-прежнему опровергается с помощью $f(G)=2E+M$. В частности, не сложно привести граф, где нарушится пункт 4.