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

[sup]

Этот "фокус" пройдет, если Вы как-нибудь докажите, что такая матрица существует. Для ее предъявления может понадобится перебор. Но для фиксации самого факта изоморфизма она не нужна.
Но если такая матрица не существует? Еще раз повторю. Нам даны два комплекта совпадающих кортежей. Изоморфны ли графы? Какие могут быть ответы.
1. Всегда Да.
2. Иногда Да, иногда Нет.
3. Всегда Нет.
Вариант 3 не проходит. Мы могли бы изучать две копии одного и того же графа. Остаются варианты 1 и 2.

Вариант 1 хорош тем, что никакого выбора то и нет. Ничего перебирать не надо. Ну подумаешь, мы не можем явно предъявить эту матрицу. Главное, что она существует. Однако есть и ложка дегтя: это надо как-то доказать.

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

Вот отсюда и выбор. Либо доказательство (любое), что всегда реализуется вариант 1, либо допускаем, что иногда бывает и вариант 2, корректируем формулировку и доказываем, что в этом случае потребуются доп. усилия не более чем полиномиальной сложности.

[bin]

Не понял. Для неизоморфных графов матрица $P$ не существует по определению изоморфизма, для изоморфных графов она всегда существует по тому же определению. По меньшей мере всегда возможно тождественное отображение графа на себя. Для ассиметрических графов это единственный автоморфизм, т.о. для них возможна только одна матрица $P$. Этот факт отмечает Харари на С. 190.

Далее, я опять не понял. В формулировке леммы 9 не присутствует каких-либо утверждений о вычислительной сложности. Более того, лемма 9 не предлагает какого-либо практического алгоритма. Там исключительно умозрительные построения, использующие декомпозицию графа. Имеем полное право удалить из статьи Алгоритм 1 (т.к. в лемме 9 и в предыдущих леммах он не используется), переименовать лемму 9 в Теорему, поставить жирную точку и на этом закончить статью. Заголовок статьи тогда нужен иной, например, "Одно свойство декомпозиции графов". (Заинтересует ли кого такая статья - это уже другой вопрос). Конечно же, мы собираемся применить лемму 9 для доказательства корректности алгоритма 1, но это мы будем делать в дальнейшем, пока об этом речи нет. Вы же, как мне видится, забегаете вперед, настаивая на доказательстве более сильных утверждений, чем те, что сформулированы в лемме 9. Зачем доказывать более сильное утверждение, чем то, которое приведено в "дано"?

Выше мы договорились, что одинаково понимаем фразу "Матрица смежности однозначно задает граф". Теперь Вы сказали:

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

Ибо в таком случае набор кортежей не однозначно задает граф.

Но в варианте 2 уже было показано, что

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

Из матриц смежности подграфов однозначно восстанавливается матрица смежности графа. А матрица смежности однозначно задает граф.

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

[sup]

Я опять свернул с "формального языка" на "неформальный" и опять напрасно.
Выскажусь формально.

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

Лемма 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$

...
...

Случай 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$
.

Я уже говорил, что такая формулировка случая 2 мне кажется несколько двусмысленной. Я ее понимаю так:
Случай 2*. Такая матрица (перестановка) $P$ не найдется.
Я в Вашем тексте выделил фразы, где, как мне кажется, об этом говорится прямым текстом.
Но тогда в этом случае графы $G$ и $G'$ НЕ изоморфны. Но ведь все кортежи совпадают. Посылка леммы выполнена, а изоморфизма нет. Значит утверждение леммы НЕ справедливо.
Таким образом, для справедливости леммы как раз и требуется доказать, что случай 2 невозможен или, другими словами, требуемая перстановка ВСЕГДА найдется.
Может я что-то не так понимаю?

[bin]

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

Может я что-то не так понимаю?

