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

[bin]

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

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

Да.

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

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

Хорошо, напишем так: $H_{ij}=(V,V',E_{ij})$, где $ E_{ij}$ множество ребер биграфа $H_{ij}$. Удаляя из $E$, тем самым удаляем и из $H$. Что тут непонятного?

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

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

У слов естественного языка бывает несколько смыслов. Смысл, который я употребляю, широко используется в computer sci. Например,

Цитата:

Модульное тестирование, или юнит-тестирование (англ. unit testing) — процесс в программировании, позволяющий проверить на корректность отдельные модули исходного кода программы. (Википедия)

Цитата:

Валидатор формата (часто просто валидатор, калька с англ. validator) — компьютерная программа, которая проверяет соответствие какого-либо документа, потока данных, или фрагмента кода определённому формату, проверяет синтаксическую корректность документа или файла — то есть, производит валидацию. Википедия

С этим замечанием не согласен, как и со следующим:

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

Линейно зависимыми могут быть векторы. Никаких векторов я тут не вижу.

Могут быть и столбцы (строки) матрицы:

Цитата:

Линейная система $n$ уравнений, где $n$ — количество переменных, имеет однозначное решение тогда и только тогда, когда столбцы её основной матрицы являются линейно независимыми.(Википедия)

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

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

Несет. Если $x=ay+bz; a,b\neq 0$, то $x$ зависит как от $y$, так и от $z$. Если же $a\neq 0$, а $b=0$, то признаком $z$ нужно пренебречь. Например, любимый Вами закон Ома для участка цепи, где сила тока $x$ прямо пропорциональна напряжению $y$, а признак $z$ - это цвет изоляции провода, из которого сделана эта цепь.

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

Цитата:

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

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

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

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

Цитата:

Отметим также, что для вершин с равными степенями $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 вершин. Ссылок на это утверждение в дальнейшем, впрочем, тоже нет.

Не понял.

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

Цитата:

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

Как это не будет, когда на шаге 2 алгоритма происходит замена $E_{ij}$? Не понял.

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

Цитата:

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

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

Написано: "для каждого ребра $(u,v)\in E_{ij}$". $E_{ij}$ - множество ребер графа $H_{ij}$. Что тут непонятного?

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

Цитата:

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)$."

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

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

Цитата:

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

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

Не связаны, речь о результате, т.е. о том, что в силу коммутативности и ассоциативности $E_{ij}\bigcap E_{pq}\bigcap ...= E_{pq}\bigcap E_{ij}\bigcap ...$ и результат будет одинаковым (с точностью до изоморфизма - с этим замечанием согласен) при разных порядках перебора.

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

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

$f(G)=2E+M$ не подходит по пункту 1: для многих графов не все веса будут зависимыми друг от друга. См. пример выше с законом Ома и цветом провода. Похоже, этой функцией Вы предлагаете некорректность (т.е. независимость от свободных переменных) в том самым мат. смысле, о котором сказали.

[ha]

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

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

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

