Если бы это предположение подтвердилось
Это означает, что была бы доказана теорема, в которой было бы доказано существование такой перестановки. А это может быть только в двух случаях. Либо она была бы построена (хотя бы и не полиномиальным способом), либо ее существование было бы получено неконструктивным рассуждением от противного. Если Вы намекаете на то, что я не упомянул еще и такой вариант, то да, я был не вполне прав.
Вы все время подозреваете меня в том, что я требую ПОЛИНОМИАЛЬНЫЙ способ построения требуемой перестановки. Это не так. Меня устроит любая умозрительная конструкция. Вот для примера, доказательство утверждения об изоморфизме по мини-коду. Вы ведь это просили? Ну что-ж, извольте.
Лемма 1. Между кодом
и матрицей размера
существует взаимно-однозначное соответствие.
В одну сторону - очевидно. Дана матрица, дан алгоритм построения - получаем код. Обратно. Дан код. Что это такое? Это число, которое в двоичном виде можно записать как
Если это код какой-то матрицы
, то по определению
,
...
Отметим, что начиная с некоторого разряда все биты будут равны 0. Вот здесь то нам и понадобится размер матрицы. До какого номера
мы должны определять
? Из размера
номер
вычисляется однозначно:
. Отсюда, кстати, видно, что если код содержит биты в разрядах старше
, то это число не может быть кодом никакой матрицы размера
.
Тем самым, биты двоичного представления данного кода
однозначно определяют наддиагональные элементы матрицы
. А в силу симметрии и всю матрицу. Легко видеть, что код этой матрицы в точности
. Впрочем, последее уже излишне. Нам нужна лишь взаимная однозначность.
Лемма 2. Пусть у двух графов мини-коды совпадают. Тогда найдется перестановка
, такая, что для их матриц смежности
,
имеет место равенство
. Доказательство.
Пусть миникод равен
. По лемме 1 существует
единственная матрица
, код которой совпадает с
. По определению, миникод графа с матрицей
, это код некой матрицы, полученной перестановкой из
. Как мы видели, такая матрица единственна. Значит найдется некая перестановка
, такая, что
.
Аналогично этому, найдется некая перестановка
, такая, что
.
Отсюда
. Следовательно, в качестве
можно взять матрицу
. Отмечу, что в даном доказательстве "архи-важна" единственность такой матрицы
, иначе все построение просто развалится. И я это особо отмечаю, не смотря на всю "очевидность" этого утверждения.
Обратите внимание. Я ПОСТРОИЛ перестановку
. Как мне это удалось? Да очень просто. Посылка леммы утверждала, что у данного графа есть такой-то код. Эта посылка неявно содержит утверждение о
существовании некой перестановки. Вот эту неявную перестановку я и использовал.
Ничто не мешает Вам использовать такие же соображения. Я Вам об этом твердил уже не знаю сколько раз. Изоморфизм
точно так же неявно дает Вам перестановки
. Вот и пользуйтесь ими сколько угодно. Но Вам эта идея не понравилась, потому, что склеить из них общую перестановку Вы не можете. Да и никто не может. Ни у кого нет никаких идей на этот счет. Иначе бы это давным-давно сделали. Вам об этом твердят раз за разом. Нужны нетривиальные идеи, позволяющие как-то увязать между собой все эти
, чтобы в конце-концов склеить из них что-то подходящее.
Альтернатива этому ровно одна. Доказать существование методом от противного. Предположим, что такой нет. Тогда .... трали-вали ... противоречие.
Вот в этом духе и должно быть Ваше доказательство. Дальше уже выбирайте сами, что Вам больше подходит.