想象你是一名城市交通规划师，手里摊开一张城市地图：路口是点，道路是线条。地图很直观，但计算机并不擅长看图形，它只认得数字和表格。为了让计算机理解城市路网，你需要把地图“翻译”成一叠表格账本——哪两个路口之间连着直路？每条道路连接了哪两个路口？从任意路口走到任意路口最短要经过多少条路？这些问题的答案，都能写进一张张矩阵表格里。图论中，把这种“图”变成“矩阵”的过程，就是图的矩阵表示。掌握了它，你就能用矩阵的加减乘除、行列式、特征值等代数武器，回答路径计数、连通性、生成树数量等图论问题，为网络分析、路径规划和人工智能算法打下坚实的数学地基。

岗位关联

对 AI 从业者而言，图结构数据（社交网络、分子结构、知识图谱）无处不在，理解矩阵表示是搭建图神经网络、设计图算法、分析谱聚类等现代 AI 模型的必备素养。

目录
  1. 可视化演示
  2. 矩阵缘起：从城市地图到表格账本
  3. 邻接矩阵：直连道路查询表
  4. 关联矩阵：道路档案表
  5. 距离矩阵：快递里程表
  6. 矩阵幂运算：走 k 步的路径计数
  7. 拉普拉斯矩阵：城市分区账本
  8. 连通性判定：整座城是否连成一片
  9. 生成树计数：最省线路有几种设计
  10. AI 应用场景
  11. Python 演示
  12. 常见误区
  13. 面试题

可视化演示

展示系统处理流水线、实时性能指标曲线及多方案对比分析，包含数据流转、吞吐延迟监控与方案评估。

本节配有交互动效（进入视口后自动加载，约 3KB）。

系统可视化 处理流程：输入→处理→模型→输出 性能监控：实时指标 P=L×T

矩阵缘起：从城市地图到表格账本

拿到一张城市地图，你想把它交给计算机分析，但计算机只认数字表格。于是你把每个路口都编上号，并在账本上按“行、列都是路口编号”的方式记录信息：如果一个表格格子里打勾，就代表这两个路口之间有直连道路。这张打勾的表格，就是图论里将抽象关系“翻译”成数字的工具——矩阵。

在图论中，一张图用顶点集 \(V\) 和边集 \(E\) 描述：顶点是路口，边是道路。把顶点编号后，顶点之间的邻接关系、顶点与边的关联关系、以及两点之间的距离关系，分别对应三种经典矩阵：邻接矩阵、关联矩阵、距离矩阵。它们从不同角度刻画同一个图，就像同一座城市的不同地图——道路图、公交线路图、骑行里程图，各有各的用途。

矩阵表示最大的好处是“代数化”：图上的许多问题可以被转化为矩阵的加减乘除、幂运算、行列式与特征值计算。图论与线性代数由此连接起来，成为网络分析、组合优化、机器学习中图算法的数学基础。

这一节告诉我们：一张图可以完整地写进一张表格。表格的格式怎么设计，就诞生了不同的矩阵——这才是“图的矩阵表示”的起点。

G=(V,E),V={v1,v2,…,vn},E⊆{{u,v}∣u,v∈V}\displaystyle G=(V,E),\quad V=\{v_1,v_2,\dots,v_n\},\quad E\subseteq\{\{u,v\}\mid u,v\in V\}
这个式子用集合语言定义了图的结构：顶点集是“路口清单”，边集是“道路清单”，每一条边连接两个路口。
  1. 顶点集 \(V\)路口编号的集合，是账本的“行标题”来源。
    V={v1,v2,…,vn}\displaystyle V=\{v_1,v_2,\dots,v_n\}
  2. 边集 \(E\)两两路口之间的连接关系，对应账本中打勾的位置。
    E⊆{{u,v}∣u,v∈V}\displaystyle E\subseteq\{\{u,v\}\mid u,v\in V\}
  3. 无序对无向图中 \(\{u,v\}\) 与 \(\{v,u\}\) 表示同一条边，因此用集合而不是有序对。
    {u,v}={v,u}\displaystyle \{u,v\}=\{v,u\}

邻接矩阵：直连道路查询表

