Определение 1. Будем говорить, что вершина
![$v$ $v$](https://dxdy-03.korotkov.co.uk/f/6/c/4/6c4adbc36120d62b98deef2a20d5d30382.png)
графа
![$G$ $G$](https://dxdy-02.korotkov.co.uk/f/5/2/0/5201385589993766eea584cd3aa6fa1382.png)
и вершина
![$v'$ $v'$](https://dxdy-02.korotkov.co.uk/f/1/9/e/19ef11ed79c62a9cb46775c20450d89f82.png)
графа
подобны, если они
подобны как вершины графа
![$G\cup G'$ $G\cup G'$](https://dxdy-02.korotkov.co.uk/f/d/e/d/ded8bc062ad8fb8bb7526c9e65bda2aa82.png)
.
Определение изоморфизма, которым я пользуюсь, следующее: обыкновенные
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
-графы
![$G$ $G$](https://dxdy-02.korotkov.co.uk/f/5/2/0/5201385589993766eea584cd3aa6fa1382.png)
и
![$H$ $H$](https://dxdy-04.korotkov.co.uk/f/7/b/9/7b9a0316a2fcd7f01cfd556eedf72e9682.png)
, с матрицами смежности
![$A $ $A $](https://dxdy-01.korotkov.co.uk/f/0/1/3/013dd970b31c3a70c7fe7cd1d7c5e6c982.png)
и
![$B$ $B$](https://dxdy-03.korotkov.co.uk/f/6/1/e/61e84f854bc6258d4108d08d4c4a085282.png)
соответственно,
изоморфны, если существует такая матрица перестановки
![$P$ $P$](https://dxdy-02.korotkov.co.uk/f/d/f/5/df5a289587a2f0247a5b97c1e8ac58ca82.png)
, что
![$B=PAP^T$ $B=PAP^T$](https://dxdy-03.korotkov.co.uk/f/2/7/2/272b1ebe36248ad99cda18dafc4c5cfc82.png)
. В указанном случае изоморфизмом будет матрица
![$P$ $P$](https://dxdy-02.korotkov.co.uk/f/d/f/5/df5a289587a2f0247a5b97c1e8ac58ca82.png)
. Изоморфное отображение графа на себя называется
автоморфизмом. Так матрица перестановки
![$Q$ $Q$](https://dxdy-02.korotkov.co.uk/f/1/a/f/1afcdb0f704394b16fe85fb40c45ca7a82.png)
задает автоморфизм, если
![$QAQ^T=A$ $QAQ^T=A$](https://dxdy-04.korotkov.co.uk/f/b/f/5/bf587336d401d723b24620d2b639f7a982.png)
. Из этой записи автоморфизма видно, что автоморфизм частный случай изоморфизма. В чем же их различие? Чтобы это выяснить, возьмем два различных изоморфизма
![$P_1$ $P_1$](https://dxdy-02.korotkov.co.uk/f/1/9/7/197fa3a18e4a8b8c7df669d00747613382.png)
и
![$P_2$ $P_2$](https://dxdy-04.korotkov.co.uk/f/b/d/a/bda33f0358442dd75d7487fa0ba0a27982.png)
и два различных автоморфизма
![$Q_1$ $Q_1$](https://dxdy-04.korotkov.co.uk/f/b/3/e/b3e07525c64893f724160bd7046f85d782.png)
и
![$Q_2$ $Q_2$](https://dxdy-02.korotkov.co.uk/f/d/4/5/d455ef8f60a853c27a0abd1e49898ea082.png)
. Рассмотрим произведение автоморфизмов
![$Q_2Q_1$ $Q_2Q_1$](https://dxdy-01.korotkov.co.uk/f/8/a/c/8ac4cb090c2d5c73075e6f9f903ed72f82.png)
(или
![$Q_1Q_2$ $Q_1Q_2$](https://dxdy-04.korotkov.co.uk/f/7/5/6/756d6c55912f48338ff07e798724597a82.png)
). Это произведение будет снова автоморфизмом, ибо
![$Q_2Q_1AQ_1^TQ_2^T = Q_2(Q_1AQ_1^T)Q_2^T = Q_2AQ_2^T = A$ $Q_2Q_1AQ_1^TQ_2^T = Q_2(Q_1AQ_1^T)Q_2^T = Q_2AQ_2^T = A$](https://dxdy-01.korotkov.co.uk/f/c/4/3/c433a70678dcf4b6897ba32563701e1382.png)
. Теперь уже нетрудно убедиться, что множество автоморфизмов относительно операции умножения автоморфизмов образует группу.
Рассмотрим теперь произведение
![$P_2P_1$ $P_2P_1$](https://dxdy-02.korotkov.co.uk/f/1/d/d/1dd70e5b952848b9a394aa892e22af5382.png)
. Это произведение, вообще говоря, не будет изоморфизмом. Действительно,
![$P_2P_1AP_1^TP_2^T = P_2(P_1AP_1^T)P_2^T = P_2BP_2^T$ $P_2P_1AP_1^TP_2^T = P_2(P_1AP_1^T)P_2^T = P_2BP_2^T$](https://dxdy-04.korotkov.co.uk/f/7/8/f/78fa791d3887bd271cd761345f7ecb3682.png)
. В общем случае
![$P_2BP_2^T \neq B$ $P_2BP_2^T \neq B$](https://dxdy-01.korotkov.co.uk/f/8/7/f/87fb9c0e6614443b4bafaed9cb0e83eb82.png)
. Следовательно, умножение изоморфизмов не замкнуто на множестве изоморфизмов и множество изоморфизмов не образует относительно операции умножения изоморфизмов группу. Произведение
![$P_2P_1$ $P_2P_1$](https://dxdy-02.korotkov.co.uk/f/1/d/d/1dd70e5b952848b9a394aa892e22af5382.png)
будет изоморфизмом, когда либо
![$P_2$ $P_2$](https://dxdy-04.korotkov.co.uk/f/b/d/a/bda33f0358442dd75d7487fa0ba0a27982.png)
- изоморфизм, а
![$P_1$ $P_1$](https://dxdy-02.korotkov.co.uk/f/1/9/7/197fa3a18e4a8b8c7df669d00747613382.png)
- автоморфизм для
![$A$ $A$](https://dxdy-02.korotkov.co.uk/f/5/3/d/53d147e7f3fe6e47ee05b88b166bd3f682.png)
, либо
![$P_1$ $P_1$](https://dxdy-02.korotkov.co.uk/f/1/9/7/197fa3a18e4a8b8c7df669d00747613382.png)
- изоморфизм, а
![$P_2$ $P_2$](https://dxdy-04.korotkov.co.uk/f/b/d/a/bda33f0358442dd75d7487fa0ba0a27982.png)
- автоморфизм для
![$B$ $B$](https://dxdy-03.korotkov.co.uk/f/6/1/e/61e84f854bc6258d4108d08d4c4a085282.png)
. В любом случае, с каждым изоморфизмом, например,
![$P_2$ $P_2$](https://dxdy-04.korotkov.co.uk/f/b/d/a/bda33f0358442dd75d7487fa0ba0a27982.png)
связан целый класс смежности симметрической группы (группы всевозможных перестановок порядка
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
) по подгруппе автоморфизмов для
![$ A$ $ A$](https://dxdy-01.korotkov.co.uk/f/c/5/c/c5cd509244936430520ce4bbaa5c00f082.png)
. То есть для любого изоморфизма
![$P_2$ $P_2$](https://dxdy-04.korotkov.co.uk/f/b/d/a/bda33f0358442dd75d7487fa0ba0a27982.png)
, изоморфизмом будет и произведение
![$P_2Q$ $P_2Q$](https://dxdy-03.korotkov.co.uk/f/6/a/f/6af20b7870f26495b38559a1ee2199a582.png)
, для любого автоморфизма
![$Q$ $Q$](https://dxdy-02.korotkov.co.uk/f/1/a/f/1afcdb0f704394b16fe85fb40c45ca7a82.png)
(
![$QAQ^T=A$ $QAQ^T=A$](https://dxdy-04.korotkov.co.uk/f/b/f/5/bf587336d401d723b24620d2b639f7a982.png)
). Аналогично, для любого изоморфизма
![$P_1$ $P_1$](https://dxdy-02.korotkov.co.uk/f/1/9/7/197fa3a18e4a8b8c7df669d00747613382.png)
, изоморфизмом будет и произведение
![$RP_1$ $RP_1$](https://dxdy-02.korotkov.co.uk/f/1/1/f/11fd617c3791bbd4d537480e7184bd3082.png)
, для любого автоморфизма
![$R$ $R$](https://dxdy-02.korotkov.co.uk/f/1/e/4/1e438235ef9ec72fc51ac5025516017c82.png)
(
![$RBR^T=B$ $RBR^T=B$](https://dxdy-02.korotkov.co.uk/f/d/b/2/db27deccaeea0bb70b3f000ae028279382.png)
).
Далее, любой автоморфизм
![$Q$ $Q$](https://dxdy-02.korotkov.co.uk/f/1/a/f/1afcdb0f704394b16fe85fb40c45ca7a82.png)
(
![$QAQ^T=A$ $QAQ^T=A$](https://dxdy-04.korotkov.co.uk/f/b/f/5/bf587336d401d723b24620d2b639f7a982.png)
), можно расписать поэлементно, т.е. в виде
![$\alpha(u)=v$ $\alpha(u)=v$](https://dxdy-01.korotkov.co.uk/f/0/3/4/034821127dd5a71fa208aee60dff621a82.png)
(
![$u, v$ $u, v$](https://dxdy-04.korotkov.co.uk/f/b/0/6/b062c846487797633a7321cc896abdeb82.png)
– вершины графа
![$G$ $G$](https://dxdy-02.korotkov.co.uk/f/5/2/0/5201385589993766eea584cd3aa6fa1382.png)
) и назвать эти вершины
подобными. Затем изоморфизм
![$P$ $P$](https://dxdy-02.korotkov.co.uk/f/d/f/5/df5a289587a2f0247a5b97c1e8ac58ca82.png)
(
![$B=PAP^T$ $B=PAP^T$](https://dxdy-03.korotkov.co.uk/f/2/7/2/272b1ebe36248ad99cda18dafc4c5cfc82.png)
) , также можно расписать поэлементно в виде
![$\pi(v)=v'$ $\pi(v)=v'$](https://dxdy-04.korotkov.co.uk/f/f/5/e/f5e786bef6807b700dcdd5832e5a644082.png)
, где v - вершина графа
![$G$ $G$](https://dxdy-02.korotkov.co.uk/f/5/2/0/5201385589993766eea584cd3aa6fa1382.png)
, а
![$v'$ $v'$](https://dxdy-02.korotkov.co.uk/f/1/9/e/19ef11ed79c62a9cb46775c20450d89f82.png)
- вершина графа
![$H$ $H$](https://dxdy-04.korotkov.co.uk/f/7/b/9/7b9a0316a2fcd7f01cfd556eedf72e9682.png)
. Никто не мешает по аналогии назвать вершины
![$v$ $v$](https://dxdy-03.korotkov.co.uk/f/6/c/4/6c4adbc36120d62b98deef2a20d5d30382.png)
и
подобными (автоморфизм частный случай изоморфизма). Другое дело, как Вы используете это аналогичное определение. Если это не ведет к недоразумениям, то никто не имеет права ставить Вам в упрек новое определение (по аналогии). Замечу, что у Харари, на стр. 36, для графов, имеющих
различные множества вершин и ребер, введена операция объединения графов, например, графов
![$G\cup H$ $G\cup H$](https://dxdy-04.korotkov.co.uk/f/f/c/5/fc5c19e1288eaddcc946598928b9bae482.png)
. Если графы
![$G$ $G$](https://dxdy-02.korotkov.co.uk/f/5/2/0/5201385589993766eea584cd3aa6fa1382.png)
и
![$H$ $H$](https://dxdy-04.korotkov.co.uk/f/7/b/9/7b9a0316a2fcd7f01cfd556eedf72e9682.png)
связные, то после объединения этих графов, они становятся различными компонентами связности одного графа. Вероятно, Ваш оппонент, когда делал Вам замечание, имел в виду следующее – определение подобных вершин у Харари дается для вершин одного графа, а Ваше обобщение переносит определение подобия на вершины разных графов. Поэтому его предложение сводится к тому, чтобы сделать вершины разных графов вершинами одного графа. Я в его, на мой взгляд, неудачном предложении не вижу "существа", вижу только желание сохранить форму.
Можно различать подобные вершины относительно автоморфизма и подобные вершины относительно изоморфизма (т.е. относительно операции изоморфного отображения). Можно сделать такое примечание в статье. Думаю, что из контекста там везде ясно, о каком подобии идет речь.