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

[bin]

sup в сообщении #787428 писал(а):

Ну в самом деле пусть даны два комплекта попарно изоморфных подграфов

Речь должна идти о полных комплектах (выше Вы отметили, что мы "вынуждены перебирать все возможные "корни"") и, если я правильно понял, то вершины 1,2,3 и 10,11,12,13 - черные. Но очевидно, что первый комплект не полон, т.к. нет $\delta$-графа с ребрами 1,2 и со стартовой вершиной 1. Второй комплект не полон, т.к. из него получается несвязный граф, а мы рассматриваем только связные. Т.о. в данном примере Вы взяли неполные комплекты графов, от которых результат мало зависит. И что же Вы хотите получить? С тем же успехом можно опровергать утверждение, что матрица смежности однозначно задает граф - выделим случайным образом в этой матрице не слишком большие блоки, а остальные элементы заменим символами "?", и однозначность исчезнет. Не все $\delta$-графы одинаково важны для результата, но и в матрице смежности для неориентированных графов важна только часть, лежащая выше главной диагонали. Есть некоторая избыточность, но это не страшно.

Как вариант для большей наглядности, можем рассмотреть аналогичные операции с матрицей смежности. Для этого матрицу смежности $A$ изначального графа дополним заголовками - нулевым столбцом и нулевой строкой (как обычно оформляют таблицы), в которые запишем номера вершин. Далее проводим декомпозиции и выписываем каждый $\delta$-граф в отдельную матрицу с заголовками. Например, граф $\Delta'_1$ из Вашего примера:

$\begin{tabular}{|c|c|c|} \hline & 10 & 11\tabularnewline \hline 10 & 0 & 1\tabularnewline \hline 11 & 1 & 0\tabularnewline \hline \end{tabular}$

В результате всех декомпозиций получаем полный комплект $\delta$-графов. Далее берем матрицу того же размера, что и матрица $A$, с теми же заголовками, у которой остальные элементы нули. И "объединяем" в нее матрицы $\delta$-графов с помощью операции логического "ИЛИ", руководствуясь заголовками. Получим матрицу $A$.

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

[sup]

Мой пример был лишь иллюстрацией проблемы: изоморфизм размеченных подграфов сам по себе не способен обеспечить изоморфизм исходных графов. Нужны дополнительные соображения. Пусть у меня есть некие комплекты попарно изоморфных графов. Начинаем по этим комплектам восстанавливать исходные графы.
Рассматриваем первый комплект. Берем первый подграф. Добавляем второй. Если есть общие вершины - склеиваем. Добавляем третий - склеиваем и тд. В конце концов получим граф $G$.
Рассматриваем второй комплект и его первый подграф. Добавляем второй. Если есть общие вершины - склеиваем. Добавляем третий - склеиваем и тд. В конце концов получим граф $G'$.
Вы утверждаете, что получатся изоморфные графы. Ну может быть, не знаю. Но вот вопрос, а в процессе параллельной склейки, когда одновременно брали подграфы из $G$ и из $G'$ и подклеивали к предыдущим, были ли промежуточные результаты изоморфными? У меня возникли сомнения, поскольку склейка идет по номерам вершин, а изоморфность подграфов нумерацию игнорирует, опираясь только на разметку. Чтобы сделать это сомнение нагляднее я и показал пример с двумя ребрами (это лишь иллюстрация, а не контрпример). В одном случае есть общая вершина (номер 1), а во втором нет. Результаты склейки получаются разными. Можно нарисовать и более сложные примеры деревьев, но проблема та же самая. При последовательной склейке промежуточные результаты могут быть не изоморфны. Поэтому надо либо доказывать, что такого не будет, либо, минуя промежуточные результаты, доказывать, что окончательный результат будет один и тот же. Ни то ни другое не выглядит простым.
Даже в простом примере Вам потребовались некие рассуждения, поясняющие что такая ситуация невозможна. Все это и означает: Ваше утверждение ни в коем случае нельзя считать самоочевидным или тривиальным. Требуется "серьёзное" доказательство.
Насчет спешки. Я никуда не тороплюсь. Предлагаю
1. Сформулировать индукционное утверждение. Выше я высказал предположение, как оно может выглядеть, но, возможно, я ошибаюсь.
2. Прямо "руками" показать переход от $i=1$ к $i=2$.
3. Если все пройдет "гладко", проделать общий индукционный переход от $i=k$ к $i=k+1$.
Обращаю Ваше внимание, что до сих пор Вы нигде не ссылались ни на какие конкретные свойства разметки. А ведь это верный признак, того, что она и вовсе не нужна. Подозрительно, не так ли?