如果要在账本上回答“任意两个路口之间有没有直连道路”，最自然的做法是画一张二维表：行和列都按路口编号排列，第 \(i\) 行第 \(j\) 列交叉处的格子填 1，表示第 \(i\) 个路口到第 \(j\) 个路口之间有直接道路；填 0 则表示没有。这样一张“直连道路查询表”就是邻接矩阵。

邻接矩阵 \(A\) 的定义非常直接：当 \((v_i,v_j)\) 是图的边时，\(A_{ij}=1\)；否则 \(A_{ij}=0\)。对无向图来说，从 \(i\) 到 \(j\) 有路和从 \(j\) 到 \(i\) 有路是一回事，所以矩阵关于主对角线对称。对有向图，矩阵不再对称——就像单行道的方向不能乱走。如果道路带长度，还可以用边的权重填充矩阵，得到加权邻接矩阵。

邻接矩阵还藏着图论的密码：无向图中，第 \(i\) 行的元素和等于顶点 \(v_i\) 的度数，也就是这个路口被多少条道路连接；矩阵的对称性告诉我们无向图的边具有双向性；矩阵的元素只有 0 和 1，又让它可以参与矩阵运算与幂运算，为路径计数打下基础。

邻接矩阵就像一张最朴素的“直连查询表”，它回答了图是否存在直接联系，也是后面所有矩阵变换的原料。