Хорошо, напишем так: $H_{ij}=(V,V',E_{ij})$, где $ E_{ij}$ множество ребер биграфа $H_{ij}$. Удаляя из $E$, тем самым удаляем и из $H$. Что тут непонятного?

Вы обозначаете множество ребер в графе отдельной буквой? Теперь кое-что обретает смысл.

Цитата:

У слов естественного языка бывает несколько смыслов. Смысл, который я употребляю, широко используется в computer sci. Например,

Цитата:

Модульное тестирование, или юнит-тестирование (англ. unit testing) — процесс в программировании, позволяющий проверить на корректность отдельные модули исходного кода программы. (Википедия)

Цитата:

Валидатор формата (часто просто валидатор, калька с англ. validator) — компьютерная программа, которая проверяет соответствие какого-либо документа, потока данных, или фрагмента кода определённому формату, проверяет синтаксическую корректность документа или файла — то есть, производит валидацию. Википедия

С этим замечанием не согласен, как и со следующим:

Этот смысл к слову задача не применим. Может быть корректное (т.е правильное) решение задачи. Но как может быть корректной (правильной) сама задача?! Таким образом вы написали абзац непонятно о чем.

Цитата:

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

Линейно зависимыми могут быть векторы. Никаких векторов я тут не вижу.

Могут быть и столбцы (строки) матрицы:

Цитата:

Линейная система $n$ уравнений, где $n$ — количество переменных, имеет однозначное решение тогда и только тогда, когда столбцы её основной матрицы являются линейно независимыми.(Википедия)

И что? Это не отменяет сути замечания. $y=0\cdot x$ как была совершенно обычной линейной функцией так всегда ей и будет как бы вы не пытались убедить в обратном. Безуспешные попытки выкинуть здесь 0 говорит лишь о вашем не понимании линейной алгебры. Ни в одном из ваших рассуждений отличность коэффициентов от нуля по существу не используется.

Цитата:

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

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

Несет. Если $x=ay+bz; a,b\neq 0$, то $x$ зависит как от $y$, так и от $z$. Если же $a\neq 0$, а $b=0$, то признаком $z$ нужно пренебречь. Например, любимый Вами закон Ома для участка цепи, где сила тока $x$ прямо пропорциональна напряжению $y$, а признак $z$ - это цвет изоляции провода, из которого сделана эта цепь.

Никакого математического определения "одинаковые по жесткости условия" в вашем ответе не дано, так что фраза по прежнему не несет никакого математического смысла.

Цитата:

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

А обязаны. Признаки могут быть разными и соответственно определения пространств будут разными. Аналогично с представителями. Без конкретных определений это пустое сотрясание воздуха. Впрочем даже с ними ваши отсылки к AI в задаче изоморфизма графов не имеют никакого математического смысла.

Цитата:

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

Цитата:

Отметим также, что для вершин с равными степенями $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 вершин. Ссылок на это утверждение в дальнейшем, впрочем, тоже нет.

Не понял.

Научитесь понимать свои тривиальные ошибки и совершенно тривиальный математический текст.

Цитата:

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

Цитата:

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

Как это не будет, когда на шаге 2 алгоритма происходит замена $E_{ij}$? Не понял.

Ваше новое определение $E_{ij}$ отличается от того, которое я предположил в виду его отсутствия. С его учетом это возражение снимается. Надо будет перепроверить части 2 и 3. Их верность с его учетом может измениться.

Цитата:

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

Цитата:

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

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

Написано: "для каждого ребра $(u,v)\in E_{ij}$". $E_{ij}$ - множество ребер графа $H_{ij}$. Что тут непонятного?

Не понятен конец фразы про каждое ребро $(p,q)$.

Цитата:

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

Цитата:

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)$."

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

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

Цитата:

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

Цитата:

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

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

Не связаны, речь о результате, т.е. о том, что в силу коммутативности и ассоциативности $E_{ij}\bigcap E_{pq}\bigcap ...= E_{pq}\bigcap E_{ij}\bigcap ...$ и результат будет одинаковым (с точностью до изоморфизма - с этим замечанием согласен) при разных порядках перебора.

Можете хоть сто раз это повторить. Как тривиальная ошибка была, так и осталась. Занятно смотреть как вы пытаетесь обмануть окружающих. $A\bigcap B = B\bigcap A$ без всяких "с точностью до изоморфизма". Откуда же это условие "с точностью до изоморфизма" появляется? Да вы просто его вставляете, чтобы выглядело правдоподобнее. Правильности доказательству это не прибавляет, а только говорит о вашем не понимании того, что такое доказательство.

Цитата:

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

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

$f(G)=2E+M$ не подходит по пункту 1: для многих графов не все веса будут зависимыми друг от друга. См. пример выше с законом Ома и цветом провода.

Пункт 1 не имеет никакого отношения к доказательству. На него нет никаких ссылок, а сам текст в нем не является математическим. Поэтому, его можно совершенно спокойно выкинуть. Так что $f(G)=2E+M$ совершенно отлично подходит и опровергает доказательство.

Цитата:

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

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

-- Сб авг 13, 2011 00:31:52 --

Перепроверил. Пункты 2 и 3 верны. Наконец-то заметил где у вас вводится $E$. Учитывая, что это сделано не так, как требуется в математике, нет ничего удивительного, что я его не заметил.

[bin]

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

Этот смысл к слову задача не применим.

Не к слову "задача", а к слову постановка. Задача может быть сформулирована корректно (верно) и некорректно (неверно). Так, например, использовать веса, которые не передают информацию о всем графе, некорректно.

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

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

Линейно зависимыми могут быть векторы. Никаких векторов я тут не вижу.

Цитата:

Могут быть и столбцы (строки) матрицы:

Цитата:

