邻接矩阵是一种方形矩阵,通过记录哪些顶点对之间有边相连来表示有限图。它的行和列按指定顺序与顶点对应,每个元素表示相应顶点之间是否有边、边的数量或边的权重。邻接矩阵在图论与线性代数之间建立了基本联系,使人们能够通过矩阵运算、特征值和计算算法研究图的结构。
定义与约定
设 是一个图,其顶点集按顺序排列为 。对于既无自环也无重边的简单无向图,其邻接矩阵 定义为
因此, 是一个元素取值于 的 矩阵。它是对称矩阵,且所有对角元素均为零。
对于有向图,常见的约定是
按照这一约定,行描述出边连接,列描述入边连接。有些作者和软件系统采用相反的约定,因此在比较不同表示时,必须核实其含义。将每条边的方向反转,就相当于将 替换为它的转置 。
重边、自环与权重
这一定义可以推广到其他类型的图:
- 重边: 可以记录从 到 的边数。
- **自环:**对角元素记录连接顶点自身的边。
- 带权边: 可以记录边的权重,或平行边的权重之和。
对于无向自环,常见的约定有两种:每个自环对相应对角元素的贡献为 或 。当一个自环对顶点度数的贡献为二时,将它计数两次可使行和等于顶点度数;而当矩阵元素记录单次边遍历时,将它计数一次则更为自然。涉及度数或矩阵幂的公式,必须根据所采用的约定来理解。
加权邻接矩阵通常用零表示不存在边。如果允许权重为零的边,仅凭权重矩阵可能无法区分零权边与不存在的边;此时可能需要单独记录边是否存在。
示例与基本性质
考虑一个无向路径,其顶点为 ,边为 和 。它的邻接矩阵为
对于简单无向图,顶点 的度数 等于第 行的元素之和:
用 表示所有元素均为 的列向量,则度数向量为 。如果图有 条边,那么
因为每条边都对应两个位置对称的矩阵元素。
对于采用“行表示起点”约定的有向图,行和给出出度,列和给出入度。如果边带有权重,这些和给出的则是加权出度与加权入度,也称为出强度和入强度。
对顶点顺序的依赖
矩阵取决于顶点的排列顺序,但其所表示的图并不因此改变。若 是表示顺序变更的置换矩阵,则重新排序后的邻接矩阵具有如下形式:
因此,两个图同构,当且仅当它们的邻接矩阵可以通过这样的行列同步置换相互转换。这是矩阵相似的一种特殊情形,因此特征值、特征多项式以及其他相似不变量均不依赖于顶点的标号。
矩阵幂、游走与可达性
使用邻接矩阵的一个主要原因是,它的幂可以用来统计游走的数量。游走是由首尾相接的边构成的序列,其中顶点和边均可重复。对于无权图,若矩阵元素记录边数,且每个自环只计数一次,则
这一结论可由矩阵乘法得出:
每一项统计的是经过 步到达 ,然后再沿一条边到达 的游走数量。
对于上述三顶点路径,
中间的对角元素为 ,对应游走 和 。它们并不是简单路径:矩阵幂统计的是游走,而不只是顶点互不重复的路线。
对于加权邻接矩阵, 等于从相应起点到终点的所有长度为 的游走的边权乘积之和。
闭游走与子图计数
的迹统计长度为 的闭游走数量,并将起始顶点的不同选择分别计数。对于简单无向图,
每个三角形都有三个可选的起始顶点和两个遍历方向。
布尔可达性
用布尔代数代替普通算术,即用逻辑或代替加法、用逻辑与代替乘法时,矩阵幂表示的是游走是否存在,而非游走的数量。
对于 ,布尔矩阵
记录了顶点之间的可达性,其中单位矩阵 将长度为零的游走也包含在内。上界取 就已足够,因为只要一个顶点能从另一个顶点到达,就一定存在一条没有重复顶点的路径。
谱性质
邻接矩阵的特征值与特征向量构成其谱信息。对于具有实数对称权重的无向图,谱定理保证其所有特征值均为实数,并且存在一组由特征向量构成的标准正交基。
若干结构性质可以从谱的角度解释:
- 如果图是 正则图,即每个顶点的度数均为 ,那么 。
- 对于简单无向图,最大特征值不超过最大顶点度数。
- 如果简单无向图是连通的,则其最大特征值对应一个所有分量均严格为正的特征向量,且该向量在相差一个非零常数倍的意义下唯一。
- 一个简单无向图是二分图,当且仅当其特征值连同重数关于零对称。
如果特征值为 ,则
因此,谱数据能够确定闭游走的数量。然而,它们不能唯一确定图:不同构的图可能具有完全相同的邻接矩阵特征值。这样的图称为同谱图。
对于有向图,邻接矩阵不一定对称。其特征值可能是复数,也不一定存在一组由特征向量构成的完整基。
相关矩阵与表示方法
图拉普拉斯算子
对于边权非负的无向图,设 为以加权度数为对角元素的对角矩阵。图拉普拉斯算子为
对于无自环的图,
因此,拉普拉斯矩阵是半正定矩阵。其零特征值的重数等于连通分量的数量。拉普拉斯矩阵在图划分、扩散和聚类分析中具有核心作用。
随机游走转移矩阵
当所有顶点的度数均为正时,对各行进行归一化可得
对于无权图, 是位于顶点 的随机游走下一步移动到 的概率。由此得到的转移矩阵定义了一个马尔可夫链。孤立顶点需要另行约定,例如将其设为吸收态。
二分图
如果二分图的两个顶点类分别有 个和 个顶点,采用适当的排列顺序可得
其中, 矩阵 称为二分邻接矩阵,记录两个顶点类之间的边。与完整的邻接矩阵不同,它可以不是方阵。
补图
对于简单无向图,其补图的邻接矩阵为
其中 是全一矩阵。减去 是为了确保补图没有自环。
计算用途与局限
邻接矩阵可用于代数图算法、网络分析以及机器学习中基于矩阵的模型。对于稠密图、频繁的边查询,以及能够利用优化数值计算硬件的计算任务,它们尤其方便。
无论边数多少,完整的 表示都需要 个存储位置。在标准的随机访问表示中,判断某条边是否存在需要 时间,而列出某个顶点的全部邻接顶点则需要扫描一整行,耗时 。这些界限采用大O记号等渐近记号表示。
对于边数相对较少的图,邻接表通常能更紧凑地存储图结构,所需空间为 。稀疏矩阵表示仅存储非零元素,同时可以保留矩阵表示的许多代数优势,不过查找和修改的代价取决于存储格式。
对矩阵采用何种代数运算也很重要。普通乘法用于统计游走数量;布尔运算用于判断可达性;将加法替换为取最小值、将乘法替换为加法,则可用于某些最短路径计算。因此,将加权邻接矩阵当作无权邻接矩阵处理,或混淆游走与简单路径,都可能导致错误的解释。