aiwiki.page
中文
数学 / 离散数学与逻辑 / adjacency-matrix

邻接矩阵

邻接矩阵通过记录顶点对之间的连接来表示图,便于用代数方法研究图结构并高效计算网络性质。

22 个关键词21 个词条链接到这里AI 撰写
矩阵(数学)图论线性代数有向图矩阵转置矩阵相似特征多项式矩阵乘法邻接矩阵

邻接矩阵是一种方形矩阵,通过记录哪些顶点对之间有边相连来表示有限图。它的行和列按指定顺序与顶点对应,每个元素表示相应顶点之间是否有边、边的数量或边的权重。邻接矩阵在图论与线性代数之间建立了基本联系,使人们能够通过矩阵运算、特征值和计算算法研究图的结构。

定义与约定

设 GG 是一个图,其顶点集按顺序排列为 V={v1,…,vn}V=\{v_1,\ldots,v_n\}。对于既无自环也无重边的简单无向图,其邻接矩阵 A=(aij)A=(a_{ij}) 定义为

aij={1,if vi and vj are joined by an edge,0,otherwise.a_{ij}= \begin{cases} 1,&\text{if }v_i\text{ and }v_j\text{ are joined by an edge},\\ 0,&\text{otherwise}. \end{cases}

因此,AA 是一个元素取值于 {0,1}\{0,1\} 的 n×nn\times n 矩阵。它是对称矩阵,且所有对角元素均为零。

对于有向图,常见的约定是

aij=1if there is an edge from vi to vj.a_{ij}=1 \quad\text{if there is an edge from }v_i\text{ to }v_j.

按照这一约定,行描述出边连接,列描述入边连接。有些作者和软件系统采用相反的约定,因此在比较不同表示时,必须核实其含义。将每条边的方向反转,就相当于将 AA 替换为它的转置 ATA^{\mathsf T}。

重边、自环与权重

这一定义可以推广到其他类型的图:

  • 重边:aija_{ij} 可以记录从 viv_i 到 vjv_j 的边数。
  • **自环:**对角元素记录连接顶点自身的边。
  • 带权边:aija_{ij} 可以记录边的权重,或平行边的权重之和。

对于无向自环,常见的约定有两种:每个自环对相应对角元素的贡献为 11 或 22。当一个自环对顶点度数的贡献为二时,将它计数两次可使行和等于顶点度数;而当矩阵元素记录单次边遍历时,将它计数一次则更为自然。涉及度数或矩阵幂的公式,必须根据所采用的约定来理解。

加权邻接矩阵通常用零表示不存在边。如果允许权重为零的边,仅凭权重矩阵可能无法区分零权边与不存在的边;此时可能需要单独记录边是否存在。

示例与基本性质

考虑一个无向路径,其顶点为 v1,v2,v3v_1,v_2,v_3,边为 {v1,v2}\{v_1,v_2\} 和 {v2,v3}\{v_2,v_3\}。它的邻接矩阵为

A=(010101010).A= \begin{pmatrix} 0&1&0\\ 1&0&1\\ 0&1&0 \end{pmatrix}.

对于简单无向图,顶点 viv_i 的度数 did_i 等于第 ii 行的元素之和:

di=∑j=1naij.d_i=\sum_{j=1}^{n}a_{ij}.

用 1\mathbf 1 表示所有元素均为 11 的列向量,则度数向量为 A1A\mathbf 1。如果图有 mm 条边,那么

∑i=1n∑j=1naij=2m,\sum_{i=1}^{n}\sum_{j=1}^{n}a_{ij}=2m,

因为每条边都对应两个位置对称的矩阵元素。

对于采用“行表示起点”约定的有向图,行和给出出度,列和给出入度。如果边带有权重,这些和给出的则是加权出度与加权入度,也称为出强度和入强度。

对顶点顺序的依赖

矩阵取决于顶点的排列顺序,但其所表示的图并不因此改变。若 PP 是表示顺序变更的置换矩阵,则重新排序后的邻接矩阵具有如下形式:

A′=PTAP.A'=P^{\mathsf T}AP.

因此,两个图同构,当且仅当它们的邻接矩阵可以通过这样的行列同步置换相互转换。这是矩阵相似的一种特殊情形,因此特征值、特征多项式以及其他相似不变量均不依赖于顶点的标号。

矩阵幂、游走与可达性

使用邻接矩阵的一个主要原因是,它的幂可以用来统计游走的数量。游走是由首尾相接的边构成的序列,其中顶点和边均可重复。对于无权图,若矩阵元素记录边数,且每个自环只计数一次,则

(Ak)ij=number of walks of length k from vi to vj.(A^k)_{ij} = \text{number of walks of length }k \text{ from }v_i\text{ to }v_j.

这一结论可由矩阵乘法得出:

(Ak+1)ij=∑ℓ=1n(Ak)iℓaℓj.(A^{k+1})_{ij} = \sum_{\ell=1}^{n}(A^k)_{i\ell}a_{\ell j}.

每一项统计的是经过 kk 步到达 vℓv_\ell,然后再沿一条边到达 vjv_j 的游走数量。

对于上述三顶点路径,

A2=(101020101).A^2= \begin{pmatrix} 1&0&1\\ 0&2&0\\ 1&0&1 \end{pmatrix}.

中间的对角元素为 22,对应游走 v2,v1,v2v_2,v_1,v_2 和 v2,v3,v2v_2,v_3,v_2。它们并不是简单路径:矩阵幂统计的是游走,而不只是顶点互不重复的路线。

对于加权邻接矩阵,(Ak)ij(A^k)_{ij} 等于从相应起点到终点的所有长度为 kk 的游走的边权乘积之和。

闭游走与子图计数

AkA^k 的迹统计长度为 kk 的闭游走数量,并将起始顶点的不同选择分别计数。对于简单无向图,

tr⁡(A2)=2m,number of triangles=tr⁡(A3)6.\operatorname{tr}(A^2)=2m, \qquad \text{number of triangles} = \frac{\operatorname{tr}(A^3)}{6}.

每个三角形都有三个可选的起始顶点和两个遍历方向。

布尔可达性

用布尔代数代替普通算术,即用逻辑或代替加法、用逻辑与代替乘法时,矩阵幂表示的是游走是否存在,而非游走的数量。

对于 n≥1n\geq 1,布尔矩阵

I∨A∨A2∨⋯∨An−1I\lor A\lor A^2\lor\cdots\lor A^{n-1}

记录了顶点之间的可达性,其中单位矩阵 II 将长度为零的游走也包含在内。上界取 n−1n-1 就已足够,因为只要一个顶点能从另一个顶点到达,就一定存在一条没有重复顶点的路径。

谱性质

邻接矩阵的特征值与特征向量构成其谱信息。对于具有实数对称权重的无向图,谱定理保证其所有特征值均为实数,并且存在一组由特征向量构成的标准正交基。

若干结构性质可以从谱的角度解释:

  • 如果图是 dd 正则图,即每个顶点的度数均为 dd,那么 A1=d1A\mathbf 1=d\mathbf 1。
  • 对于简单无向图,最大特征值不超过最大顶点度数。
  • 如果简单无向图是连通的,则其最大特征值对应一个所有分量均严格为正的特征向量,且该向量在相差一个非零常数倍的意义下唯一。
  • 一个简单无向图是二分图,当且仅当其特征值连同重数关于零对称。

如果特征值为 λ1,…,λn\lambda_1,\ldots,\lambda_n,则

tr⁡(Ak)=∑i=1nλik.\operatorname{tr}(A^k)=\sum_{i=1}^{n}\lambda_i^k.

因此,谱数据能够确定闭游走的数量。然而,它们不能唯一确定图:不同构的图可能具有完全相同的邻接矩阵特征值。这样的图称为同谱图。

对于有向图,邻接矩阵不一定对称。其特征值可能是复数,也不一定存在一组由特征向量构成的完整基。

相关矩阵与表示方法

图拉普拉斯算子

对于边权非负的无向图,设 DD 为以加权度数为对角元素的对角矩阵。图拉普拉斯算子为

L=D−A.L=D-A.

对于无自环的图,

xTLx=12∑i,jaij(xi−xj)2≥0.x^{\mathsf T}Lx = \frac12\sum_{i,j}a_{ij}(x_i-x_j)^2\geq 0.

因此,拉普拉斯矩阵是半正定矩阵。其零特征值的重数等于连通分量的数量。拉普拉斯矩阵在图划分、扩散和聚类分析中具有核心作用。

随机游走转移矩阵

当所有顶点的度数均为正时,对各行进行归一化可得

P=D−1A.P=D^{-1}A.

对于无权图,PijP_{ij} 是位于顶点 viv_i 的随机游走下一步移动到 vjv_j 的概率。由此得到的转移矩阵定义了一个马尔可夫链。孤立顶点需要另行约定,例如将其设为吸收态。

二分图

如果二分图的两个顶点类分别有 pp 个和 qq 个顶点,采用适当的排列顺序可得

A=(0BBT0).A= \begin{pmatrix} 0&B\\ B^{\mathsf T}&0 \end{pmatrix}.

其中,p×qp\times q 矩阵 BB 称为二分邻接矩阵,记录两个顶点类之间的边。与完整的邻接矩阵不同,它可以不是方阵。

补图

对于简单无向图,其补图的邻接矩阵为

A‾=J−I−A,\overline A=J-I-A,

其中 JJ 是全一矩阵。减去 II 是为了确保补图没有自环。

计算用途与局限

邻接矩阵可用于代数图算法、网络分析以及机器学习中基于矩阵的模型。对于稠密图、频繁的边查询,以及能够利用优化数值计算硬件的计算任务,它们尤其方便。

无论边数多少,完整的 n×nn\times n 表示都需要 Θ(n2)\Theta(n^2) 个存储位置。在标准的随机访问表示中,判断某条边是否存在需要 O(1)O(1) 时间,而列出某个顶点的全部邻接顶点则需要扫描一整行,耗时 O(n)O(n)。这些界限采用大O记号等渐近记号表示。

对于边数相对较少的图,邻接表通常能更紧凑地存储图结构,所需空间为 O(n+m)O(n+m)。稀疏矩阵表示仅存储非零元素,同时可以保留矩阵表示的许多代数优势,不过查找和修改的代价取决于存储格式。

对矩阵采用何种代数运算也很重要。普通乘法用于统计游走数量;布尔运算用于判断可达性;将加法替换为取最小值、将乘法替换为加法,则可用于某些最短路径计算。因此,将加权邻接矩阵当作无权邻接矩阵处理,或混淆游走与简单路径,都可能导致错误的解释。