Линейная система $n$ уравнений, где $n$ — количество переменных, имеет однозначное решение тогда и только тогда, когда столбцы её основной матрицы являются линейно независимыми.(Википедия)

И что? Это не отменяет сути замечания. $y=0\cdot x$ как была совершенно обычной линейной функцией так всегда ей и будет как бы вы не пытались убедить в обратном. Безуспешные попытки выкинуть здесь 0 говорит лишь о вашем не понимании линейной алгебры. Ни в одном из ваших рассуждений отличность коэффициентов от нуля по существу не используется.

Тогда я не понимаю суть Вашей претензии. Сначала Вы сказали, что векторов тут не видите. Я привел пример, где говорится не про векторы. И причем тут линейная алгебра? У меня она используется как инструмент, позволяющий провести преобразование формул, например, в доказательстве Утверждения 1. А речь о содержательной постановке задачи. Если к задачам подходить чисто формально, то с помощью инструмента "мат.статистика" можно получить прекрасную корреляцию между приростом народонаселения и поголовьем аистов, и хотя с точки зрения мат. статистики все сделано верно, результат будет неверным по содержанию.

(Оффтоп)

И снова Вы переходите на личности Поймите, наконец, что данная тема не о моих познаниях и пониманиях.

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

Никакого математического определения "одинаковые по жесткости условия" в вашем ответе не дано, так что фраза по прежнему не несет никакого математического смысла.

Предложите свой вариант

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

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

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

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

Впрочем даже с ними ваши отсылки к AI в задаче изоморфизма графов не имеют никакого математического смысла.

Задача GI может быть сформулирована и в терминах распознавания образов.

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

Научитесь понимать свои тривиальные ошибки и совершенно тривиальный математический текст.

Научитесь понятно ставить вопросы, тогда я смогу на них ответить.

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

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

Не понял. У меня сделано допущение "Если порядок совпадает", а если он не совпадает? Как это доказать проще, Вы не написали.

(Оффтоп)

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

Занятно смотреть как вы пытаетесь обмануть окружающих.

Никого я обмануть не пытаюсь. Не научный спор, а базар какой-то!

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

Откуда же это условие "с точностью до изоморфизма" появляется?

Условие появляется из Вашего замечания, что "в разном порядке получатся разные изоморфизмы".

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

Так что $f(G)=2E+M$ совершенно отлично подходит и опровергает доказательство.

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

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

Цитата:

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

[bin]

PS

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

$y=0\cdot x$ как была совершенно обычной линейной функцией так всегда ей и будет

$y=0\cdot x$ не биективна, а мы ищем изоморфизм, т.е. биекцию.

[bin]

Выложил новую версию статьи:
http://arxiv.org/abs/1004.1808
Жду откликов.

[bin]

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

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

Я уже устал ждать, когда наконец будет предоставлено обещанное "опровержение". Возьмите какой-нибудь граф и распишите действия алгоритма с придуманной Вами функцией $2E+M$, где будут происходить ошибки. Сразу будет видно, что причина неверной работы - вырождения, происходящие от того, что функция $y=0x$ невзаимнооднозначная.

[rtfai]

Я тоже занимался этой проблемой, и уменя простой вопрос, Вы все графы Маккея просчитали?

Дело в том, что более сложных примеров чем у Маккея нет...

[bin]

rtfai
Вероятно, нет - нужно уточнить вопрос: см.ЛС.

[whitefox]

Всем привет!
Я снова здесь, и могу продолжить обсуждение алгоритма автора.

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

Решить за полиномиальное время проблему изоморфизма графов при наличии доступа к оракулу, отвечающему правдиво на вопрос "Подобна ли вершина $i$ графа $G$ вершине $j$ графа $G'$ ?" если графы $G$ и $G'$ изоморфны, и дающему произвольный ответ в противном случае.

(ПОДОБИЕ)

Напомню, что термин подобие используется здесь в расширенном автором смысле:

Цитата:

According to Harary’s definition: “Two points [vertices – MT] $u$ and $v$ of the
graph $G$ are $similar$ if for some automorphism $\alpha$ of $G$, $\alpha(u) = v$.” [5], p.171.
We expand this definition for vertex $u$ of the graph $G$ and vertex $v$ of the graph
$G'$:
Definition 1. If $G\cong G'$ and $v\leftrightarrow u$ is possible mapping, then $u$ and $v$ are
$similar$.