[bin]

sup в сообщении #787780 писал(а):

Насчет спешки. Я никуда не тороплюсь.

Ok! Поэтому, прежде чем формулировать индукционное утверждение, давайте подробнее поговорим о втором варианте доказательства на языке матричной алгебры, которое Вы никак не откомментировали. Ниже я его немного переделал. Итак, изначально Вы задали вопрос:

sup в сообщении #781900 писал(а):

В лемме 9 заявлено "$f(M)$ однозначно задает $G_B$", но доказательство отсутствует. А именно. Не показано, что разные $G_B$ непременно дают разные $f(M)$. В сущности, это и есть самый главный вопрос. Как показать, что по набору инвариантов граф восстанавливается однозначно.

Вариант 2.Пусть $n\times n$ матрица $A$ - матрица смежности графа $G_B$. Получим с помощью декомпозиций все $\delta$-графы. Запишем "расширенные" матрицы смежности этих $\delta$-графов, как делали в Лемме 6 с другими графами. Т.е. для $\delta$-графа $\Delta_i$ в матрице $A$ заменяем все единички, соответствующие ребрам, которые не входят в $\Delta_i$ нулями. Полученную матрицу обозначим $A_i$.

Такая матрица соответствует графу, полученному из $\Delta_i$ добавлением всех вершин, не входящих в $\Delta_i$, но входящих в $G_B$. (Или, что то же самое: соответствует графу, полученному из $G_B$ удалением всех ребер, не входящих в $\Delta_i$). Степень каждой добавленной вершины будет нулевой, и как было отмечено при доказательстве Леммы 6: если графы изоморфны, то и соответствующие им графы с раширенными матрицами будут изоморфны, добавление одинакового количества изолированных вершин к каждому графу не нарушает смежность. Дополнительные корни в $A_i$ отсутствуют и т.о. игнорируются.

А теперь, поэлементно проделав операцию "ИЛИ" над всеми матрицами $A_i$, получим: $\underset{(i)}{\bigvee}A_{i}=A$. Т.е. если в каком-либо $\delta$-графе есть ребро $(j,k)$, то и в графе $\underset{(i)}{\bigvee}A_{i}$ будет это ребро, и наоборот, если во всех $\delta$-графах отсутствует ребро $(j,k)$, то в графе $\underset{(i)}{\bigvee}A_{i}$ его не будет. Матрица $A$ однозначно задает граф $G_B$, значит и $\underset{(i)}{\bigvee}A_{i}$, т.е. набор всех $\delta$-графов, однозначно задает $G_B$. Что и требовалось доказать.

[sup]

Ну что-ж, Вы в очередной раз показали, что граф можно восстановить. Но ведь в этом никто и не сомневался. А в чем проблема? А вот в чем.
Давайте возьмем все эти матрицы $A_i$, и произвольно переставим в них строки и столбцы (эквивалентно некой перенумерации вершин). В каждой матрице своим образом. Получим комплект матриц $A'_i$. Вот с этим-то комплектом и надо работать. Для этого комплекта и надо доказывать, что либо он несовместный, либо из него получается матрица, эквивалентная $A$.
Ну в самом деле. Пусть у нас есть два комплекта попарно-изоморфных подграфов. Тогда из матрицы $A_i$ некой перестановкой столбцов и строк получается $A'_i$. Мы не можем требовать чтобы для всех матриц эта перестановка была одна и та же. (Это значительно более сильное утверждение, нежели чем просто попарный изоморфизм). Обратно, совместность набора $A'_i$ в точности означает, что его можно получить из некой матрицы $A'$. При этом на языке графов получится комплект подграфов, эквивалентный оригинальному комплекту.

[bin]

sup в сообщении #787963 писал(а):

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

А я и говорил, что это выглядит очевидным

sup в сообщении #787963 писал(а):