Вы не учитываете, что подграфы от каждой декомпозиции имеют общие вершины, но не имеют общих ребер. (Эта ситуация для двух подграфов рассмотрена в лемме 6). Для изолированных вершин, которые мы добавляем, подходит любая перестановка. Таким образом, перестановка, подходящая для одного подграфа, подойдет и для другого, полученного при одной и той же декомпозиции (одной и той же стартовой вершине). (Если сказать неформально, но наглядно, то мы "соединяем" матрицы перестановок каждого подграфа в одну большую матрицу перестановки для всего графа. Иными словами, при перестановке подграфа местами могут меняться не каждый столбец и не каждая строка с каждым другим столбцом (строкой) матрицы смежности, а только со столбцами и строками парного подграфа. Когда мы рассматриваем два графа, мы используем не только "расширенные" матрицы смежности, но и "расширенные" матрицы перестановок для них.)

Но я продолжаю думать, что Вариант 2 оптимальнее Варианта 2.3. Обращу также Ваше внимание, что Вы процитировали не последнюю версию 2.3. Выше я сказал:

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

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

[sup]

Вынужден повторить свое замечание.
В лемме 9 вы утверждаете, что $f(M)$ однозначно задает $G_B$. По моим понятиям это означает, что из равенства $f(M) = f(M')$ следует, что $G \cong G'$
Однако случай 2 противоречит утверждению леммы 9.
Повторю Ваше доказательство своими словами.
Пусть $f(M) = f(M')$. По определению, $f(M)$, равно как и $f(M')$ - это наборы кортежей дельта-графов $\Delta_i$(если не напутал в названии). В силу равенства $f(M) = f(M')$ каждому $\Delta_i$ поставим в соответствие $\Delta'_i$. При этом, разумеется, $\Delta_i \cong \Delta'_i$. "Расширенные" матрицы смежности этих графов Вы обозначили как $A_i$ и $A'_i$. Коль скоро $\Delta_i \cong \Delta'_i$, для некоторой перестановки с матрицей $P_i$ имеем $A_i = P_i^{-1}A'_iP_i$.
Чтобы не "мутить воду" сразу же скажу, что в наборе $f(M)$ могут быть одинаковые кортежи, а значит соответствие $A_i \to A'_i$ можно определить разными способами. Кроме того, граф $\Delta_i$ может иметь нетривиальные автоморфизмы и, следовательно, матрицы $P_i$ определены НЕ однозначно.
Поэтому теоретически, возможны два случая.
Случай 1. Найдется такое соответствие $A_i \to A'_i$, что все эти матрицы $P_i$ совпадают. Т.е. найдется матрица $P$ такая, что $A_i = P^{-1}A'_iP$ для всех $i$. В этом случае можно показать, что $A = P^{-1}A'P$. Что означает, что $G \cong G'$. Здесь все "хорошо".
Случай 2. (все, что "не попало в случай 1") Для любого соответствия $A_i \to A'_i$ если $A_i = P_i^{-1}A'_iP_i$, то среди $P_i$ есть различные.
Ранее, в случае 2 Вы просто заявили, что $G$ не изоморфен $G'$.
Ну и как это называется? Доказываем, что графы изоморфны и вдруг такое заявление. Само по себе это заявление абсолютно верно, но как же быть с утверждением леммы ???
Если Вы утверждаете, что лемма верна, докажите, что случай 2 никогда не возникнет. Иначе такое "доказательство" просто абсурдно.

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

[bin]

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

я прошу Вас вновь предъявить формальный текст, который можно обсуждать.

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

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

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

Цитата:

Лемма 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}$ его не будет.

Матрица $A$ однозначно задает $G_{B}$, и т.к. $\underset{(i)}{\bigvee}A_{i}=A$, то $\underset{(i)}{\bigvee}A_{i}$ однозначно задает $G_{B}$. Откуда следует, что $f(M)$ однозначно задает $G_{B}$. Конец доказательства.

Выше в предыдущих сообщениях я уже высказал мнение, что следует вернуться к доказательству 2 (2.1). Моя методологическая ошибка в данном обсуждении заключалась в том, что в ответ на Ваше пожелание использовать два графа я привел Вариант 2.2. По сути, Вы высказали сомнение без достаточного его обоснования. Я воспринял это сомнение как опровержение и стал его опровергать вместо того, чтобы сначала попросить у Вас предъявить строгое формальное доказательство Вашего опровержения. Бремя доказательства некого утверждения лежит на авторе этого утверждения. Здесь я привел формулировку и доказательство (2.1) леммы 9. Если Вы не согласны, то: 1) укажите на ошибку; 2) если хотите опровергать через "случай 3", то строго докажите, что такой случай возможен (Вы автор "случая 3" - Вам и доказывать). При этом (2) не исключает (1), иначе мы получаем парадокс.

