基于邻接矩阵定义的图自同构的置换矩阵描述方法问询

嘿，这个问题戳中了很多人用邻接矩阵理解图自同构的误区，我来给你捋清楚～

首先，你之前对图同构的置换矩阵描述有点小偏差，这也是导致你困惑自同构的根源。正确的同构定义应该是：两个图的邻接矩阵A和B同构，当且仅当存在置换矩阵σ，使得 $\sigma A \sigma^{-1} = B$（或者等价于 $\sigma^T A \sigma = B$，因为置换矩阵的逆等于它的转置）。这个式子的本质是：用σ置换A的行，再用σ⁻¹（也就是σ^T）置换列，得到的矩阵就是B——相当于把A的节点按σ重新编号后，结构和B完全一致。

那回到图自同构，它其实是同构的特殊情况：当B=A的时候，也就是置换σ作用在A上之后，得到的矩阵还是A本身。所以自同构的正确描述是：存在置换矩阵σ，使得 $\sigma A \sigma^{-1} = A$（或者 $\sigma^T A \sigma = A$）。

为什么你之前想的 $\sigma A = A$ 不对呢？因为这个式子只要求“置换行之后矩阵不变”，这只有当所有行的结构完全相同时才成立（比如完全图），但绝大多数图并不满足这个条件。而自同构的核心是节点重排后图的邻接关系完全不变，这需要同时置换行和列：置换行对应重新排列节点作为“起点”的邻接关系，置换列对应重新排列节点作为“终点”的邻接关系，两者结合才能保证重排后的邻接矩阵和原矩阵一致。

举个简单例子帮你理解：

• 拿3节点的路径图来说，邻接矩阵A是：

  0 1 0
  1 0 1
  0 1 0
  

• 取置换矩阵σ，它对应交换节点1和3（也就是σ是$\begin{bmatrix}0&0&1\0&1&0\1&0&0\end{bmatrix}$）。
• 计算 $\sigma A \sigma^{-1}$：因为σ是对称矩阵，σ⁻¹=σ，所以先算σA得到的结果和A一致，再乘以σ后结果还是A。这说明σ是这个图的一个自同构——交换节点1和3后，图的结构完全没变，这符合我们对自同构的直观理解。

如果换一个不对称的图，比如邻接矩阵是：

0 1 0
1 0 0
0 0 0

这时候交换节点1和2的置换矩阵σ，σA会变成：

1 0 0
0 1 0
0 0 0

显然不等于A，但计算 $\sigma A \sigma^{-1}$ 会得到原矩阵A，这说明σ是自同构，而 $\sigma A = A$ 并不成立——这就体现了正确定义的必要性。

总结一下：

• 图同构：$\sigma A \sigma^{-1} = B$（节点重排后A变成B）
• 图自同构：$\sigma A \sigma^{-1} = A$（节点重排后图的结构不变）

这样就和邻接矩阵的定义完美契合啦～

备注：内容来源于stack exchange，提问作者Loic Stoic