图论深度指南

文档概述

图论是研究离散结构中关系的数学分支，其理论在社交网络分析、神经网络、交通路由、推荐系统等人工智能领域有广泛应用。本指南系统介绍图的基本概念、最短路径算法、网络流与匹配、图着色、平面图理论以及谱图理论。

关键词

序号	关键词	英文	核心公式
1	图	Graph	$G=(V,E)$
2	最短路径	Shortest Path	$\min {\sum }_{e\in P}w(e)$
3	Dijkstra算法	Dijkstra’s Algorithm	$O((V+E)\log V)$
4	网络流	Network Flow	$f:E\to {\mathbb{R}}^{+}$
5	最大流最小割	Max-Flow Min-Cut	$\max \Vert f\Vert =\min \text{cap}(S,\bar{S})$
6	匹配	Matching	边集无公共顶点
7	Hall定理	Hall’s Marriage Theorem	$\Vert N(S)\Vert \ge \Vert S\Vert$
8	图着色	Graph Coloring	$\chi (G)$
9	平面图	Planar Graph	无交叉边的图
10	欧拉公式	Euler’s Formula	$V-E+F=2$
11	谱图理论	Spectral Graph Theory	研究邻接矩阵/拉普拉斯算子的特征值
12	拉普拉斯矩阵	Laplacian	$L=D-A$

---

一、图的基本概念

1.1 图的定义与分类

图 $G$ 由顶点集 $V$（或 $V(G)$）和边集 $E$（或 $E(G)$）组成，记作 $G=(V,E)$。

无向图：边没有方向，$(u,v)=(v,u)$。

有向图：边有方向，记作有序对 $⟨u,v⟩$。从 $u$ 指向 $v$。

加权图：每条边关联一个权重 $w:E\to \mathbb{R}$。

基本概念：

• 度（无向图）：顶点 $v$ 的度 $d(v)$ 是与 $v$ 关联的边数
• 出度/入度（有向图）：$d^{+}(v)$ 和 $d^{-}(v)$
• 握手定理：${\sum }_{v\in V}d(v)=2|E|$
• 路径：顶点序列 $v_0,v_1,\dots ,v_k$，相邻顶点间有边
• 环：起点终点相同的路径
• 连通图：任意两顶点间存在路径

图的实例

1. 社交网络：顶点是用户，边是好友关系（无向无权图）
2. 万维网：顶点是网页，边是超链接（有向图）
3. 道路网络：顶点是路口，边是道路，权重是距离或时间
4. 神经网络：顶点是神经元，边是突触连接

1.2 特殊图类

完全图 $K_n$：$n$ 个顶点，每对顶点都有边，$|E|=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$。

二分图 $K_{m,n}$：顶点集可分为两部分 $X,Y$，每条边连接 $X$ 中一点和 $Y$ 中一点。

树：连通无环图，$|E|=|V|-1$。

森林：无环图（树的并）。

正则图：所有顶点度相同。$k$-正则图所有顶点度为 $k$。

平面图：可以画在平面上且边不交叉的图。

1.3 图的矩阵表示