Давайте возьмем все эти матрицы $A_i$, и произвольно переставим в них строки и столбцы (эквивалентно некой перенумерации вершин). В каждой матрице своим образом. Получим комплект матриц $A'_i$. Вот с этим-то комплектом и надо работать.

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

sup в сообщении #787963 писал(а):

Для этого комплекта и надо доказывать, что либо он несовместный, либо из него получается матрица, эквивалентная $A$.

...либо из него получается матрица, не эквивалентная $A$.

sup в сообщении #787963 писал(а):

Ну в самом деле. Пусть у нас есть два комплекта попарно-изоморфных подграфов.

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

[sup]

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

Я доказал ровно то, что утверждается в лемме 9, и не больше

Боюсь, что Вы этого не доказали. Но тут может возникнуть некоторое непонимание друг друга.
Поскольку в процессе переписки возникали разные вопросы, то теперь уже трудно понять, с каким вопросом мы сейчас разбираемся. Вернусь к началу.
В лемме 9 утверждается, что $f(M)$ однозначно задает $G$. Ранее Вы утверждали, что это вытекает из попарного изоморфизма $\Delta_i \cong \Delta'_i$. Вот это сообщение.

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

Предположим, что граф $G_{B}$ не изоморфен графу $G_{B}^{\prime}$, но при этом $f(M)=f(M^{\prime})$. Из $f(M)=f(M^{\prime})$ следует, что для каждого графа $\Delta_{i}\in M$ найдется такой граф $\Delta_{j}^{\prime}\in M^{\prime}$, что $\Delta_{i}\cong\Delta_{j}^{\prime}$. Отсюда $\underset{(i)}{\bigcup}\Delta_{i}\cong\underset{(i)}{\bigcup}\Delta_{i}^{\prime}$.

Я просил Вас показать откуда следует этот последний изоморфизм. Вы сначала ссылались на возможность индукции, а потом предъявили некий вариант 2. Про индукцию мы уже "забыли". Вариант 2 выглядит некоторым экспромтом (то ли это готовый текст, то ли набросок). Поэтому хотелось бы, чтобы Вы четко показали некий текст, в котором устанавливается изоморфизм $G$ и $G'$, исходя из попарного изоморфизма $\Delta_i \cong \Delta'_i$.
Если Вы считаете, что "вариант 2" является требуемым доказательством, то вынужден Вас огорчить. Это не так. Там фигурирует слишком много расплывчатых выражений. Например, я уже убедился, что мы по разному понимаем фразу "однозначно задает". Посему, чтобы не тонуть в попытках понять, что означает та или иная фраза, я предлагаю прямо предъявить соответствие вершин графа $G$ вершинам $G'$. Не разговоры, что это можно сделать, а прямо процедуру. Вот например, для графов $\Delta_1$ и $\Delta'_1$ я это сделать могу. Поскольку эти графы изоморфны, то существует отображение вершин $\varphi : V(\Delta_1) \to V'(\Delta'_1)$ такое, что $u,v \in V(\Delta_1)$ - инцидентны если и только если $\varphi (u), \varphi (v)$ инцидентны. Но вот дальше я не понимаю как Вы намерены действовать. То ли Вы будете продолжать это отображение на все множество вершин $V(G)$, то ли будете как-то его модифицировать. Скорее всего, Вы примените индукцию, но я не знаю как. Вот отсюда и моя просьба. Покажите как строится это отображение.
Коль скоро Вы построите это отображение и докажите изоморфизм, лемма 9 будет доказана. В противном случае - нет.

[bin]

sup в сообщении #788868 писал(а):

я уже убедился, что мы по разному понимаем фразу "однозначно задает".

Ключ к пониманию есть у Харари:

Цитата:

Матрица смежностей [...] существует взаимно однозначное соответствие между помеченными графами с $p$ вершинами и симметрическими бинарными $(p\times p)$ матрицами с нулями на диагонали. [...] Если $A_{1}$ и $A_{2}$ — матрицы смежностей, соответствующие различным нумерациям одного и того же графа $G$, то $A_{1}=P^{-1}A_{2}P$ для некоторой матрицы перестановки $P$. C.178-179