Aij={1,(vi,vj)∈E0,其他\displaystyle A_{ij} = \begin{cases} 1, & (v_i,v_j)\in E \\ 0, & \text{其他} \end{cases}
邻接矩阵是“有没有直接道路”的开关矩阵：1 代表直连，0 代表没有直连，但不代表不能绕路到达。
  1. 元素 \(A_{ij}\)第 \(i\) 行第 \(j\) 列的值，表示从路口 \(i\) 到路口 \(j\) 是否一步可达。
    Aij∈{0,1}\displaystyle A_{ij}\in\{0,1\}
  2. 条件为 1只有存在直连边 \((v_i,v_j)\) 时才填 1，像是账本中对应的格子里打勾。
    (vi,vj)∈E⇒Aij=1\displaystyle (v_i,v_j)\in E \Rightarrow A_{ij}=1
  3. 否则为 0没有直连边就填 0；对无向图，\(A_{ij}=A_{ji}\)，账本关于对角线对称。
    Aij=Aji\displaystyle A_{ij}=A_{ji}

关联矩阵：道路档案表

邻接矩阵把注意力放在“点与点”上，而关联矩阵更像一份“道路档案表”：每一行是一个路口，每一列是一条道路，表格记录“某条道路是否与这个路口有关”。在无向图中，如果第 \(i\) 个路口是第 \(j\) 条道路的端点，就在交叉处填 1，否则填 0。由于每条道路恰有两个端点，所以无向关联矩阵的每一列恰好有两个 1。

当图变成有向图，关联矩阵会带上方向信息的正负号：若顶点 \(v_i\) 是边 \(e_j\) 的起点，记 1；若是终点，记 -1；若无关则记 0。这样，每一列恰有一个 1 和一个 -1，就像道路档案上注明“从哪出发、到哪结束”。这个特性让关联矩阵在计算图的秩、分析电路网络时非常好用。

关联矩阵的性质也很有趣：有向图中每一列元素之和为 0，说明一条边从一个点出发、必然到达另一个点；每一行非零元素的个数等于该顶点的度数。矩阵的每一列告诉我们一条边的来龙去脉，所有列合在一起就还原了整张图。

关联矩阵是“边角料视角”的账本：以道路为主线，记录每条道路的两端属性，在电路分析和网络流问题中尤其重要。

Bij={1,vi是边 ej的起点−1,vi是边 ej的终点0,vi与 ej无关联\displaystyle B_{ij} = \begin{cases} 1, & v_i \text{是边 } e_j \text{的起点}\\ -1, & v_i \text{是边 } e_j \text{的终点}\\ 0, & v_i \text{与 } e_j \text{无关联} \end{cases}
关联矩阵用 +1 / -1 把“方向”写进账本：一正一负表示一条路从哪出发、到哪结束。
  1. 起点标记 1若路口 \(v_i\) 是道路 \(e_j\) 的出发点，则 \(B_{ij}=1\)，相当于账本上写“从这里出发”。
    Bij=1  ⟺  vi 是 ej 的起点\displaystyle B_{ij}=1 \iff v_i \text{ 是 } e_j \text{ 的起点}
  2. 终点标记 -1若路口 \(v_i\) 是道路 \(e_j\) 的到达点，则 \(B_{ij}=-1\)，表示“到这里结束”。
    Bij=−1  ⟺  vi 是 ej 的终点\displaystyle B_{ij}=-1 \iff v_i \text{ 是 } e_j \text{ 的终点}
  3. 无关联标记 0路口与道路没有接触时填 0，保证每列元素和为 0。
    ∑i=1nBij=0\displaystyle \sum_{i=1}^{n} B_{ij}=0

距离矩阵：快递里程表

邻接矩阵只告诉你“两个路口有没有直连道路”，但很多时候我们关心的是“从一个路口到另一个路口最少要走多少路”。想象快递公司要制作一张里程表：表格的行列都是站点，格子里填写两站之间的最短行驶距离。这张“快递里程表”就是距离矩阵。

距离矩阵 \(D\) 的元素 \(D_{ij}\) 定义为顶点 \(v_i\) 到 \(v_j\) 的最短路径长度（按无权图的边数计算，或按带权图的权重和计算）。如果从 \(i\) 到 \(j\) 根本不可达，就记作无穷大 \(\infty\)。对无向图，距离矩阵是对称的；并且它天然满足三角不等式：直接从 \(i\) 到 \(j\) 的绕路距离，不会超过先经过某个中转站 \(k\) 再出发的距离。

距离矩阵与邻接矩阵的本质区别在于：邻接矩阵只记录“一步到达”的直连关系，距离矩阵则记录“全局最优”的路径距离。计算距离矩阵通常使用 Floyd-Warshall 或 Dijkstra 等最短路径算法，而不是简单地把邻接矩阵乘几次。

距离矩阵把“最短路径”这个动态规划问题固化成一张静态表格——查询方便，且天然满足三角不等式，为路径规划算法提供了有力工具。

Dij=min⁡{ℓ(P)∣P 是从 vi 到 vj 的路径}(不可达时为 ∞)\displaystyle D_{ij} = \min\{\ell(P)\mid P\text{ 是从 } v_i \text{ 到 } v_j \text{ 的路径}\} \quad(\text{不可达时为 }\infty)
距离矩阵回答“最少要走多少路”，把图上的最短路径问题变成一张可查的里程表。
  1. 路径集合 \(P\)从 \(v_i\) 到 \(v_j\) 可能有许多条路线，先收集所有路线。
    P={P∣P 连接 vi 与 vj}\displaystyle \mathcal{P}=\{P \mid P\text{ 连接 } v_i \text{ 与 } v_j\}
  2. 取最小值在所有路线长度中挑最短的那个，作为 \(D_{ij}\)。
    Dij=min⁡P∈Pℓ(P)\displaystyle D_{ij}=\min_{P\in\mathcal{P}} \ell(P)
  3. 不可达为无穷若不存在任何路径，就记 \(\infty\)，表示账本上“无法送达”。
    Dij=∞  ⟺  vj 从 vi 不可达\displaystyle D_{ij}=\infty \iff v_j \text{ 从 } v_i \text{ 不可达}

矩阵幂运算：走 k 步的路径计数

邻接矩阵记录了“一步直达”的关系，那么问题来了：从路口 \(i\) 出发，恰好走 \(k\) 步到达路口 \(j\)，一共有多少种走法？答案藏在矩阵连乘里！把邻接矩阵 \(A\) 自乘 \(k\) 次，得到 \(A^k\)，它的第 \(i\) 行第 \(j\) 列元素 \((A^k)_{ij}\) 就是长度为 \(k\) 的“漫游”（walk）数量。

为什么矩阵乘法能数路径？回顾矩阵乘法法则：\((A^2)_{ij} = \sum_{t} A_{it}A_{tj}\)。这里的求和遍历所有中间路口 \(t\)。如果 \(i\to t\) 有路且 \(t\to j\) 有路，那么乘积为 1，就贡献一条“走两步”的走法。推广到 \(k\) 步，就对所有可能的中间顶点序列求和，每一步的边存在性相乘。注意，这里允许中间顶点重复经过，所以叫 walk 而非严格路径（path）。

这个发现非常实用：通过计算 \(A^k\)，我们可以知道一个社交网络中 k 度好友的数量，或者交通路网中 k 步通勤的方案数。更进一步，把第 0 步到第 \(n-1\) 步的结果都用布尔逻辑合并，还能得到“可达矩阵”，用于判断任意两点之间是否存在路径。

矩阵幂计数让我们用纯代数方法数出“步数受限”的路线方案，这是从静态表示走向动态分析的关键一步。

(Ak)ij=∑t1=1n∑t2=1n⋯∑tk−1=1nAit1At1t2⋯Atk−1j\displaystyle (A^k)_{ij} = \sum_{t_1=1}^{n}\sum_{t_2=1}^{n}\cdots\sum_{t_{k-1}=1}^{n} A_{i t_1} A_{t_1 t_2} \cdots A_{t_{k-1} j}
矩阵幂的每个元素都在数“走几步的路线条数”：每一步中间站点被求和，乘积为 1 时表示一条可行的中转路线。
  1. 矩阵乘法本质\((A^2)_{ij}\) 是“先走一步到某个中间点，再走一步到终点”的路线总和。
    (A2)ij=∑t=1nAitAtj\displaystyle (A^2)_{ij}=\sum_{t=1}^{n} A_{it}A_{tj}
  2. 迭代相乘\(A^k = A^{k-1}A\)，每乘一次就多走一步，中间节点层层展开。
    Ak=Ak−1A\displaystyle A^k = A^{k-1}A
  3. 求和覆盖所有中间序列对 \(t_1,t_2,\dots,t_{k-1}\) 全部求和，每一项对应一条长度为 \(k\) 的 walk。
    ∑t1,…,tk−1Ait1At1t2⋯Atk−1j\displaystyle \sum_{t_1,\dots,t_{k-1}} A_{i t_1}A_{t_1 t_2}\cdots A_{t_{k-1}j}

拉普拉斯矩阵：城市分区账本

城市规划师经常要回答：整个城市是否连成一片？能不能划分成几个相对独立的片区？如果把每个路口的度数（直连道路数量）放在对角线上，再减去邻接矩阵，就得到一张特殊的账本——拉普拉斯矩阵 \(L = D - A\)。它的每一行和为 0，许多性质都藏着图的结构信息。

拉普拉斯矩阵的定义非常简洁：\(D\) 是度对角矩阵，对角线上是每个顶点的度数，其余元素为 0；\(A\) 是邻接矩阵。两者相减后，对角线位置 \(L_{ii}\) 等于 \(v_i\) 的度数，非对角线位置 \(L_{ij}\) 等于 \(-A_{ij}\)。这个矩阵是半正定的，所有特征值非负，且最小特征值一定是 0。

拉普拉斯矩阵的特征值被称为图的谱，它刻画了图的整体形状。0 特征值的重数恰好等于图中连通分量的个数：如果图只有一个连通分量，0 特征值只出现一次；如果城市被河流分成两个不相连的片区，0 特征值就会出现两次。谱图理论还通过第二个小特征值（Fiedler 值）指导图分割，常用于聚类算法。

拉普拉斯矩阵是谱聚类、图神经网络、图像分割等 AI 算法中绕不开的核心工具，它的特征值就是图的“心电图”。

L=D−A,Dii=deg⁡(vi),Dij=0 (i≠j)\displaystyle L = D - A,\qquad D_{ii}=\deg(v_i),\quad D_{ij}=0\ (i\neq j)
拉普拉斯矩阵把“拥挤度”和“邻居关系”写进同一本账：对角线记自己的度数，非对角线记是否需要减去邻居连接。
  1. 度对角矩阵 \(D\)只有对角线有值，\(D_{ii}\) 等于顶点 \(v_i\) 的度数，其余为 0。
    Dii=deg⁡(vi)\displaystyle D_{ii}=\deg(v_i)
  2. 减去邻接矩阵用度数对角阵减去邻接矩阵，得到非对角线上的负邻居关系。
    Lij={deg⁡(vi),i=j−1,vi 与 vj 相邻0,其他\displaystyle L_{ij} = \begin{cases} \deg(v_i), & i=j\\ -1, & v_i \text{ 与 } v_j \text{ 相邻}\\ 0, & \text{其他}\end{cases}
  3. 行和为零\(\deg(v_i)\) 减去若干个 -1 的和恰好抵消，所以每一行元素之和为 0。
    ∑j=1nLij=0\displaystyle \sum_{j=1}^{n} L_{ij}=0

连通性判定：整座城是否连成一片

拿到一张城市地图，我们首先想知道：从任意一个路口出发，能不能到达所有其他路口？若把所有可能存在路径的信息汇总成一张“可达矩阵” \(P\)，其中 \(P_{ij}=1\) 表示 \(v_i\) 可以到达 \(v_j\)，那么判断整张图是否连通，就变成了检查 \(P\) 中是否存在 0。

如何构造可达矩阵？利用矩阵幂的思想：在邻接矩阵 \(A\) 中加上单位阵 \(I\)（表示原地不动、走 0 步），然后计算 \((A+I)^{n-1}\)。只要存在一条长度不超过 \(n-1\) 的 walk 从 \(i\) 到 \(j\)，\((A+I)^{n-1}\) 对应元素就大于 0。再经过“非零取 1”的符号函数处理，就得到只含 0/1 的可达矩阵。更高效的实现是 Warshall 算法，用三重循环在布尔坐标系下闭包传递。

连通性判定不只回答“是否连通”，还能数出连通分量数：可达矩阵可以按行划分出互达的等价类，每个等价类就是一个连通分量。这与拉普拉斯矩阵零特征值重数的结论互为印证——一个从账本看结构，一个从路径看关系。

连通性判定是图论中“全局视角”的基础操作，无论是排查网络断点，还是验证知识图谱中实体之间是否存在联系，都离不开它。

P=sign⁡((A+I)n−1)\displaystyle P = \operatorname{sign}\left((A+I)^{n-1}\right)
可达矩阵是整个城市“能到哪”的总账：\((A+I)\) 允许原地停留，幂运算扩展步数，sign 把正数统一写成 1。
  1. 加单位阵 \(I\)给每个顶点加上“走 0 步”的自环，使矩阵幂可以覆盖长度小于 \(n-1\) 的路径。
    (A+I)ij={1,i=jAij,i≠j\displaystyle (A+I)_{ij}=\begin{cases}1,& i=j\\ A_{ij},& i\neq j\end{cases}
  2. 计算 \(n-1\) 次幂图有 \(n\) 个顶点时，任意简单路径长度至多 \(n-1\)，所以幂次足够覆盖所有可达关系。
    (A+I)n−1\displaystyle (A+I)^{n-1}
  3. 符号函数取 0/1把幂结果中的正数全部变为 1，得到真正的可达矩阵。
    sign⁡(x)={0,x=01,x>0\displaystyle \operatorname{sign}(x)=\begin{cases}0,& x=0\\ 1,& x>0\end{cases}

生成树计数：最省线路有几种设计

如果要在城市里铺设通信光缆，要求用最少的线路把所有路口连成一个整体（不允许成环），这样的设计方案就是图的生成树。一个有趣的问题来了：这样的“最省网络”总共有多少种设计？答案再次藏在拉普拉斯矩阵里，这就是著名的矩阵树定理（Kirchhoff's Matrix-Tree Theorem）。

矩阵树定理说：对于无向连通图，其生成树的数量等于拉普拉斯矩阵 \(L\) 删去任意一行一列后得到的矩阵 \(L_0\) 的行列式 \(\det(L_0)\)。为什么这么神奇？这背后的代数原因是拉普拉斯矩阵所有“第一余子式”相等，而行列式恰好统计了所有包含 \(n-1\) 条边且无环的连通子图数量。无论你删掉哪一行哪一列，结果都一样——就像无论从哪个路口开始规划，能连成一片的方案总数不变。

有了矩阵树定理，计算生成树数量不必暴力枚举所有边的子集，只需一次行列式运算。这在电路网络的独立回路数分析、化学分子结构的同分异构体计数等问题中有广泛应用。

生成树计数让“最省网络设计”从组合枚举问题变成线性代数计算，这是图论与矩阵结合的最好范例之一。

τ(G)=det⁡(L0)\displaystyle \tau(G)=\det(L_0)
矩阵树定理把“数生成树”变成“算行列式”：删掉拉普拉斯矩阵任意一行一列，再求行列式，就得到生成树数量。
  1. 删去一行一列对拉普拉斯矩阵 \(L\)，去掉第 \(r\) 行和第 \(r\) 列，得到 \((n-1)\times(n-1)\) 的子矩阵。
    L0=L 删去第 r 行第 r 列\displaystyle L_0 = L\text{ 删去第 }r\text{ 行第 }r\text{ 列}
  2. 计算行列式子矩阵的行列式是一个数值，它统计了生成树的个数。
    τ(G)=det⁡(L0)\displaystyle \tau(G)=\det(L_0)
  3. 任意行任意列矩阵树定理保证删除的 \(r\) 不影响结果，因为所有代数余子式相等。
    det⁡(L0) 与 r 无关\displaystyle \det(L_0) \text{ 与 } r \text{ 无关}

AI 应用场景

社交网络中的好友推荐

阶段：特征工程 / 图神经网络聚合

解决的问题：传统推荐只看一对一好友关系，无法感知“朋友的朋友”这类二阶关系。用邻接矩阵 \(A\) 表示用户关注关系，计算 \(A^2\) 就能找出所有二度好友及其共同好友数量，作为推荐特征引入模型。

具体案例：某社交 App 用 \(A^2\) 提取“二度人脉计数”特征，再结合图神经网络聚合邻居信息，显著提升了新用户好友推荐准确率。

城市配送路径规划

阶段：算法设计 / 组合优化

解决的问题：物流配送需要查询任意两个配送点之间的最短距离，传统做法每次临时跑最短路径，耗时巨大。预计算距离矩阵后，查询 \(D_{ij}\) 只需 \(O(1)\) 时间，AI 路径优化算法可以快速评估成百上千种配送顺序。

具体案例：某快递公司在 5000 个配送点的路网上预计算距离矩阵，配合启发式搜索算法规划每日派送顺序，将平均配送里程缩短了 12%。

分子活性预测中的谱特征

阶段：分子表示学习 / 图卷积

解决的问题：药物分子可以表示为原子为点、化学键为边的图。直接输入图结构给卷积网络较难捕捉全局连通性，而拉普拉斯矩阵的特征值（谱）蕴含分子连通模式。

具体案例：在 AI 制药项目中，研究员将分子图的拉普拉斯矩阵特征值作为全局特征，拼接到图神经网络的节点特征上，用于预测化合物对靶点的抑制活性，模型 AUC 提升了约 5%。

Python 演示

python29 行
import numpy as np def adjacency_matrix(n, edges):    A = np.zeros((n, n), dtype=int)    for u, v in edges:        A[u][v] = 1        A[v][u] = 1    return A def path_counts(A, k):    return np.linalg.matrix_power(A, k) def laplacian(A):    D = np.diag(A.sum(axis=1))    return D - A def spanning_trees(L):    L0 = L[:-1, :-1]    return round(np.linalg.det(L0)) if __name__ == '__main__':    n = 4    edges = [(0, 1), (1, 2), (2, 3), (3, 0), (0, 2)]    A = adjacency_matrix(n, edges)    print("邻接矩阵:\n", A)    print("两步路径数:\n", path_counts(A, 2))    L = laplacian(A)    print("拉普拉斯矩阵:\n", L)    print("生成树数量:", spanning_trees(L))
目的：用 NumPy 实现图的邻接矩阵、矩阵幂路径计数、拉普拉斯矩阵和矩阵树定理生成树计数，展示图论代数化的核心操作。
  1. A = np.zeros((n, n), dtype=int)先创建一张全 0 的表格，行和列代表顶点编号。
  2. A[u][v] = 1在表格对应位置填入 1，表示顶点 u 到 v 有直连边。
  3. np.linalg.matrix_power(A, k)计算邻接矩阵的 k 次幂，每个元素是从某个顶点到另一个顶点走 k 步的路径数。
  4. np.diag(A.sum(axis=1))统计每个顶点的度数（每行非零元素个数），构造成度对角矩阵 D。
  5. D - A用度对角矩阵减去邻接矩阵，得到拉普拉斯矩阵。
  6. L[:-1, :-1]删除最后一行和最后一列，得到子矩阵 L0。
  7. np.linalg.det(L0)计算行列式，输出生成树数量，实现矩阵树定理。

常见误区

误区邻接矩阵里很多 0，说明两个点之间没有路，所以距离矩阵也应该是 0 或没有意义，反正都是“到不了”。

正解邻接矩阵的 0 只表示“没有直连边”，但两个点之间可能通过绕行其他点到达。距离矩阵的无穷大才表示彻底不可达。就像两个小区之间没有直达公交，但可以换乘到达，邻接矩阵记 0，距离矩阵记的是换乘后的最短里程数。

为何常见：初学者只看到矩阵里都是数字，忽略了不同矩阵的语义载体不同，把“无直连”和“不可达”错误等价。

误区\(A^k_{ij}\) 就是从 i 到 j 经过 k 条不同道路、且每个路口都不重复走的方案数。

正解\(A^k_{ij}\) 计算的是允许顶点重复出现的 walk 数量，不是简单路径。比如 i→k→i→j 这样走 3 步，中间回到了 i，在简单路径中不允许，但在 walk 计数中完全合法。因此矩阵幂得到一个可能大于 1 的整数，不能直接用于简单路径枚举。

为何常见：生活里“走路”通常默认不绕回原地，而矩阵乘法只关心每步的边是否存在，不检查顶点是否重复。

误区拉普拉斯矩阵对角线是度数，所以矩阵每一行的和就应该是那个顶点的度数。

正解拉普拉斯矩阵 \(L=D-A\)，对角线的度数是正贡献，但非对角线还包含了与所有邻居相连的 -1，两者相加恰好抵消。因此每一行元素之和为 0，而不是度数。行和为 0 是拉普拉斯矩阵最显著的特征之一。

为何常见：只盯着对角线上的大数，忽略非对角线上的负号，缺少对矩阵整体结构的观察。

误区矩阵树定理计算生成树数时，必须先删除第 1 行第 1 列，删别的位置结果就不对了。

正解对连通图的拉普拉斯矩阵，删去任意一行一列后得到的代数余子式都相等，都等于生成树数。选择删除哪一行哪一列是自由的，只是为了计算方便常选最后一行最后一列。

为何常见：教材举例总以删第一行第一列呈现，容易让读者误以为只有这一种操作合法。

面试题

Q1. 邻接矩阵中第 \(i\) 行第 \(j\) 列为 1，通常表示什么？

单选题 · easy

  • A.从 i 到 j 有边← 正确答案
  • B.i 到 j 距离为 1 公里
  • C.i 与 j 是同一个顶点
  • D.图是有向图

答案：A。邻接矩阵只记录“是否存在直连边”，不是距离、不是顶点编号比较，也不决定有向图属性。无向图和有向图都可以用邻接矩阵表示，区别在于是否对称。

Q2. 无向图的邻接矩阵具有什么结构性质？

单选题 · easy

  • A.沿主对角线对称← 正确答案
  • B.反对称
  • C.对角元素全为 1
  • D.每行元素和为 0

答案：A。无向图中 \(i\) 到 \(j\) 有边等价于 \(j\) 到 \(i\) 有边，因此 \(A_{ij}=A_{ji}\)，矩阵对称。反对称要求 \(A_{ij}=-A_{ji}\)，对角全为 1 只在自环存在时成立，行和为 0 更不可能，因为行和是度数。

Q3. 在无负权有向图中，距离矩阵的对角线元素 \(D_{ii}\) 恒为？

单选题 · easy

  • A.0← 正确答案
  • B.无穷大
  • C.1
  • D.无法确定

答案：A。从顶点出发回到自身，最短路径长度为 0（原地不动）。只要没有负权环，绕行一圈回到自身的距离必然大于 0，不会小于 0。

Q4. 邻接矩阵 \(A\) 的平方 \((A^2)_{ij}\) 表示什么？

单选题 · mid

  • A.从 i 到 j 恰好走 2 步的 walk 数量← 正确答案
  • B.从 i 到 j 的最短路径长度
  • C.i 与 j 之间的边数
  • D.i 到 j 的可达性标记

答案：A。矩阵乘法 \((A^2)_{ij}=\sum_t A_{it}A_{tj}\) 对中间顶点 \(t\) 求和，每一项表示 i→t→j 经过 2 步的一条 walk。它不等于最短路径长度，也不是简单边的数量。

Q5. 关于关联矩阵，下列哪些说法正确？

多选题 · mid

  • A.无向图每列恰有两个 1← 正确答案
  • B.有向图每列一个 1 和一个 -1← 正确答案
  • C.无向图每行只有一个 1
  • D.有向图每行至少一个 -1

答案：AB。无向边有两个端点，因此每列恰好两个 1；有向边有起点和终点，因此每列一个 1 一个 -1。一个顶点可以连接多条边，所以每行可以有多个 1；孤立顶点没有关联边，所以不一定有 -1。

Q6. 拉普拉斯矩阵 \(L=D-A\) 的每一行元素之和为？

单选题 · mid

  • A.0← 正确答案
  • B.该行度数
  • C.1
  • D.图的边数

答案：A。对角线元素等于度数，非对角线把每个邻居对应的 -1 加起来，总和正好抵消为 0。这是拉普拉斯矩阵的核心性质，也是 0 特征值存在的直接原因。

Q7. 设图 G 的拉普拉斯矩阵删去第 r 行第 r 列后的行列式为 5，则 G 的生成树数量为？

单选题 · hard

  • A.5← 正确答案
  • B.10
  • C.无法确定
  • D.0

答案：A。矩阵树定理指出，连通图的生成树数量等于拉普拉斯矩阵删去任意一行一列后的行列式。因此删去第 r 行第 r 列行列式为 5，生成树数量就是 5。

Q8. 以下哪些矩阵可以直接或间接用于判定图是否连通？

多选题 · mid

  • A.可达矩阵 \(P=\operatorname{sign}((A+I)^{n-1})\)← 正确答案
  • B.距离矩阵中是否存在无穷大← 正确答案
  • C.拉普拉斯矩阵零特征值的重数← 正确答案
  • D.邻接矩阵所有元素之和

答案：ABC。可达矩阵所有元素非零说明任意两点可达；距离矩阵没有无穷大说明不存在不可达对；拉普拉斯矩阵零特征值重数为 1 说明只有一个连通分量。邻接矩阵元素之和只反映总边数，无法判断边是否连接成整体，因此不能判定连通性。

Q9. 关于邻接矩阵的幂，正确的是？

多选题 · hard

  • A.\((A^k)_{ij}\) 表示从 i 到 j 长度为 k 的 walk 数量← 正确答案
  • B.计数时允许中间顶点重复出现← 正确答案
  • C.\((A^k)_{ij}\) 一定是 0 或 1
  • D.它不能直接计数简单路径（顶点不重复的路径）← 正确答案

答案：ABD。矩阵幂展开后每个求和项对应一条长度为 k 的顶点序列，序列允许重复顶点，所以是 walk 计数而非简单路径计数。由于多条 walk 可能到达同一终点，计数结果可能大于 1，因此 C 错误。

Q10. 对连通图 G 的拉普拉斯矩阵 L，删除任意一行一列得到 L0，则 \(\det(L_0)\)：

单选题 · extreme

  • A.与删去的行和列无关← 正确答案
  • B.仅与删去的行有关
  • C.等于邻接矩阵的行列式
  • D.等于顶点数的阶乘

答案：A。矩阵树定理的关键结论就是拉普拉斯矩阵的所有第一余子式相等，因此删去任意一行一列后行列式都等于生成树数量，与选择无关。C、D 显然不符合定义。