邻接矩阵 $A\in {\mathbb{R}}^{n\times n}$： $A_{ij}=\{\begin{array}{ll}1& \text{若 }(v_i,v_j)\in E\\ 0& \text{否则}\end{array}$

对于加权图，$A_{ij}=w(v_i,v_j)$。

度矩阵 $D$：对角矩阵，$D_{ii}=d(v_i)$。

拉普拉斯矩阵 $L=D-A$：

• 对称正半定：$L⪰0$
• 行和为零：$L1=0$
• 拉普拉斯算子 $L$ 是图上的离散拉普拉斯算子

关联矩阵：对于无向图，$B\in {\mathbb{R}}^{n\times m}$，$B_{v,e}=1$ 若顶点 $v$ 是边 $e$ 的端点。

---

二、最短路径算法

2.1 问题定义

单源最短路径（SSSP）：给定加权图 $G=(V,E,w)$ 和源点 $s$，求 $s$ 到所有其他顶点的最短路径及其长度。

假设：边权重非负（$w(e)\ge 0$）。若无此假设，问题更困难。

2.2 Dijkstra算法

Dijkstra算法是解决非负权图SSSP的经典算法：

初始化：dist[s] = 0，dist[v] = ∞ 对所有 v ≠ s
S = ∅（已确定最短距离的顶点集合）
Q = V（优先队列，按dist排序）

while Q ≠ ∅:
    u = Extract-Min(Q)  // 距离最小的顶点
    S = S ∪ {u}
    for each neighbor v of u:
        if dist[u] + w(u,v) < dist[v]:
            dist[v] = dist[u] + w(u,v)

复杂度：

• 朴素实现：$O(V^2)$
• 使用二叉堆：$O((V+E)\log V)$
• 使用斐波那契堆：$O(E+V\log V)$

正确性证明思路：

• 维护不变式：一旦顶点 $u$ 被加入 $S$，$dist[u]$ 就是 $s$ 到 $u$ 的最短距离
• 反证法：若 $u$ 不是最短的，假设存在更短路径 $P$ 经过 $S$ 外的顶点，矛盾在于 $P$ 必须经过 $S$ 的边界，而边界顶点的距离都 $\ge dist[u]$（因为 $u$ 是最小者）

Dijkstra与BFS的关系

当所有边权重相同时（$w(e)=1$），Dijkstra算法退化为广度优先搜索（BFS），时间复杂度 $O(V+E)$。

2.3 Bellman-Ford算法

Bellman-Ford算法可以处理负权边，并检测负环：

初始化：dist[s] = 0，dist[v] = ∞ 对所有 v ≠ s

for i = 1 to |V| - 1:
    for each edge (u,v) in E:
        if dist[u] + w(u,v) < dist[v]:
            dist[v] = dist[u] + w(u,v)

for each edge (u,v) in E:  // 检测负环
    if dist[u] + w(u,v) < dist[v]:
        报告负环存在

复杂度：$O(VE)$

SPFA（Shortest Path Faster Algorithm）是Bellman-Ford的队列优化版本，实际中通常更快。

2.4 Floyd-Warshall算法

Floyd-Warshall算法解决全对最短路径问题：

初始化：dist[i][j] = w(i,j) 若 (i,j) ∈ E，否则 ∞；dist[i][i] = 0

for k in V:  // 中间顶点
    for i in V:
        for j in V:
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

复杂度：$O(V^3)$

空间优化：可用两行实现（当前行和上一行）。

---

三、匹配与网络流

3.1 匹配的基本概念

匹配（Matching）$M\subseteq E$ 是两两无公共端点的边集。

完美匹配：图中每个顶点都被匹配（即 $|M|=|V|/2$）。

最大匹配：边数最多的匹配。

最大权匹配：边权重之和最大的匹配。

3.2 Hall定理

Hall婚姻定理：设 $G=(X\cup Y,E)$ 是二分图，则存在完美匹配当且仅当对所有 $S\subseteq X$，$|N(S)|\ge |S|$，其中 $N(S)$ 是 $S$ 的邻居集合。

直觉：对于任何 $k$ 个女孩，她们必须认识至少 $k$ 个男孩，否则这 $k$ 个女孩无法全部配对。

Hall定理应用

5个男孩和5个女孩相亲：男孩A认识{1,2}，B认识{2,3}，C认识{3,4}，D认识{4,5}，E认识{5,1}。

检查Hall条件：任意子集S的邻居数≥|S|？

• S={A,B}，N(S)={1,2,3}，|N|=3≥2 ✓
• S={A,B,C}，N(S)={1,2,3,4}，|N|=4≥3 ✓
• …所有子集满足，存在完美匹配。

3.3 网络流

网络流 $(G,s,t,c)$：

• $G=(V,E)$ 是有向图
• $s$ 是源点（只有出流），$t$ 是汇点（只有入流）
• $c:E\to {\mathbb{R}}^{+}$ 是容量函数

可行流 $f$ 满足：

1. 容量约束：$0\le f(e)\le c(e)$
2. 流量守恒：对所有 $v\ne s,t$，${\sum }_{e\text{ into }v}f(e)={\sum }_{e\text{ out of }v}f(e)$

流的值：$|f|={\sum }_{e\text{ out of }s}f(e)-{\sum }_{e\text{ into }s}f(e)$

3.4 最大流最小割定理

割 $(S,\bar{S})$：将顶点划分为两部分，$s\in S$，$t\in \bar{S}$。

割的容量：$c(S,\bar{S})={\sum }_{e\in (S,\bar{S})}c(e)$

最大流最小割定理（Ford-Fulkerson, 1956）：

${\max }_{f\text{ 可行流}}|f|={\min }_{S}c(S,\bar{S})$

即最大流的值等于最小割的容量。

定理的意义

这个定理不仅给出了最大流的上界（任何流的值不超过任何割的容量），还证明了存在某个流和某个割使得等号成立。这是组合优化中最重要的对偶定理之一。

3.5 最大流算法

Ford-Fulkerson方法：反复寻找增广路径（从 $s$ 到 $t$ 的可增广路径）并增加流量。

while 存在增广路径 P:
    找到 P 的最小剩余容量 b
    沿 P 增加 b 单位流量
    更新剩余图

Edmonds-Karp算法：使用BFS寻找最短（边数最少）的增广路径，保证 $O(V{E}^2)$ 时间。

Dinic算法：使用层次图和阻塞流，$O(V^{2}E)$，实际中更快。

---

四、图的着色问题

4.1 色数与基本性质

图着色：用最少的颜色给顶点着色，使得相邻顶点颜色不同。

色数 $\chi (G)$：使图 $G$ 可着色的最少颜色数。

下界：

• $\chi (G)\ge \omega (G)$（最大团大小）
• $\chi (G)\ge \lceil \Delta (G)\rceil$（最大度）

上界（Brooks定理）：对于连通图，如果不是完全图 $K_n$ 也不是奇环，$\chi (G)\le \Delta (G)$。

4.2 平面图着色

四色定理（Appel-Haken, 1977）：

任何平面图都可以用不超过4种颜色着色。

这是图论最著名的定理之一，历史上首个借助计算机证明的主要定理。

五色定理（更简单的证明）：

• 使用归纳法
• 若最小度 $\delta \le 5$，必有可删除的顶点
• 删除顶点，递归着色，再加回顶点

四色定理的实际意义

四色定理保证了地图着色只需要4种颜色——这对于制图学有实际意义。但五色定理的证明更简洁易懂，通常在教学中更受青睐。

4.3 着色算法的复杂度

判断 $\chi (G)=2$：等价于判断图是否为二分图（可检测负环/奇环）。

一般着色问题：NP难。已知最好近似算法保证 $\chi (G)\le O(\frac{\Delta }{\log \Delta }\sqrt{\log \log \Delta })$。

实际算法：回溯搜索 + 分支定界 + 启发式（如DSATUR）可以在中等规模图上找到最优着色。

---

五、平面图与欧拉公式

5.1 平面图的基本性质

平面图：可以在平面上绘制且边不相交（除在顶点处）的图。

Kuratowski定理（平面图的判定）：

图 $G$ 是平面图当且仅当 $G$ 不包含 $K_5$ 或 $K_{3,3}$（或它们的细分）作为子图。

$K_5$（5个顶点的完全图）和 $K_{3,3}$（完全二分图）是平面性的两个”障碍”。

5.2 欧拉公式

欧拉公式（Euler’s Formula）：对于连通平面图，

$V-E+F=2$

其中 $V$ 是顶点数，$E$ 是边数，$F$ 是面数（包括外部无限面）。

推论1：对于平面图，$E\le 3V-6$（当 $V\ge 3$）。

推论2：任何平面图都有度数为5或更小的顶点。

欧拉公式的证明（归纳法）

1. 基础：单个顶点的图，$V=1,E=0,F=1$，公式成立。
2. 归纳：假设对有 $k$ 条边的图成立。添加一条边：
   • 若连接两个现有顶点：$V$ 不变，$E+1$，$F+1$，$V-E+F$ 不变。
   • 若连接顶点与新顶点：$V+1$，$E+1$，$F$ 不变，$V-E+F$ 不变。

5.3 平面图的对偶

对偶图 $G^{\ast }$：对于平面图 $G$，其对偶图 $G^{\ast }$ 的顶点对应 $G$ 的面，$G^{\ast }$ 的边对应 $G$ 中相邻面的边界。

平面图与其对偶图的性质：

• $G$ 的环对应 $G^{\ast }$ 的桥
• $G$ 是连通图当且仅当 $G^{\ast }$ 连通
• $G$ 的欧拉公式可从 $G^{\ast }$ 推导

---

六、谱图理论

6.1 谱图理论的基本框架

谱图理论研究图的矩阵表示（邻接矩阵、拉普拉斯矩阵等）的特征值与图结构的关系。

拉普拉斯矩阵 $L=D-A$：

• $L$ 是对称正半定的
• 特征值：$0={\lambda }_1\le {\lambda }_2\le \cdots \le {\lambda }_n$
• 特征值之和：${\sum }_i{\lambda }_i=\text{tr}(L)={\sum }_{v}d(v)=2m$

拉普拉斯矩阵的特征向量与图的性质密切相关。

6.2 谱与图属性的联系

连通性与谱：

• $G$ 连通 $\iff$ ${\lambda }_2>0$（第二小特征值称为代数连通度）
• ${\lambda }_2$ 越大，$G$ 越”连通得好”

Cheeger不等式： $\frac{\varphi (G)}{2}\le {\lambda }_2\le 2\varphi (G)$

其中 $\varphi (G)$ 是图的Cheeger常数（边缘比），衡量图的连通性。Cheeger不等式将代数连通度与几何连通度联系起来。

完全图的谱：$K_n$ 的拉普拉斯特征值是 $n$（重数 $n-1$）和 $0$（重数1）。

6.3 谱聚类

谱聚类（Spectral Clustering）利用图的拉普拉斯矩阵进行降维和聚类：

算法步骤（无向图上的归一化切割）：

1. 计算相似度矩阵 $W$，度矩阵 $D$
2. 计算归一化拉普拉斯 $L_{sym}=I-D^{-1/2}W{D}^{-1/2}$
3. 取 $k$ 个最小特征值对应的特征向量（或最大的 $k$ 个，若用 $I-L$）
4. 对特征向量组成的矩阵按行聚类（如K-means）

谱聚类的优势

• 不需要凸区域假设（不同于K-means） 可以发现非凸形状的簇
• 计算效率高（只需特征分解）
• 理论基础与图分割的自然目标相关

6.4 拉普拉斯算子与图神经网络

图卷积网络（GCN）的核心操作：

$H^{(l+1)}=\sigma \left({\tilde{D}}^{-1/2}\tilde{A}{\tilde{D}}^{-1/2}{H}^{(l)}{W}^{(l)}\right)$

其中 $\tilde{A}=A+I$（加自环），$\tilde{D}$ 是对应的度矩阵。

这实际上是图的拉普拉斯矩阵的归一化版本，体现了消息传递和邻域聚合的思想。

---

参考文献

1. Diestel, R. (2017). Graph Theory (5th ed.). Springer.
2. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
3. Chung, F. R. K. (1997). Spectral Graph Theory. American Mathematical Society.
4. Bondy, J. A., & Murty, U. S. R. (2008). Graph Theory. Springer.
5. Von Luxburg, U. (2007). A Tutorial on Spectral Clustering. Statistics and Computing, 17(4), 395-416.

---

相关文档

• 线性代数深度指南 - 图矩阵的线性代数基础
• 概率论深度指南 - 马尔可夫链与图模型
• 博弈论基础 - 网络博弈与图结构博弈