Обратное также верно: если $A_{1}=P^{-1}A_{2}P$, то $A_{1}$ и $A_{2}$ — матрицы смежности, соответствующие различным нумерациям одного и того же графа. Вместо «одного и того же графа» можно говорить о двух копиях одного и того же графа, т.е. о двух изоморфных графах с разной нумерацией вершин. При этом $A_{1}$ и $A_{2}$ могут быть неравны, и, соответственно, графы не равны, но изоморфны. Не существует двух неизоморфных графов, матрицы смежности которых удовлетворяют $A_{1}=P^{-1}A_{2}P$. Как же иначе можно понять утверждение о том, что матрица смежности однозначно задает граф?

Но если очень хочется, давайте возьмем два графа $G$ и $G'$, и модифицируем Вариант 2.

Вариант 2.2.Пусть $n\times n$ матрица $A$ - матрица смежности графа $G_B$. Получим с помощью декомпозиций все $\delta$-графы. Запишем "расширенные" матрицы смежности этих $\delta$-графов, как делали в Лемме 6 с другими графами. Т.е. для $\delta$-графа $\Delta_i$ в матрице $A$ заменяем все единички, соответствующие ребрам, которые не входят в $\Delta_i$ нулями. Полученную матрицу обозначим $A_i$.

Такая матрица соответствует графу, полученному из $\Delta_i$ добавлением всех вершин, не входящих в $\Delta_i$, но входящих в $G_B$. (Или, что то же самое: соответствует графу, полученному из $G_B$ удалением всех ребер, не входящих в $\Delta_i$). Степень каждой добавленной вершины будет нулевой, и как было отмечено при доказательстве Леммы 6: если графы изоморфны, то и соответствующие им графы с раширенными матрицами будут изоморфны, добавление одинакового количества изолированных вершин к каждому графу не нарушает смежность. Дополнительные корни в $A_i$ отсутствуют и т.о. игнорируются.

А теперь, поэлементно проделав операцию "ИЛИ" над всеми матрицами $A_i$, получим: $\underset{(i)}{\bigvee}A_{i}=A$. Т.е. если в каком-либо $\delta$-графе есть ребро $(j,k)$, то и в графе $\underset{(i)}{\bigvee}A_{i}$ будет это ребро, и наоборот, если во всех $\delta$-графах отсутствует ребро $(j,k)$, то в графе $\underset{(i)}{\bigvee}A_{i}$ его не будет.

Все то же самое проделаем и с графом $G'$. Получим матрицы $A'_i$. Если для какой-то перестановки $P$ и для каждой матрицы $A_i$, найдется такая матрица $A'_j$, что $A_i=P^{-1}A'_{j}P$ ($P$ во всех случаях одна и та же), то $A=\underset{(i)}{\bigvee}A_{i}=\underset{(i)}{\bigvee}(P^{-1}A'_{i}P)=P^{-1}(\underset{(i)}{\bigvee}A'_{i})P=P^{-1}A'P$, и графы $G$, $G'$ изоморфны по определению изоморфизма $A=P^{-1}A'P$. Если же для какой-то матрицы $A_i$ все матрицы $A'_j$ такие, что $A_i \neq P^{-1}A'_{j}P$, то $A \neq P^{-1}A'P$, и графы $G$, $G'$ не изоморфны по тому же определению изоморфизма. Т.о. графы $G$, $G'$ изоморфны тогда и только тогда, когда для каждой матрицы $A_i$, найдется такая матрица $A'_j$, что $A_i=P^{-1}A'_{j}P$. Конец доказательства.

-- Сб ноя 16, 2013 09:48:14 --

sup в сообщении #788868 писал(а):

я предлагаю прямо предъявить соответствие вершин графа $G$ вершинам $G'$

Я предлагаю алгоритм, который только отвечает на вопрос "изоморфны?" - Да/нет. Но он не устанавливает возможных соответствий. Допускаю, что поиск какого-либо конкретного изоморфизма может оказаться неполиномиальной задачей.

[sup]

