机器学习数学基础 120 章

图、节点、边、路径、连通与树

层级：B｜建议先修：01-03、01-04、05-05

图论提供了一种描述“对象及对象之间关系”的语言。决策树、概率图模型、聚类、图神经网络和网络分析都以图为基础。

1. 图的定义

图记为

G=(V,E),G=(V,E),

其中 VV 是节点（顶点）集合，EE 是边集合。节点表示对象，边表示两个对象之间存在某种关系。

  • 无向图的边写作 {u,v}\{u,v\}；
  • 有向图的边写作 (u,v)(u,v) 或 u→vu\to v；
  • 加权图给每条边附加权重 w(u,v)w(u,v)；
  • 简单图没有自环和重复边。

2. 邻接、邻居与度

在无向图中，若 {u,v}∈E\{u,v\}\in E，称 u,vu,v 相邻。节点 vv 的邻居集合为

N(v)={u:{u,v}∈E}.N(v)=\{u:\{u,v\}\in E\}.

节点的度为相连边数：

deg⁡(v)=∣N(v)∣.\deg(v)=|N(v)|.

无向图满足握手定理：

∑v∈Vdeg⁡(v)=2∣E∣.\sum_{v\in V}\deg(v)=2|E|.

有向图区分入度和出度，且所有节点的入度和与出度和都等于边数。

3. 走法、路径与环

从 v0v_0 到 vkv_k 的走法是相邻节点序列。若节点不重复，通常称为简单路径。路径长度可以指边数，也可以指边权之和。

若路径首尾相同且中间节点不重复，就构成环。无环图是不含环的图；有向无环图简称 DAG。

4. 连通性

无向图中，若任意两点间都存在路径，则图连通。若不连通，可分解成若干最大连通子图，称为连通分量。

有向图中：

  • 强连通：任意两点相互都有有向路径；
  • 弱连通：忽略边方向后连通。

在聚类中，连通分量可以直接形成簇；在图搜索中，不连通意味着某些状态无法相互到达。

5. 子图、团与独立集

从部分节点和边形成的图称为子图。若一组节点中任意两点都相连，该集合称为团。无向概率图模型的因子常定义在团上。

若一组节点之间没有边，则称为独立集。注意图论的“独立集”和概率论的“独立”是不同概念。

6. 树与森林

树是连通且无环的无向图。若树有 nn 个节点，则恰有 n−1n-1 条边，并且任意两节点之间只有一条简单路径。

森林是若干棵互不相连的树。树的这些性质使递归、动态规划和消息传递非常高效。

根树指定一个根节点，并产生父节点、子节点、祖先、后代、深度和叶节点等概念。机器学习的决策树就是根树：内部节点执行判断，叶节点给出预测。

7. 生成树

连通无向图的生成树包含原图全部节点，但只保留足以连通它们的 n−1n-1 条边。若边有代价，总代价最小的生成树称为最小生成树，可用于层次聚类、网络设计等。

8. 图的矩阵表示

对 nn 个节点，邻接矩阵 A∈Rn×nA\in\mathbb R^{n\times n} 定义为

Aij={1,(i,j)∈E,0,否则.A_{ij}=\begin{cases} 1,&(i,j)\in E,\\ 0,&\text{否则}. \end{cases}

加权图中可用边权替代 1。无向图的邻接矩阵对称。有向图一般不对称。

度矩阵 DD 是对角矩阵，Dii=deg⁡(i)D_{ii}=\deg(i)。图 Laplacian 为

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

它是半正定矩阵，零特征值的重数等于连通分量数，是谱聚类和图正则化的基础。

9. 图的遍历

  • 深度优先搜索（DFS）沿一条路径尽量深入，再回溯；
  • 广度优先搜索（BFS）按离起点的边数逐层展开。

在无权图中，BFS 可求最短边数路径；DFS 常用于环检测、连通分量和拓扑排序。

10. 机器学习联系

  • 决策树与随机森林：根树结构；
  • Bayesian 网络：有向无环图；
  • Markov 随机场：无向图；
  • 谱聚类：Laplacian 的特征向量；
  • 图神经网络：在邻居间聚合消息；
  • 层次聚类：树状图表示簇合并过程。

11. 易错点

  1. “树”默认通常指无向连通无环图；有向根树需额外说明方向。
  2. 路径长度不一定等于边数，加权图中常取权重和。
  3. 邻接矩阵的行列含义在有向图中必须先约定。
  4. 图中没有边不自动等于概率独立；只有在指定概率图语义后才可解释。

常见问答

Q1：为什么树有 n−1n-1 条边？
从单节点开始，每加入一个新节点，为保持连通且不成环只能加一条边，因此总共 n−1n-1 条。

Q2：树上任意两点为何只有一条路径？
若存在两条不同路径，它们合在一起会形成环，与树无环矛盾。

Q3：图 Laplacian 为什么重要？
它把图的连接结构转化为二次型和谱信息，例如 xTLx=12∑ijAij(xi−xj)2\mathbf x^TL\mathbf x=\tfrac12\sum_{ij}A_{ij}(x_i-x_j)^2，衡量相邻节点取值的不平滑程度。

Q4：概率图模型中的节点一定代表随机变量吗？
通常如此；因子图还包含因子节点。具体语义取决于图模型类型。

练习

  1. 证明无向图所有节点度数之和为边数的两倍。
  2. 一个有 8 个节点的树有多少条边？删除任意一条边会怎样？
  3. 写出三节点链 1−2−31-2-3 的邻接矩阵、度矩阵和 Laplacian。
  4. 解释为什么 BFS 能求无权图最短路径。

答案与提示

  1. 每条边恰好给两个端点各贡献 1 次度数。
  2. 7 条；删除任意一条边都会变成两个连通分量。
  3. A=[010101010]A=\begin{bmatrix}0&1&0\\1&0&1\\0&1&0\end{bmatrix}，D=diag⁡(1,2,1)D=\operatorname{diag}(1,2,1)，L=D−AL=D-A。
  4. BFS 按路径边数从小到大首次访问节点，首次到达时不可能存在更短未探索路径。