611 图的性质

图的性质

邻接矩阵 A

邻接矩阵 $A$ 是一个方阵，用于表示一个有限图。如果图有 $N$ 个顶点，那么 $A$ 是一个 $N\times N$ 的矩阵。

• 元素 $A_{ij}$ 的含义：
• 对于简单图（没有自环和重边）：如果顶点 $i$ 和顶点 $j$ 之间存在一条边，则矩阵的第 $i$ 行第 $j$ 列的元素 $A_{ij}=1$；如果没有边，则 $A_{ij}=0$。对于简单图，对角线元素 $A_{ii}$ 通常为 0，因为不允许自环。
• 对于允许重边或自环的图：$A_{ij}$ 可以表示顶点 $i$ 和顶点 $j$ 之间的边的数量。如果允许自环，对角线元素 $A_{ii}$ 可以非零。
• 无向图的邻接矩阵：如果图是无向的，即所有边都是双向的，那么邻接矩阵是对称的，即 $A_{ij}=A_{ji}$。
• 有向图的邻接矩阵：行通常表示出边（从该行对应的顶点出发的边），列表示入边（指向该列对应顶点的边）。

邻接矩阵的平方 A²

矩阵 $A^2$ 是通过将邻接矩阵 $A$ 与自身进行矩阵乘法得到的。

• 元素 $(A^2{)}_{ij}$ 的含义：矩阵 $A^2$ 的第 $i$ 行第 $j$ 列的元素 $(A^2{)}_{ij}$ 表示从顶点 $i$ 到顶点 $j$ 的长度为 2 的路径（或漫游）的数量。
• 这意味着如果 $(A^2{)}_{ij}>0$，则存在至少一条从顶点 $i$ 经过一个中间顶点到达顶点 $j$ 的路径。
• 对角线元素 $(A^2{)}_{ii}$ 的含义：对角线上的元素 $(A^2{)}_{ii}$ 表示从顶点 $i$ 出发，经过一条边再回到顶点 $i$ 的长度为 2 的闭合路径的数量。这实际上等于顶点 $i$ 的度数（degree），即与顶点 $i$ 相连的边的数量。
• 矩阵的迹 $tr(A^2)$：$A^2$ 的迹（对角线元素之和）等于图中所有顶点度数之和，也等于图中边数的两倍，即 $tr(A^2)={\sum }_{i=1}^N\mathrm{deg}(v_i)=2m$，其中 $m$ 是图中的边数。

邻接矩阵的 n 次幂 Aⁿ

更一般地，邻接矩阵的 $n$ 次幂（或写作 $A^k$）提供了关于更长路径的信息。

• 元素 $(A^n{)}_{ij}$ 的含义：矩阵 $A^n$ 的第 $i$ 行第 $j$ 列的元素 $(A^n{)}_{ij}$ 表示从顶点 $i$ 到顶点 $j$ 的长度为 $n$ 的路径（或漫游）的数量。
• 这是一个非常重要的结论，可以通过数学归纳法证明。
• 例如，$(A^3{)}_{ij}$ 表示从顶点 $i$ 到顶点 $j$ 的长度为 3 的路径数量。

总结来说，邻接矩阵的幂次可以揭示图中不同顶点之间特定长度路径的数量。$A$ 直接表示了长度为 1 的路径（即边），$A^2$ 表示长度为 2 的路径，而 $A^n$ 则表示长度为 $n$ 的路径。