Когда я говорил про соответствие вершин, я не имел в виду конструктивный полиномиальный алгоритм. Достаточно любой доказательной конструкции. Почему? Потому, что речь шла просто о доказательстве изоморфизма $\bigcup \Delta_i \cong \bigcup \Delta'_i$, а не полиномиальном алгоритме. Ваш алгоритм проверки графов полиномиальный, а мы обсуждаем доказательство его корректности. Которое, в свою очередь, может использовать решительно любые построения. Хоть полиномиальные хоть нет.
Теперь о варианте 2 и его модификациях. Я вынужден разъяснить свою позицию.
Коль скоро речь идет о строгом доказательстве, то должен быть некий конкретный текст, в котором сформулировано утверждение и далее приведено полное доказательное рассуждение. Этот текст можно обсуждать. Иначе это просто некий "обмен мнениями" - можно так действовать или нельзя, верное тут рассуждение или в нем есть ошибки и тд.
В этом контексте давайте рассмотрим Ваши "варианты 2 & 2.2". Чтобы их обсуждать, нужно конкретное утверждение. ЧТО МЫ ДОКАЗЫВАЕМ? Лемму 9? Или $\bigcup \Delta_i \cong \bigcup \Delta'_i$, или то, что из одного следует другое? Что дано и что надо доказать?
Почему я на этом акцентирую внимание? Потому, что мы должны четко понимать посылку, из которой будем делать выводы. А я вот уже не уверен, что дано, а что надо доказать.
Вот Вы пишете

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

Если для какой-то перестановки $P$ и для каждой матрицы $A_i$, найдется такая матрица $A'_j$, что $A_i=P^{-1}A'_{j}P$ ($P$ во всех случаях одна и та же)

Это что дано? Или некое предположение? По-видимому Вы так трактуете условие попарного изоморфизма $\Delta_i \cong \Delta'_i$.
Так вот, с этим я решительно не согласен. Попарный изоморфизм НЕ предполагает, что матрица $P$ одна и та же для разных пар $\Delta_i$, $\Delta'_i$. Если же Вы намерены этим фактом пользоваться, то это не согласуется с условием леммы 9. В лемме 9 фигурирует лишь набор кортежей. Но из равенства кортежей равенство всех матриц $P_i$ никак не следует. Хотя бы уже по той причине, что в некоторых случаях она определяется не однозначно. В любом случае, никаких доказательств на этот счет у Вас нет.
Как следствие, мы переливаем из пустого в порожнее. Это доп. предположение делает все утверждение тривиальным. Но ведь я-то исходил совсем из другой формулировки.

[bin]

Цитирую статью:

Цитата:

Лемма 9. Пусть в результате всех декомпозиций $D_ {\beta} (t_{i}), t_{i}\in V, i=1,2,...,n$ $B$-графа $G_{B}$ получено множество $\delta$-графов $M=\{\Delta_{1}, \Delta_{2},...\}$, тогда $(\underset{(j)}{\bigcup}\Delta_{j})\cap G_{B}=G_{B}$ и $f(M)$ однозначно задает $G_{B}$. $\square$
Доказательство. Для синих и красных ребер каждый $\delta$-граф совпадает с $\gamma$-графом, из которого он был получен, поэтому справедливость доказываемого утверждения для этих ребер следует из леммы 7. Рассмотрим зеленые ребра. Пусть в результате $D_{\beta}(h)$ образовалось зеленое дерево с черными листьями $i,j\in V$ на уровне $d$ и оранжевым корнем $k\in U$ на уровне $d+1$. Т.о. ребра $(i,k)$ и $(k,j)$ не войдут в соответствующие уровню $d$ $\delta$-графы. Предположим, что эти ребра не войдут в $\delta$-графы и для других стартовых вершин. Возьмем $i$ в качестве стартовой вершины. Тогда в результате $D_{\beta}(i)$ вершина $i$ окажется на уровне 0, вершина $k$ окажется на уровне 1, а вершина $j$ окажется на уровне 2, и ребро $(i,k)$ будет раскрашено красным, а ребро $(k,j)$ синим. Эти ребра войдут в соответствующий $\delta$-граф. Следовательно, наше предположение неверно.

Пусть граф $G_{B}$ изоморфен графу $G_{B}^{\prime}$. Из леммы 4 следует, что при любой декомпозиции $D_{\beta}(t_{i}), t_{i}\in V, i=1,2,...,n$ найдется такая декомпозиция $D_{\beta}(t^{\prime}), t^{\prime}\in V^{\prime}$, что число уровней будет одинаковым, и $\beta$-деревья одного уровня будут изоморфны. Учитывая вывод 4 и лемму 8 видим, что $f(M)=f(M^{\prime})$, где $M^{\prime}$-- множество всех $\delta$-графов графа $G_{B}^{\prime}$.