[sup]

Ну что же. Значит мое понимание фразы "$f(M)$ однозначно задает $G$" было неправильно.
Я то думал, что равенство $f(M) = f(M')$ влечет за собой изоморфизм $G \cong G'$. А оказывается нет. Изоморфизм отсюда не следует. Вот уже и продвижение вперед.
Но "меня терзают смутные подозрения" $\copyright$.
Вы уверены, что такая лемма может принести какую-то пользу? Ведь тогда она говорит только о полном совпадении матриц. Никакая перестановка вершин уже невозможна. Я правильно понял?

-- Чт ноя 21, 2013 14:43:21 --

Я вот что подумал. Вы бы дали "четкое" определение, что Вы понимаете под фразой "$f(M)$ однозначно определяет граф $G$".
Я вот, например, уже свое понимание сформулировал. На всякий случай повторю.

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

По моим понятиям это означает, что из равенства $f(M) = f(M')$ следует, что $G \cong G'$

А что Вы подразумеваете под этой фразой?

[bin]

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

Никакая перестановка вершин уже невозможна.

Почему невозможна? Что изменится, если, например, первую вершину мы будем называть десятой, а десятую первой?

Про понимание фразы

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

"$f(M)$ однозначно определяет граф $G$".

- интересный вопрос. Например, можно сказать, что матрица расстояний однозначно определяет граф. Но как ответить на этот вопрос в случае матрицы расстояний? Думаю, что так: по матрице расстояний восстанавливается матрица смежности (все расстояния, не равные единице, обнуляем), точно так же из доказанной леммы следует, что по $A_i$ восстанавливается матрица смежности. По определению изоморфизма из $A=P^{-1}A'P$ следует $G \cong G'$. Таким образом, равенство $f(M) = f(M')$ влечет за собой изоморфизм $G \cong G'$.

[sup]

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

Таким образом, равенство $f(M) = f(M')$ влечет за собой изоморфизм $G \cong G'$.

Рад слышать, что мы с Вами одинаково понимаем это выражение.
В таком случае я не могу понять, как Вы смогли доказать изоморфизм $G \cong G'$ НИ РАЗУ не упомянув про $G'$.
Все что есть в вашем тексте, это некие манипуляции с матрицей $A$. Сначала Вы обнуляли часть единиц в этой матрице, получая матрицы $A_i$. Затем с помощью операции "ИЛИ" Вы обратно собрали эту матрицу. Все это замечательно. Но при чем тут граф $G'$. Признаться, я впервые вижу доказательство свойств объекта (граф $G'$), который и вовсе в доказательстве не упоминается.
Боюсь Вас огорчить, но этот текст ничего не доказывает. Точнее, первая часть - да, доказывает, что у изоморфных графов набор инвариантов совпадает. Но это тривиальное утверждение, не стоило на него и время тратить. А вот обратного у Вас нет.
Ваш текст НИГДЕ даже не упоминает условие $f(M) = f(M')$. Ладно, я и сам могу догадаться, что в начале должна быть магическая фраза
" Пусть $f(M) = f(M')$".
Но где Вы этим пользуетесь? Где $G'$? Где рассуждения, обосновывающие изоморфизм? Вы занимаетесь какой-то словесной эквилибристикой, пытаясь доказать изоморфизм ДВУХ графов, рассматривая ТОЛЬКО ОДНУ матрицу.
На всякий случай я Вам напомню, что доказать изоморфизм - это:
либо сослаться на некую теорему об изоморфизме, предварительно убедившись, что выполнены ее условия
либо предъявить отображение $\varphi: V(G) \to V(G')$ со свойством вершины $u,v \in V(G)$ инцидентны если и только если $\varphi (u),\varphi (v)$ инцидентны.
Ничего подобного у Вас я не вижу. Так что доказательства у Вас нет.

[bin]

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

Где рассуждения, обосновывающие изоморфизм? Вы занимаетесь какой-то словесной эквилибристикой, пытаясь доказать изоморфизм ДВУХ графов, рассматривая ТОЛЬКО ОДНУ матрицу.

Загляните, например, в Зыкова:

Цитата:

Оба эти кода [мини-код и макси-код - bin], очевидно, - инварианты, и, более того, по любому из них и количеству вершин легко восстанавливается одна из матриц смежностей графа, а значит, и сам граф (с точностью до изоморфизма).(С.33)

Далее на С.55-56 автор еще раз отмечает, что эти коды являются полными инвариантами. Но где в рассуждениях Зыкова ДВА графа? Он рассматривает ТОЛЬКО ОДНУ матрицу. Но ни Зыков, ни тем более я, в данном случае ничего нового не придумали - посмотрите другую литературу по инвариантам графов и Вы увидите, что это общепризнанный подход. Если Вы не слышали про этот подход, то незачем употреблять чисто эмоциональные оценки типа "словесная эквилибристика". Такие оценки угрожают понизить уровень нашего обсуждения с конструктивного до малосодержательного препирательства. Давайте будем избегать их, придерживаясь стиля, принятого в академических кругах.

[sup]

Мне незачем заглядывать в книгу Зыкова. Мне достаточно посмотреть на Ваш текст. Почему-то Зыков нашел необходимым хоть что-то сказать про коды, а вот Вы - нет. И, уж если на то пошло, Ваши коды однозначно определют все дельта-графы $\Delta_i$. С этим никто и не спорил. Вопрос идет об однозначном определении всего графа $G$. А на сей счет у Зыкова ничего не говорится.
Я Вас просил дать формальный текст. В том тексте, что Вы представили, после слов "продолжение доказательства" речь идет о каких-то действиях с матрицей $A$. Больше я не увидел ничего. В лучшем случае, Вы можете утверждать, что все то же самое можно проделать и с матрицей $A'$. Ну и что? Ну можно разобрать на части и снова собрать. Что из этого следует? Это можно сделать с любым графом, не важно изоморфен он $G$ или нет. Может быть у Вас есть еще какие-то соображения, но вот в тексте ничего нет. Догадываться, что Вы хотели сказать, но не сказали, я не могу. Посему я и дал оценку Вашему тексту. Это может быть что угодно, но не доказательство изоморфизма.
Впрочем, есть еще один вариант. Я недостаточно компетентен и не вижу весьма простые соображения, которые Вы не считаете нужным излагать (ввиду их очевидности). Ну что-ж, это возможно. Но ведь Вам тогда ничего не стоит просто расшифровать эту "очевидность". Например утверждения Зыкова о восстановлении матрицы смежности по мини-коду легко показать по индукции. Не просто сослаться на очевидность, а построить отображение вершин одного графа на вершины другого. Помнится, Вы по индукции и собирались доказывать свое утверждение, но потом почему-то передумали. Ну так за чем же дело встало. Покажите как Вы строите отображение вершин с помощью индукции и дело с концом. Казалось бы, ну в чем вопрос. Вы же заинтересованы в тщательной проверке Вашей работы. У Вас есть изоморфизм. Ну покажите его непосредственным рассуждением. Зачем ссылаться на то, что все "аналогично". Чем дольше Вы уклоняетесь от этой задачи, тем очевиднее становится, что Вы этого сделать НЕ МОЖЕТЕ. Изоморфизм есть, а перестановку предъявить не могу. Вот "така, панимашь, загогулина".
На мой взгляд это и означает, что идея алгоритма у Вас, вне всякого сомнения, есть. А вот серьёзной идеи, как доказать его корректность - нет.

[bin]

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

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

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

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

Изоморфизм есть, а перестановку предъявить не могу.

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

[sup]

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

Если бы это предположение подтвердилось

Это означает, что была бы доказана теорема, в которой было бы доказано существование такой перестановки. А это может быть только в двух случаях. Либо она была бы построена (хотя бы и не полиномиальным способом), либо ее существование было бы получено неконструктивным рассуждением от противного. Если Вы намекаете на то, что я не упомянул еще и такой вариант, то да, я был не вполне прав.
Вы все время подозреваете меня в том, что я требую ПОЛИНОМИАЛЬНЫЙ способ построения требуемой перестановки. Это не так. Меня устроит любая умозрительная конструкция. Вот для примера, доказательство утверждения об изоморфизме по мини-коду. Вы ведь это просили? Ну что-ж, извольте.

Лемма 1. Между кодом $C$ и матрицей размера $n \times n$ существует взаимно-однозначное соответствие.
В одну сторону - очевидно. Дана матрица, дан алгоритм построения - получаем код. Обратно. Дан код. Что это такое? Это число, которое в двоичном виде можно записать как
$C = c_02^0 + c_12^1 + ...$
Если это код какой-то матрицы $A$, то по определению
$c_0 = A_{1,2}$, $c_1 = A_{1,3}$ ...
Отметим, что начиная с некоторого разряда все биты будут равны 0. Вот здесь то нам и понадобится размер матрицы. До какого номера $m$ мы должны определять $c_m$? Из размера $n$ номер $m$ вычисляется однозначно: $m = n(n-1)/2-1$. Отсюда, кстати, видно, что если код содержит биты в разрядах старше $m$, то это число не может быть кодом никакой матрицы размера $n \times n$.
Тем самым, биты двоичного представления данного кода $C$ однозначно определяют наддиагональные элементы матрицы $A$. А в силу симметрии и всю матрицу. Легко видеть, что код этой матрицы в точности $C$. Впрочем, последее уже излишне. Нам нужна лишь взаимная однозначность.

Лемма 2. Пусть у двух графов мини-коды совпадают. Тогда найдется перестановка $P$, такая, что для их матриц смежности $M$,$M'$ имеет место равенство $M = P^{-1}M'P$. Доказательство.
Пусть миникод равен $C$. По лемме 1 существует единственная матрица $A$, код которой совпадает с $C$. По определению, миникод графа с матрицей $M$, это код некой матрицы, полученной перестановкой из $M$. Как мы видели, такая матрица единственна. Значит найдется некая перестановка $P_1$, такая, что $M = P_1^{-1}AP_1$.
Аналогично этому, найдется некая перестановка $P_2$, такая, что $M' = P_2^{-1}AP_2$.
Отсюда $M = P_1^{-1} P_2 M' P_2^{-1} P_1$. Следовательно, в качестве $P$ можно взять матрицу $P_2^{-1} P_1$. Отмечу, что в даном доказательстве "архи-важна" единственность такой матрицы $A$, иначе все построение просто развалится. И я это особо отмечаю, не смотря на всю "очевидность" этого утверждения.

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

[bin]

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

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

Например утверждения Зыкова о восстановлении матрицы смежности по мини-коду легко показать по индукции.

Но где в Вашем доказательстве индукция? Может, мы понимаем этот термин по-разному? Чтобы объяснить свое понимание, не буду далеко ходить, а процитирую википедию:

Цитата:

Для этого сначала проверяется истинность утверждения с номером $1$ — база (базис) индукции, а затем доказывается, что, если верно утверждение с номером $n$, то верно и следующее утверждение с номером $n + 1$ — шаг индукции, или индукционный переход. (Математическая индукция)

[sup]

Здесь индукции нет. Когда я писал про индукцию в предыдущем посте, мне показалось, что речь идет об изоморфизме деревьев (алгоритм Эдмондса). Позже выяснилось, что Вы просили доказать более простое утверждение. Но если Вы так настаиваете, то я могу ее туда добавить. Нет проблем.
Теорема. Из равенства миникодов графов следует их изоморфизм.

Доказательство проведем индукцией по натуральному $k$.

База. Пусть $k=1$. По лемме 2 графы изоморфны.
Индуктивное предположение. Пусть утверждение справедливо для $k = k_0$
Рассмотрим $k = k_0 + 1$. Вновь применяем лемму 2.
Тем самым, утверждение доказано с применением индукции. Как Вам и хотелось.
А Вы свое сможете доказать по индукции? Да хоть и без индукции. Просто докажите и делу край.