В переводе на язык математики это должно звучать примерно так:
Вершина $u$ графа $G$ и вершина $v$ графа $G'$ $\textit{подобны}$, если существует изоморфизм $\alpha$ графа $G$ на граф $G'$ для которого $\alpha(u)=v.$

Автор привёл два алгоритма (один из которых решат эту задачу, а второй предположительно решает), и попросил высказать своё мнение.
Мой ответ был:

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

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

А какое мнение об алгоритме 2?

Ну, раз Вы спросили, отвечу:
ни алгоритм 1, ни алгоритм 2 не нужен для решения поставленной Вами задачи.

Поясню свою точку зрения.

Рассмотрим две копии графа $G$.
Так как они необходимо изоморфны, то по отношению к ним наш оракул всегда будет давать правдивые ответы.
Далее используем хорошо-известный способ сведения проблемы изоморфизма к проблеме автоморфного разбиения графа (т.е. разбиения множества вершин графа на классы подобных вершин). Смотри, например, R. Mathon, A note on the graph isomorphism counting problem, Inform. Process. Lett., 8 (1979), 131–132, или И.Н. Пономаренко, Проблема изоморфизма графов: Алгоритмические аспекты (записки к лекциям).
А именно:
Пусть нам даны два $n$-вершинных графа $G_1$ и $G_2$ с не пересекающимися множествами вершин.
Возьмём ещё две вершины $x_1$ и $x_2$ не принадлежащие ни $V(G_1)$ ни $V(G_2).$
Вершину $x_1$ соединим ребром с каждой вершиной графа $G_1$, а вершину $x_2$ с каждой вершиной графа $G_2.$
Дополнительно соединим ребром сами вершины $x_1$ и $x_2.$
Полученный граф обозначим как $G_{12}.$
В этом графе только вершины $x_1$ и $x_2$ имеют степень $n+1$, степень всех прочих вершин не более чем $n.$
Поэтому любой автоморфизм $\alpha$ графа $G_{12}$ либо оставляет эти вершины на месте, либо переводит их друг в друга.
Последнее имеет место тогда и только тогда, когда ограничение автоморфизма $\alpha$ на графы $G_1$ и $G_2$ является их изоморфизмом.
Следовательно графы $G_1$ и $G_2$ изоморфны тогда и только тогда, когда вершины $x_1$ и $x_2$ графа $G_{12}$ подобны.
А на последний вопрос наш оракул даёт правдивый ответ.

Таким образом, выполнив за линейное время построение графа $G_{12}$, и задав оракулу один единственный вопрос, мы решим проблему изоморфизма графов $G_1$ и $G_2.$

Всё, что нужно автору это доказать, что предложенная им функция Comp является тем самым оракулом, и может быть вычислена за полиномиальное время.

Приступаю к изучению нового варианта статьи.

[whitefox]

2bin
Насколько я понял, для правильной работы процедуры P1 совершенно необходима приведённая Вами верхняя оценка величин $k_{ij}$

Цитата:

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

Не могли бы Вы поподробнее изложить её вывод?

[whitefox]

Вы не рассматривали возможность вместо Вашей матрицы:

$$\mathrm{A}=\mathrm{E}-\mathrm{D^{-1}}\mathrm{M}$$

где:
$\mathrm{E}$ -- единичная матрица,
$\mathrm{D}=\operatorname{diag}(d_{1}+1,d_{2}+1,\dots,d_{n}+1) $ -- диагональная матрица ($d_i$ степень вершины $i$)
$\mathrm{M}$ -- матрица смежности

использовать матрицу:

$$\mathrm{A_0}=\mathrm{E}-\mathrm{D^{-\frac12}}\mathrm{M}\mathrm{D^{-\frac12}}$$

при тех же самых $\mathrm{E}$, $\mathrm{D}$ и $\mathrm{M}$?

Матрица $\mathrm{A_0}$ обладает всеми свойствами матрицы $\mathrm{A}$ и, кроме того, она симметрическая.
А это позволит упростить некоторые Ваши выкладки.
Так, например, Вы часто используете свойство $k_{ij}=k_{ji}\textrm{ если }d_i=d_j$.
В случае симметрической матрицы $\mathrm{A_0}$ свойство $k_{ij}=k_{ji}$ выполнено всегда, не зависимо от равенства $d_i$ и $d_j.$

[whitefox]

Ваша процедура P1 на некоторых графах работает не верно.
Свои соображения изложу когда будет свободное время.

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