(Продолжение доказательства).Пусть $n\times n$ матрица $A$ - матрица смежности графа $G_B$. Получим с помощью декомпозиций все $\delta$-графы. Запишем "расширенные" матрицы смежности этих $\delta$-графов, как делали в Лемме 6 с другими графами. Т.е. для $\delta$-графа $\Delta_i$ в матрице $A$ заменяем все единички, соответствующие ребрам, которые не входят в $\Delta_i$ нулями. Полученную матрицу обозначим $A_i$.

Такая матрица соответствует графу, полученному из $\Delta_i$ добавлением всех вершин, не входящих в $\Delta_i$, но входящих в $G_B$. (Или, что то же самое: соответствует графу, полученному из $G_B$ удалением всех ребер, не входящих в $\Delta_i$). Степень каждой добавленной вершины будет нулевой, и как было отмечено при доказательстве Леммы 6: если графы изоморфны, то и соответствующие им графы с раширенными матрицами будут изоморфны, добавление одинакового количества изолированных вершин к каждому графу не нарушает смежность. Дополнительные корни в $A_i$ отсутствуют и т.о. игнорируются.

А теперь, поэлементно проделав операцию "ИЛИ" над всеми матрицами $A_i$, получим: $\underset{(i)}{\bigvee}A_{i}=A$. Т.е. если в каком-либо $\delta$-графе есть ребро $(j,k)$, то и в графе $\underset{(i)}{\bigvee}A_{i}$ будет это ребро, и наоборот, если во всех $\delta$-графах отсутствует ребро $(j,k)$, то в графе $\underset{(i)}{\bigvee}A_{i}$ его не будет.

Все то же самое проделаем и с графом $G_B'$. Получим матрицы $A'_i$. Рассмотрим два возможных случая.

Случай 1. Если для какой-то перестановки $P$ и для каждой матрицы $A_i$, найдется такая матрица $A'_j$, что $A_i=P^{-1}A'_{j}P$ ($P$ во всех случаях одна и та же), то $A=\underset{(i)}{\bigvee}A_{i}=\underset{(i)}{\bigvee}(P^{-1}A'_{i}P)=P^{-1}(\underset{(i)}{\bigvee}A'_{i})P=P^{-1}A'P$, и графы $G_B$, $G'_B$ изоморфны по определению изоморфизма $A=P^{-1}A'P$.

Случай 2. Если же для какой-то матрицы $A_i$ и для каждой из возможных перестановок $P$ все матрицы $A'_j$ такие, что $A_i \neq P^{-1}A'_{j}P$, то $A \neq P^{-1}A'P$, и графы $G_B$, $G'_B$ не изоморфны по тому же определению изоморфизма.

Т.о. графы $G_B$, $G'_B$ изоморфны тогда и только тогда, когда для каждой матрицы $A_i$, найдется такая матрица $A'_j$, что $A_i=P^{-1}A'_{j}P$, т.е. $f(M)=f(M^{\prime})$. $\square$

Я все еще не уверен, что нужно два графа в "продолжении доказательства", а не один, как в варианте 2. Поэтому переспрошу еще раз:

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

Как же иначе можно понять утверждение о том, что матрица смежности однозначно задает граф?

[sup]

Ну вот, есть текст - можно обсуждать. Спасибо.
Матрица смежности, разумеется, однозначно задает граф. У Вас нет доказательства того, что у графов эквивалентные матрицы смежности.
Вот и сейчас, в данном доказательстве пропущен (на мой взгляд самый главный)
Случай 3. Для всякого $i$
$A_ i = P^{-1}_iA'_iP_i$
и все $P_i$ разные. Ну или некоторые могут совпадать, но некоторые все же разные.
(Возможно, это как-то отражено в вашем "случае 2". Я засомневался, правильно ли я понял определение этого случая.)
Вот это главный вопрос. Пусть выполнен случай 3. Что для него можно сказать? Мне кажется, что этот случай у Вас не разобран.
И еще один вопрос. В Вашем тексте не упоминается разметка графа. Все рассуждения идут лишь в терминах матриц смежности. Значит ли это, что в лемме 9 разметка (кортежирование) не нужна, и она (лемма) справедлива и для "обычных" графов?

