Если бы это предположение подтвердилось
Это означает, что была бы доказана теорема, в которой было бы доказано существование такой перестановки. А это может быть только в двух случаях. Либо она была бы построена (хотя бы и не полиномиальным способом), либо ее существование было бы получено неконструктивным рассуждением от противного. Если Вы намекаете на то, что я не упомянул еще и такой вариант, то да, я был не вполне прав.
Вы все время подозреваете меня в том, что я требую ПОЛИНОМИАЛЬНЫЙ способ построения требуемой перестановки. Это не так. Меня устроит любая умозрительная конструкция. Вот для примера, доказательство утверждения об изоморфизме по мини-коду. Вы ведь это просили? Ну что-ж, извольте.
Лемма 1. Между кодом
![$C$ $C$](https://dxdy-02.korotkov.co.uk/f/9/b/3/9b325b9e31e85137d1de765f43c0f8bc82.png)
и матрицей размера
![$n \times n$ $n \times n$](https://dxdy-04.korotkov.co.uk/f/3/a/d/3add1221abfa79cb14021bc2dacd572582.png)
существует взаимно-однозначное соответствие.
В одну сторону - очевидно. Дана матрица, дан алгоритм построения - получаем код. Обратно. Дан код. Что это такое? Это число, которое в двоичном виде можно записать как
![$C = c_02^0 + c_12^1 + ...$ $C = c_02^0 + c_12^1 + ...$](https://dxdy-01.korotkov.co.uk/f/4/9/5/495c87861cac473f79d629547b6265b982.png)
Если это код какой-то матрицы
![$A$ $A$](https://dxdy-02.korotkov.co.uk/f/5/3/d/53d147e7f3fe6e47ee05b88b166bd3f682.png)
, то по определению
![$c_0 = A_{1,2}$ $c_0 = A_{1,2}$](https://dxdy-02.korotkov.co.uk/f/5/2/7/5279808ae66bafaf7816e36bd809f8d482.png)
,
![$c_1 = A_{1,3}$ $c_1 = A_{1,3}$](https://dxdy-03.korotkov.co.uk/f/6/5/a/65aecfa0f1fe920b0743ea44af9eba9082.png)
...
Отметим, что начиная с некоторого разряда все биты будут равны 0. Вот здесь то нам и понадобится размер матрицы. До какого номера
![$m$ $m$](https://dxdy-01.korotkov.co.uk/f/0/e/5/0e51a2dede42189d77627c4d742822c382.png)
мы должны определять
![$c_m$ $c_m$](https://dxdy-03.korotkov.co.uk/f/e/7/1/e710976777475b48fa8cd4acca53874882.png)
? Из размера
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
номер
![$m$ $m$](https://dxdy-01.korotkov.co.uk/f/0/e/5/0e51a2dede42189d77627c4d742822c382.png)
вычисляется однозначно:
![$m = n(n-1)/2-1$ $m = n(n-1)/2-1$](https://dxdy-03.korotkov.co.uk/f/a/e/7/ae746e8ac2c888323a0c21a385c3ff7282.png)
. Отсюда, кстати, видно, что если код содержит биты в разрядах старше
![$m$ $m$](https://dxdy-01.korotkov.co.uk/f/0/e/5/0e51a2dede42189d77627c4d742822c382.png)
, то это число не может быть кодом никакой матрицы размера
![$n \times n$ $n \times n$](https://dxdy-04.korotkov.co.uk/f/3/a/d/3add1221abfa79cb14021bc2dacd572582.png)
.
Тем самым, биты двоичного представления данного кода
![$C$ $C$](https://dxdy-02.korotkov.co.uk/f/9/b/3/9b325b9e31e85137d1de765f43c0f8bc82.png)
однозначно определяют наддиагональные элементы матрицы
![$A$ $A$](https://dxdy-02.korotkov.co.uk/f/5/3/d/53d147e7f3fe6e47ee05b88b166bd3f682.png)
. А в силу симметрии и всю матрицу. Легко видеть, что код этой матрицы в точности
![$C$ $C$](https://dxdy-02.korotkov.co.uk/f/9/b/3/9b325b9e31e85137d1de765f43c0f8bc82.png)
. Впрочем, последее уже излишне. Нам нужна лишь взаимная однозначность.
Лемма 2. Пусть у двух графов мини-коды совпадают. Тогда найдется перестановка
![$P$ $P$](https://dxdy-02.korotkov.co.uk/f/d/f/5/df5a289587a2f0247a5b97c1e8ac58ca82.png)
, такая, что для их матриц смежности
![$M$ $M$](https://dxdy-04.korotkov.co.uk/f/f/b/9/fb97d38bcc19230b0acd442e17db879c82.png)
,
![$M'$ $M'$](https://dxdy-01.korotkov.co.uk/f/0/f/2/0f2499041fc1b61072cd553b4a1deed782.png)
имеет место равенство
![$M = P^{-1}M'P$ $M = P^{-1}M'P$](https://dxdy-03.korotkov.co.uk/f/6/e/0/6e0003f9070c21e3c905a7f0f496c4fb82.png)
. Доказательство.
Пусть миникод равен
![$C$ $C$](https://dxdy-02.korotkov.co.uk/f/9/b/3/9b325b9e31e85137d1de765f43c0f8bc82.png)
. По лемме 1 существует
единственная матрица
![$A$ $A$](https://dxdy-02.korotkov.co.uk/f/5/3/d/53d147e7f3fe6e47ee05b88b166bd3f682.png)
, код которой совпадает с
![$C$ $C$](https://dxdy-02.korotkov.co.uk/f/9/b/3/9b325b9e31e85137d1de765f43c0f8bc82.png)
. По определению, миникод графа с матрицей
![$M$ $M$](https://dxdy-04.korotkov.co.uk/f/f/b/9/fb97d38bcc19230b0acd442e17db879c82.png)
, это код некой матрицы, полученной перестановкой из
![$M$ $M$](https://dxdy-04.korotkov.co.uk/f/f/b/9/fb97d38bcc19230b0acd442e17db879c82.png)
. Как мы видели, такая матрица единственна. Значит найдется некая перестановка
![$P_1$ $P_1$](https://dxdy-02.korotkov.co.uk/f/1/9/7/197fa3a18e4a8b8c7df669d00747613382.png)
, такая, что
![$M = P_1^{-1}AP_1$ $M = P_1^{-1}AP_1$](https://dxdy-03.korotkov.co.uk/f/e/6/5/e65041c4e72767226f515429074e19b682.png)
.
Аналогично этому, найдется некая перестановка
![$P_2$ $P_2$](https://dxdy-04.korotkov.co.uk/f/b/d/a/bda33f0358442dd75d7487fa0ba0a27982.png)
, такая, что
![$M' = P_2^{-1}AP_2$ $M' = P_2^{-1}AP_2$](https://dxdy-01.korotkov.co.uk/f/8/4/8/848531022ba53fa011674d6a03c6c57e82.png)
.
Отсюда
![$M = P_1^{-1} P_2 M' P_2^{-1} P_1$ $M = P_1^{-1} P_2 M' P_2^{-1} P_1$](https://dxdy-04.korotkov.co.uk/f/3/2/7/327d9c70fdbfc120311a15d62ee63c0e82.png)
. Следовательно, в качестве
![$P$ $P$](https://dxdy-02.korotkov.co.uk/f/d/f/5/df5a289587a2f0247a5b97c1e8ac58ca82.png)
можно взять матрицу
![$P_2^{-1} P_1$ $P_2^{-1} P_1$](https://dxdy-02.korotkov.co.uk/f/d/5/d/d5d13f6471b375526df09274670ca55982.png)
. Отмечу, что в даном доказательстве "архи-важна" единственность такой матрицы
![$A$ $A$](https://dxdy-02.korotkov.co.uk/f/5/3/d/53d147e7f3fe6e47ee05b88b166bd3f682.png)
, иначе все построение просто развалится. И я это особо отмечаю, не смотря на всю "очевидность" этого утверждения.
Обратите внимание. Я ПОСТРОИЛ перестановку
![$P$ $P$](https://dxdy-02.korotkov.co.uk/f/d/f/5/df5a289587a2f0247a5b97c1e8ac58ca82.png)
. Как мне это удалось? Да очень просто. Посылка леммы утверждала, что у данного графа есть такой-то код. Эта посылка неявно содержит утверждение о
существовании некой перестановки. Вот эту неявную перестановку я и использовал.
Ничто не мешает Вам использовать такие же соображения. Я Вам об этом твердил уже не знаю сколько раз. Изоморфизм
![$\Delta_i \cong \Delta'_i$ $\Delta_i \cong \Delta'_i$](https://dxdy-03.korotkov.co.uk/f/6/f/e/6fe3acf260b57a0d1340eec03b19a80b82.png)
точно так же неявно дает Вам перестановки
![$P_i$ $P_i$](https://dxdy-03.korotkov.co.uk/f/e/f/0/ef0de0b48cb187b636ae34b0aea8c1db82.png)
. Вот и пользуйтесь ими сколько угодно. Но Вам эта идея не понравилась, потому, что склеить из них общую перестановку Вы не можете. Да и никто не может. Ни у кого нет никаких идей на этот счет. Иначе бы это давным-давно сделали. Вам об этом твердят раз за разом. Нужны нетривиальные идеи, позволяющие как-то увязать между собой все эти
![$P_i$ $P_i$](https://dxdy-03.korotkov.co.uk/f/e/f/0/ef0de0b48cb187b636ae34b0aea8c1db82.png)
, чтобы в конце-концов склеить из них что-то подходящее.
Альтернатива этому ровно одна. Доказать существование методом от противного. Предположим, что такой нет. Тогда .... трали-вали ... противоречие.
Вот в этом духе и должно быть Ваше доказательство. Дальше уже выбирайте сами, что Вам больше подходит.