Вы оперируете матрицей $\mathrm{D}-\mathrm{M}$, где $\mathrm{D}=\operatorname{diag}(d_{1}+1,d_{2}+1,\dots,d_{n}+1)$
Они используют матрицу $\mathrm{D_0}+\mathrm{M}$, где $\mathrm{D_0}=\operatorname{diag}(d_{1}+d,d_{2}+d,\dots,d_{n}+d)$, $d=\max(d_1,d_2,\dots,d_n)$

Они, также как и Вы, для графов $G$ и $G'$ строят вектора $X$ и $X'$ решений соответствующих СЛАУ такие, что оба вектора совпадают с точностью до перестановки, но все координаты одного вектора попарно различны. Затем, полученную таким образом перестановку, проверяют на изоморфизм.
Это Вам ничто не напоминает?

Похоже, что вы одновременно пришли к одной и той же идее.
Впрочем, уверен, что приоритет за Вами.

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

Полагаю, что эти выводы применимы и к Вашему алгоритму.

[bin]

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

Всем привет! Я снова здесь, и могу продолжить обсуждение алгоритма автора.

И Вам привет!

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

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

Не аналогичен. (В противном случае все подходы, где решается СЛУ, придется называть аналогичными ) Выше я уже говорил, что избегаю, по-возможности, сравнивать и критиковать здесь чужие алгоритмы. Упомянутые авторы опубликовали ряд работ, в которых предложен ряд остроумных алгоритмов. Они (эти авторы) идут своим путем, а я иду другим. Некоторые принципиальные соображения в отношении работ указанных авторов были высказаны в моей статье (совместно с Е.А.Смоленским), опубликованной в Известиях РАН в 2005 г. (ссылка на которую приведена в абстракте). Думаю, что повторять эти соображения здесь избыточно.

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

Далее используем хорошо-известный способ сведения проблемы изоморфизма к проблеме автоморфного разбиения графа (т.е. разбиения множества вершин графа на классы подобных вершин). Смотри, например, R. Mathon, A note on the graph isomorphism counting problem, Inform. Process. Lett., 8 (1979), 131–132, или И.Н. Пономаренко, Проблема изоморфизма графов: Алгоритмические аспекты (записки к лекциям).

Я читал многие статьи Пономаренко, посвященные проблеме изоморфизма графов. Приведенная ссылка - это своего рода популяризация этих работ для студентов. На мой взгляд, очень хорошая и нужная. К недостатком я бы отнес некоторые места, где можно было бы достичь большей наглядности, что способствовало бы лучшему усвоению материала учащимися. В частности, например, при доказательстве теоремы 1.3 об изоморфно-полных классах используются построения, многие из них стоило бы пояснить с помощью рисунка-схемы, как это делается во многих учебниках по теории графов (Зыков, Харари и др.). Но, повторюсь, этот и некоторые другие недостатки достаточно мелкие и не умаляют достоинств Записок. Надеюсь, И. Пономаренко не будет в претензии, если я перескажу здесь одно место из личной переписки с ним в отношении моей статьи: после беглого просмотра, он предположил, что мой подход является модификацией некоторых ранее предложенных, при этом он не учел, что те подходы основаны на канонической нумерации вершин графа, а мой нет. (Ведь не факт, что поиск канонической нумерации не более трудоемкий, чем сравнение графов на изоморфизм.)

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

В переводе на язык математики это должно звучать примерно так

Не понял, чем предложенный перевод "математичнее" моего оригинала? ИМХО замечание по форме не корректно. На остальное отвечу позже, но как и ранее в этой теме: пока я думаю над ответом, можете не дожидаясь его добавлять сюда новые замечания.

[whitefox]

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

Не понял, чем предложенный перевод "математичнее" моего оригинала?

В оригинале используется "possible mapping", а правильнее будет "some isomorphism".

-- 18 июн 2012, 18:33 --

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

ИМХО замечание по форме не корректно.

Это только Ваше ИМХО.
Тем не менее, раз Вы сочли форму замечания не корректной, приношу свои извинения.

-- 18 июн 2012, 19:03 --

(Оффтоп)

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

Некоторые принципиальные соображения в отношении работ указанных авторов были высказаны в моей статье (совместно с Е.А.Смоленским), опубликованной в Известиях РАН в 2005 г. (ссылка на которую приведена в абстракте).

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

[bin]

whitefox

(Оффтоп)

Я не в праве массово распространять статью, но пришлите мне Ваше "мыло" на ЛС