[bin]

sup в сообщении #789941 писал(а):

Матрица смежности, разумеется, однозначно задает граф.

Ok. Значит, мы договорились, что одинаково понимаем эту фразу (иначе ее просто понять невозможно). Случай 3, о котором Вы спрашиваете, в моем доказательстве относится к случаю 2: нас не интересуют перестановки, которые лишь частично удовлетворяют случаю 1, т.е. какие-то $A_i$ получаются с помощью такой перестановки, а другие матрицы нет. Два случая достаточно, как в программировании простой условный оператор if-then-else:

if x=0 then write ('input error') else y:=1/x;

О разметке: уже в формулировке леммы присутствует разметка в виде $f(M)$, декомпозиция - тоже разметка, матрица смежности задает разметку, т.е. порядок следования строк (столбцов) и т.д.

[sup]

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

Случай 3, о котором Вы спрашиваете, в моем доказательстве относится к случаю 2: нас не интересуют перестановки, которые лишь частично удовлетворяют случаю 1, т.е. какие-то $A_i$ получаются с помощью такой перестановки, а другие матрицы нет. Два случая достаточно, как в программировании простой условный оператор if-then-else:

if x=0 then write ('input error') else y:=1/x;

Здесь не понял. Что значит не интересуют? Я взял матрицы $A_i$ и $A'_i$. Нашел, что $A_i = P_i^{-1}A'_iP_i$ и не все $P_i$ равны между собой. И что мне теперь делать? Искать одну и ту же $P$, или объявлять что изоморфизма нет, или выдавать сообщение об ошибке? А если буду искать и не найду? Тогда что делать?

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

О разметке: уже в формулировке леммы присутствует разметка в виде $f(M)$, декомпозиция - тоже разметка, и т.д.

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

[bin]

Согласен, что формулировку случая 2 нужно изменить. Например, так: "Случай 2. Остальные случаи, не попадающие под случай 1".

sup в сообщении #790012 писал(а):

Будем использовать "простые" кортежи деревьев (как в доказательстве изоморфизма деревьев), полученных при декомпозиции. После этого применим Ваше доказательство. Получим все то же самое. Это верно?

Нет. У меня не "простые" кортежи деревьев, а пары кортежей (см. определение функции $f$). Для кортежей, неупорядоченных в пары с учетом раскраски, не будет выполняться лемма 8.

[sup]

Так, с кортежами у меня еще возможно будут вопросы, но позже. А сейчас надо разобраться с более важной проблемой.

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

Случай 1. Если для какой-то перестановки $P$ и для каждой матрицы $A_i$, найдется такая матрица $A'_j$, что $A_i=P^{-1}A'_{j}P$ ($P$ во всех случаях одна и та же)
Случай 2. Если же для какой-то матрицы $A_i$ и для каждой из возможных перестановок $P$ все матрицы $A'_j$ такие, что $A_i \neq P^{-1}A'_{j}P$

Формулировку 2-го случая надо бы изменить. Например, случай 2 - это если такая матрица не найдется (или что-то в этом роде). В принципе, ничего страшного в этом нет. Но вот какая проблема. Как мы узнаем есть такая матрица или нет?
Что нам дано? Два совпадающих набора кортежей. Чтобы узнать, что такая матрица $P$ не найдется, придется перебрать ВСЕ возможные варианты реализации попарных изоморфизмов между $A_i$ и $A'_j$. Где гарантия, что количество этих вариантов полиномиально зависит от размера задачи?
Или же надо доказывать, что для двух комплектов равных кортежей такая матрица ВСЕГДА найдется. Тогда нужно доказательство.

[bin]

sup в сообщении #790114 писал(а):

Чтобы узнать, что такая матрица $P$ не найдется, придется перебрать ВСЕ возможные варианты реализации попарных изоморфизмов между $A_i$ и $A'_j$. Где гарантия, что количество этих вариантов полиномиально зависит от размера задачи?

Отвечу Вашими словами:

sup в сообщении #789345 писал(а):

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

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