я уже убедился, что мы по разному понимаем фразу "однозначно задает".
Ключ к пониманию есть у Харари:
Цитата:
Матрица смежностей [...] существует взаимно однозначное соответствие между помеченными графами с
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
вершинами и симметрическими бинарными
![$(p\times p)$ $(p\times p)$](https://dxdy-03.korotkov.co.uk/f/a/d/2/ad28a01927bbaa97efc064245385191282.png)
матрицами с нулями на диагонали. [...] Если
![$A_{1}$ $A_{1}$](https://dxdy-04.korotkov.co.uk/f/b/2/8/b2832f739d23176b744231e94d7ddada82.png)
и
![$A_{2}$ $A_{2}$](https://dxdy-04.korotkov.co.uk/f/7/1/6/71633e70788c689f9965bcbeb3e0125f82.png)
— матрицы смежностей, соответствующие различным нумерациям одного и того же графа
![$G$ $G$](https://dxdy-02.korotkov.co.uk/f/5/2/0/5201385589993766eea584cd3aa6fa1382.png)
, то
![$A_{1}=P^{-1}A_{2}P$ $A_{1}=P^{-1}A_{2}P$](https://dxdy-01.korotkov.co.uk/f/c/5/4/c5474a9193936393cfe8b31084361ad882.png)
для некоторой матрицы перестановки
![$P$ $P$](https://dxdy-02.korotkov.co.uk/f/d/f/5/df5a289587a2f0247a5b97c1e8ac58ca82.png)
. C.178-179
Обратное также верно: если
![$A_{1}=P^{-1}A_{2}P$ $A_{1}=P^{-1}A_{2}P$](https://dxdy-01.korotkov.co.uk/f/c/5/4/c5474a9193936393cfe8b31084361ad882.png)
, то
![$A_{1}$ $A_{1}$](https://dxdy-04.korotkov.co.uk/f/b/2/8/b2832f739d23176b744231e94d7ddada82.png)
и
![$A_{2}$ $A_{2}$](https://dxdy-04.korotkov.co.uk/f/7/1/6/71633e70788c689f9965bcbeb3e0125f82.png)
— матрицы смежности, соответствующие различным нумерациям одного и того же графа. Вместо «одного и того же графа» можно говорить о двух копиях одного и того же графа, т.е. о двух изоморфных графах с разной нумерацией вершин. При этом
![$A_{1}$ $A_{1}$](https://dxdy-04.korotkov.co.uk/f/b/2/8/b2832f739d23176b744231e94d7ddada82.png)
и
![$A_{2}$ $A_{2}$](https://dxdy-04.korotkov.co.uk/f/7/1/6/71633e70788c689f9965bcbeb3e0125f82.png)
могут быть неравны, и, соответственно, графы не равны, но изоморфны. Не существует двух неизоморфных графов, матрицы смежности которых удовлетворяют
![$A_{1}=P^{-1}A_{2}P$ $A_{1}=P^{-1}A_{2}P$](https://dxdy-01.korotkov.co.uk/f/c/5/4/c5474a9193936393cfe8b31084361ad882.png)
. Как же иначе можно понять утверждение о том, что матрица смежности однозначно задает граф?
Но если очень хочется, давайте возьмем два графа
![$G$ $G$](https://dxdy-02.korotkov.co.uk/f/5/2/0/5201385589993766eea584cd3aa6fa1382.png)
и
![$G'$ $G'$](https://dxdy-02.korotkov.co.uk/f/9/6/6/966ea729edb76f391d2d66d92daf725182.png)
, и модифицируем Вариант 2.
Вариант 2.2.Пусть
![$n\times n$ $n\times n$](https://dxdy-03.korotkov.co.uk/f/2/b/e/2be744f3276b5219af5f8dd5f793e02c82.png)
матрица
![$A$ $A$](https://dxdy-02.korotkov.co.uk/f/5/3/d/53d147e7f3fe6e47ee05b88b166bd3f682.png)
- матрица смежности графа
![$G_B$ $G_B$](https://dxdy-03.korotkov.co.uk/f/a/b/e/abe25a5cf2b94e0d1767d967ad87a14582.png)
. Получим с помощью декомпозиций все
![$\delta$ $\delta$](https://dxdy-04.korotkov.co.uk/f/3/8/f/38f1e2a089e53d5c990a82f28494895382.png)
-графы. Запишем "расширенные" матрицы смежности этих
![$\delta$ $\delta$](https://dxdy-04.korotkov.co.uk/f/3/8/f/38f1e2a089e53d5c990a82f28494895382.png)
-графов, как делали в Лемме 6 с другими графами. Т.е. для
![$\delta$ $\delta$](https://dxdy-04.korotkov.co.uk/f/3/8/f/38f1e2a089e53d5c990a82f28494895382.png)
-графа
![$\Delta_i$ $\Delta_i$](https://dxdy-02.korotkov.co.uk/f/9/b/d/9bdd4a586073113ff2a07f4afe289f6082.png)
в матрице
![$A$ $A$](https://dxdy-02.korotkov.co.uk/f/5/3/d/53d147e7f3fe6e47ee05b88b166bd3f682.png)
заменяем все единички, соответствующие ребрам, которые не входят в
![$\Delta_i$ $\Delta_i$](https://dxdy-02.korotkov.co.uk/f/9/b/d/9bdd4a586073113ff2a07f4afe289f6082.png)
нулями. Полученную матрицу обозначим
![$A_i$ $A_i$](https://dxdy-01.korotkov.co.uk/f/4/e/b/4ebf880807deff5796460f39aea46f8082.png)
.
Такая матрица соответствует графу, полученному из
![$\Delta_i$ $\Delta_i$](https://dxdy-02.korotkov.co.uk/f/9/b/d/9bdd4a586073113ff2a07f4afe289f6082.png)
добавлением всех вершин, не входящих в
![$\Delta_i$ $\Delta_i$](https://dxdy-02.korotkov.co.uk/f/9/b/d/9bdd4a586073113ff2a07f4afe289f6082.png)
, но входящих в
![$G_B$ $G_B$](https://dxdy-03.korotkov.co.uk/f/a/b/e/abe25a5cf2b94e0d1767d967ad87a14582.png)
. (Или, что то же самое: соответствует графу, полученному из
![$G_B$ $G_B$](https://dxdy-03.korotkov.co.uk/f/a/b/e/abe25a5cf2b94e0d1767d967ad87a14582.png)
удалением всех ребер, не входящих в
![$\Delta_i$ $\Delta_i$](https://dxdy-02.korotkov.co.uk/f/9/b/d/9bdd4a586073113ff2a07f4afe289f6082.png)
). Степень каждой добавленной вершины будет нулевой, и как было отмечено при доказательстве Леммы 6: если графы изоморфны, то и соответствующие им графы с раширенными матрицами будут изоморфны, добавление одинакового количества изолированных вершин к каждому графу не нарушает смежность. Дополнительные корни в
![$A_i$ $A_i$](https://dxdy-01.korotkov.co.uk/f/4/e/b/4ebf880807deff5796460f39aea46f8082.png)
отсутствуют и т.о. игнорируются.
А теперь, поэлементно проделав операцию "ИЛИ" над всеми матрицами
![$A_i$ $A_i$](https://dxdy-01.korotkov.co.uk/f/4/e/b/4ebf880807deff5796460f39aea46f8082.png)
, получим:
![$\underset{(i)}{\bigvee}A_{i}=A$ $\underset{(i)}{\bigvee}A_{i}=A$](https://dxdy-03.korotkov.co.uk/f/e/e/2/ee29846f9dad68b07e4ebbbd90eabc3282.png)
. Т.е. если в каком-либо
![$\delta$ $\delta$](https://dxdy-04.korotkov.co.uk/f/3/8/f/38f1e2a089e53d5c990a82f28494895382.png)
-графе есть ребро
![$(j,k)$ $(j,k)$](https://dxdy-02.korotkov.co.uk/f/5/7/7/577f0aa5510fdc977cdcb0695dc5dd0382.png)
, то и в графе
![$\underset{(i)}{\bigvee}A_{i}$ $\underset{(i)}{\bigvee}A_{i}$](https://dxdy-04.korotkov.co.uk/f/7/2/e/72ec56b5f7bd7ce909a2cb35855df2c482.png)
будет это ребро, и наоборот, если во всех
![$\delta$ $\delta$](https://dxdy-04.korotkov.co.uk/f/3/8/f/38f1e2a089e53d5c990a82f28494895382.png)
-графах отсутствует ребро
![$(j,k)$ $(j,k)$](https://dxdy-02.korotkov.co.uk/f/5/7/7/577f0aa5510fdc977cdcb0695dc5dd0382.png)
, то в графе
![$\underset{(i)}{\bigvee}A_{i}$ $\underset{(i)}{\bigvee}A_{i}$](https://dxdy-04.korotkov.co.uk/f/7/2/e/72ec56b5f7bd7ce909a2cb35855df2c482.png)
его не будет.
Все то же самое проделаем и с графом
![$G'$ $G'$](https://dxdy-02.korotkov.co.uk/f/9/6/6/966ea729edb76f391d2d66d92daf725182.png)
. Получим матрицы
![$A'_i$ $A'_i$](https://dxdy-03.korotkov.co.uk/f/6/6/8/668ef2db0127f77c701a8c7920c8f4c082.png)
. Если для какой-то перестановки
![$P$ $P$](https://dxdy-02.korotkov.co.uk/f/d/f/5/df5a289587a2f0247a5b97c1e8ac58ca82.png)
и для каждой матрицы
![$A_i$ $A_i$](https://dxdy-01.korotkov.co.uk/f/4/e/b/4ebf880807deff5796460f39aea46f8082.png)
, найдется такая матрица
![$A'_j$ $A'_j$](https://dxdy-02.korotkov.co.uk/f/1/7/9/179938582960babd3fd44f6cdcfb281a82.png)
, что
![$A_i=P^{-1}A'_{j}P$ $A_i=P^{-1}A'_{j}P$](https://dxdy-04.korotkov.co.uk/f/b/1/9/b1961000d5107b9dfa297326cbf88b5b82.png)
(
![$P$ $P$](https://dxdy-02.korotkov.co.uk/f/d/f/5/df5a289587a2f0247a5b97c1e8ac58ca82.png)
во всех случаях одна и та же), то
![$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$ $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$](https://dxdy-03.korotkov.co.uk/f/6/d/d/6dd4fed0587bfda58b98f9c8211f488482.png)
, и графы
![$G$ $G$](https://dxdy-02.korotkov.co.uk/f/5/2/0/5201385589993766eea584cd3aa6fa1382.png)
,
![$G'$ $G'$](https://dxdy-02.korotkov.co.uk/f/9/6/6/966ea729edb76f391d2d66d92daf725182.png)
изоморфны по определению изоморфизма
![$A=P^{-1}A'P$ $A=P^{-1}A'P$](https://dxdy-02.korotkov.co.uk/f/d/9/a/d9a7e55742aafff75d6600687b2dd44882.png)
. Если же для какой-то матрицы
![$A_i$ $A_i$](https://dxdy-01.korotkov.co.uk/f/4/e/b/4ebf880807deff5796460f39aea46f8082.png)
все матрицы
![$A'_j$ $A'_j$](https://dxdy-02.korotkov.co.uk/f/1/7/9/179938582960babd3fd44f6cdcfb281a82.png)
такие, что
![$A_i \neq P^{-1}A'_{j}P$ $A_i \neq P^{-1}A'_{j}P$](https://dxdy-03.korotkov.co.uk/f/2/1/d/21dcfd197f736c580d7383d932d0b6a482.png)
, то
![$A \neq P^{-1}A'P$ $A \neq P^{-1}A'P$](https://dxdy-01.korotkov.co.uk/f/0/d/3/0d36b5bff6e7224999b2b786b6d3ef1182.png)
, и графы
![$G$ $G$](https://dxdy-02.korotkov.co.uk/f/5/2/0/5201385589993766eea584cd3aa6fa1382.png)
,
![$G'$ $G'$](https://dxdy-02.korotkov.co.uk/f/9/6/6/966ea729edb76f391d2d66d92daf725182.png)
не изоморфны по тому же определению изоморфизма. Т.о. графы
![$G$ $G$](https://dxdy-02.korotkov.co.uk/f/5/2/0/5201385589993766eea584cd3aa6fa1382.png)
,
![$G'$ $G'$](https://dxdy-02.korotkov.co.uk/f/9/6/6/966ea729edb76f391d2d66d92daf725182.png)
изоморфны тогда и только тогда, когда для каждой матрицы
![$A_i$ $A_i$](https://dxdy-01.korotkov.co.uk/f/4/e/b/4ebf880807deff5796460f39aea46f8082.png)
, найдется такая матрица
![$A'_j$ $A'_j$](https://dxdy-02.korotkov.co.uk/f/1/7/9/179938582960babd3fd44f6cdcfb281a82.png)
, что
![$A_i=P^{-1}A'_{j}P$ $A_i=P^{-1}A'_{j}P$](https://dxdy-04.korotkov.co.uk/f/b/1/9/b1961000d5107b9dfa297326cbf88b5b82.png)
. Конец доказательства.
-- Сб ноя 16, 2013 09:48:14 --я предлагаю прямо предъявить соответствие вершин графа
![$G$ $G$](https://dxdy-02.korotkov.co.uk/f/5/2/0/5201385589993766eea584cd3aa6fa1382.png)
вершинам
![$G'$ $G'$](https://dxdy-02.korotkov.co.uk/f/9/6/6/966ea729edb76f391d2d66d92daf725182.png)
Я предлагаю алгоритм, который только отвечает на вопрос "изоморфны?" - Да/нет. Но он не устанавливает возможных соответствий. Допускаю, что поиск какого-либо конкретного изоморфизма может оказаться неполиномиальной задачей.