同构图的邻接矩阵与谱是否一致？实操疑问咨询

嗨，这个问题其实是图论里的基础结论之一，先给你吃个定心丸：同构图的谱（特征值，包括重数）一定是完全相同的。

核心原因：同构意味着邻接矩阵相似 #

两个图同构的定义是存在一个节点的双射（也就是你提到的按颜色对应的映射），能把图G₁的节点一一对应到G₂的节点，并且严格保持边的连接关系——原节点之间有边，映射后的节点之间也一定有边，反之亦然。

用邻接矩阵来表达这个性质的话，就是存在一个置换矩阵P（每行每列只有一个1的方阵，用来表示节点顺序的重排），使得G₂的邻接矩阵满足：
A₂ = PᵀA₁P
（注：置换矩阵的逆等于它的转置，所以也可以写成A₂ = P⁻¹A₁P，这就是线性代数里的相似变换）

而线性代数的核心结论之一就是：相似矩阵的特征值完全相同。相似变换只是重新排列了描述矩阵的基向量，不会改变矩阵的核心特征（特征值及重数），所以同构图的谱必然一致。

对你操作的验证：邻接矩阵一致是合理的 #

你按节点颜色对应映射写出两个图的邻接矩阵后发现它们一致，这完全不是操作失误，反而刚好印证了同构图的性质。因为当你把两个图的节点都按照这个同构映射的顺序来排列时，它们的邻接矩阵自然会完全重合——相当于你直接用同构映射对齐了节点顺序，跳过了相似变换的步骤，得到的矩阵当然一模一样。

额外补充：注意逆命题不成立 #

最后提个小知识点：反过来，谱相同的图不一定是同构图（这类图被称为「同谱图」），但你问的正向结论（同构图必同谱）是绝对成立的，不用有任何怀疑。

内容的提问来源于stack exchange，提问作者bee5911