matrix - 发病矩阵

Question

关联矩阵中任意两行或两列的排列仅对应于重新标记同一图的顶点和边。相反，两个图 X 和 Y 是同构的当且仅当它们的关联矩阵 A(X) 和 A(Y) 仅在行和列的排列上有所不同。

有人可以举例说明这是什么意思吗？“任意两行或两列的排列”到底是什么意思？

Answer 1

“排列”在这里的意思是“交换”。考虑以下节点-节点关联矩阵：

0 1 0
0 0 1
1 0 0

它定义了一个顶点为 0、1、2 的图，其中边构成一个圆 0-1-2-0。如果交换前两行，我们得到

0 0 1
0 1 0
1 0 0

其中圆圈为 0-2-1-0。该图是通过将 1 重新标记为 2 从初始图获得的，反之亦然。这意味着两个图“在重命名顶点之前都是相同的”，即它们是同构的。