图论深度指南

文档概述

图论是研究离散结构中关系的数学分支，其理论在社交网络分析、神经网络、交通路由、推荐系统、知识图谱、分子生物学等人工智能领域有广泛应用。本指南系统介绍图的基本概念与分类、最短路径算法（Dijkstra、Bellman-Ford、Floyd-Warshall、A*）、网络流与匹配（最大流最小割、完美匹配）、图的着色问题、平面图与拓扑图论、谱图理论，以及图神经网络（GNN、GCN、GraphSAGE、GAT）的数学基础。附录包含极值图论、随机图、图算法复杂度分类、拟阵理论等高级专题。

---

关键词

序号	关键词	英文	核心公式
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$
13	邻接矩阵	Adjacency Matrix	$A_{ij}=1$ 若 $(i,j)\in E$
14	树	Tree	连通无环图，$
15	欧拉回路	Eulerian Circuit	遍历每条边恰好一次的回路
16	哈密顿回路	Hamiltonian Circuit	遍历每个顶点恰好一次的回路
17	割集	Cut Set	删除后使图不连通的最小边集
18	生成树	Spanning Tree	包含所有顶点的树
19	强连通分量	SCC	有向图中相互可达的顶点集
20	拓扑排序	Topological Sort	DAG 顶点的线性排序

---

一、图的基本概念

1.1 图的定义与分类

图 $G$ 由顶点集 $V$（或 $V(G)$）和边集 $E$（或 $E(G)$）组成，记作 $G=(V,E)$。每条边连接一个或两个顶点。

无向图：边没有方向，$(u,v)=(v,u)$。如果一条边恰好连接两个顶点，我们称这两个顶点相邻（adjacent），这两个顶点都与该边关联（incident）。

有向图（Digraph）：边有方向，记作有序对 $⟨u,v⟩$，表示从 $u$ 指向 $v$ 的弧（arc）。$u$ 是弧尾（tail），$v$ 是弧头（head）。

混合图：同时包含无向边和有向边的图。

加权图：每条边关联一个权重 $w:E\to \mathbb{R}$。权重可以表示距离、时间、成本、容量等物理量。

超图：一条边可以连接任意数量（$\ge 2$）的顶点。

基本概念：

• 度（无向图）：顶点 $v$ 的度 $d(v)$ 是与 $v$ 关联的边数（注意：环计算两次）
• 出度/入度（有向图）：$d^{+}(v)$ 和 $d^{-}(v)$ 分别是出发和进入 $v$ 的弧数
• 握手定理（Handshaking Lemma）：${\sum }_{v\in V}d(v)=2|E|$。这意味着度数为奇数的顶点必为偶数个。
• 路径：顶点序列 $v_0,v_1,\dots ,v_k$，相邻顶点间有边
• 环（Cycle）：起点终点相同的路径，长度至少为3（简单环）
• 连通图：任意两顶点间存在路径
• 子图：$G^{\prime }=(V^{\prime },E^{\prime })$ 满足 $V^{\prime }\subseteq V$ 且 $E^{\prime }\subseteq E$（且关联顶点属于 $V^{\prime }$）

图的实例

1. 社交网络：顶点是用户，边是好友关系（无向无权图）
2. 万维网：顶点是网页，边是超链接（有向图，入度/出度不对称）
3. 道路网络：顶点是路口，边是道路，权重是距离或时间（加权无向图）
4. 神经网络：顶点是神经元，边是突触连接（有权有向图）
5. 分子图：顶点是原子，边是化学键
6. 知识图谱：实体为顶点，关系为边（多关系有向图）
7. 交通流网络：顶点是路口，边是道路，权重是容量（网络流模型）

自环：连接顶点到自身的边 $(v,v)$。

重边：两个顶点之间有多条边（多重边），含重边的图称为多重图（multigraph），不含重边的图称为简单图（simple graph）。

1.2 特殊图类

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

二分图（Bipartite Graph）：顶点集可分为两部分 $X,Y$，每条边恰好连接 $X$ 中一点和 $Y$ 中一点。记作 $G=(X\cup Y,E)$。

完全二分图 $K_{m,n}$：$|X|=m$，$|Y|=n$，所有 $mn$ 条可能的边都存在。

树：连通无环图。等价定义：

• $|E|=|V|-1$ 的连通图
• 无环且添加任意一条边后恰好产生一个环
• 任意两点间有唯一路径的连通图

森林：无环图（树的并）。若有 $c$ 个连通分量，则 $|E|=|V|-c$。

正则图：所有顶点度相同。$k$-正则图所有顶点度为 $k$。正则图在谱图理论中有重要地位。

平面图：可以画在平面上且边不交叉（除在顶点处）的图。这是图论中历史最悠久的研究方向之一。

补图：给定图 $G$，其补图 $\bar{G}$ 的顶点集与 $G$ 相同，边集为所有不在 $G$ 中的顶点对。

笛卡尔积：两个图的笛卡尔积 $G\square H$ 的顶点集为 $V(G)\times V(H)$，$(u,v)$ 与 $(u^{\prime },v^{\prime })$ 相邻当且仅当 $u=u^{\prime }$ 且 $(v,v^{\prime })\in E(H)$，或 $v=v^{\prime }$ 且 $(u,u^{\prime })\in E(G)$。超立方体图 $Q_n$ 是 $K_2$ 与自身的 $n$ 次笛卡尔积。

1.3 图的矩阵表示

图的代数研究依赖于其矩阵表示。设图 $G$ 有 $n=|V|$ 个顶点。

邻接矩阵 $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}=1$ 表示从 $i$ 到 $j$ 的弧。对于加权图，$A_{ij}=w(v_i,v_j)$（无边时为 0 或 $\infty$）。

• 无向图的邻接矩阵是对称的：$A=A^T$
• $A$ 的行和等于对应顶点的出度，列和等于入度
• $A^k$ 的 $(i,j)$ 元素等于从 $v_i$ 到 $v_j$ 的长度为 $k$ 的路径数量

度矩阵 $D$：对角矩阵，$D_{ii}=d(v_i)$（对于有向图可分出度阵和入度阵）。

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

• 对称正半定：$L⪰0$（所有特征值 $\ge 0$）
• 行和为零：$L1=0$（零是 $L$ 的特征值，对应特征向量 $1=(1,1,\dots ,1{)}^T$）
• $L$ 是图上的离散拉普拉斯算子的矩阵形式
• 对于加权图，$L_{ii}={\sum }_j{w}_{ij}$，$L_{ij}=-w_{ij}$（$i\ne j$ 时）

归一化拉普拉斯矩阵： $L_{sym}=D^{-1/2}L{D}^{-1/2}=I-D^{-1/2}A{D}^{-1/2}$ $L_{rw}=D^{-1}L=I-D^{-1}A\text{（随机游走拉普拉斯）}$

关联矩阵：对于无向图，$B\in {\mathbb{R}}^{n\times m}$（$m=|E|$），$B_{v,e}=1$ 若顶点 $v$ 是边 $e$ 的端点，否则 0（若 $e=(i,j)$，则 $B_{i,e}=1$，$B_{j,e}=-1$，或两者均为 1）。有向图的关联矩阵使用 $+1$（弧尾）和 $-1$（弧头）。

可达性矩阵 $P$：$P_{ij}=1$ 若从 $i$ 到 $j$ 存在路径，否则 0。$P=(I+A+A^2+\cdots +A^{n-1}{)}_{threshold}$。

矩阵表示在算法中的应用

邻接矩阵适合稠密图（$O(1)$ 查询两点是否相邻），关联矩阵适合边操作。拉普拉斯矩阵是谱图理论和图神经网络的代数基础。度矩阵和关联矩阵在网络流算法中扮演核心角色。

---

二、最短路径算法

2.1 问题定义与分类

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

全对最短路径（All-Pairs Shortest Path, APSP）：求所有顶点对之间的最短路径。

假设：边权重 $w(e)\ge 0$（Dijkstra 适用）。若无此假设，问题更困难（Bellman-Ford 或 SPFA）。

最短路径的性质：

• 最优子结构：最短路径的子路径也是最短路径。
• 三角不等式：$d(s,t)\le d(s,u)+w(u,v)$。
• 唯一性（若边权重均为正）：最短路径是唯一的。

2.2 Dijkstra算法

Dijkstra算法（1959）是解决非负权图 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)
            predecessor[v] = u

正确性证明（归纳不变式）：

维护不变式：对于 $S$ 中的每个顶点 $u$，$dist[u]$ 是 $s$ 到 $u$ 的最短距离。

• 初始化：$S=\{s\}$，$dist[s]=0$（显然最短）。
• 保持：设 $u$ 是从 $Q$ 中提取的最小 $dist$ 顶点。反证：若存在更短的 $s\to u$ 路径 $P$，$P$ 必经过 $Q$ 中的某个顶点 $x$。设 $x$ 是 $P$ 上第一个落在 $Q$ 中的顶点，则 $P$ 的 $s\to x$ 部分已是最短的（子路径最优性），故 $dist[x]\le w(P_{s\to x})<w(P_{s\to u})=dist[u]$，矛盾（因为 $u$ 是 $Q$ 中 $dist$ 最小的）。
• 终止：所有顶点加入 $S$，$dist$ 均为最短距离。

复杂度分析：

• 朴素实现（线性扫描找最小）：$O(V^2)$
• 使用二叉堆（优先队列）：$O((V+E)\log V)$
• 使用斐波那契堆：$O(E+V\log V)$
• 在稀疏图（$E=O(V)$）中，使用堆实现是 $O(V\log V)$；在稠密图（$E=O(V^2)$）中，朴素实现 $O(V^2)$ 更优。

Dijkstra与BFS的关系

当所有边权重相同（$w(e)=1$），Dijkstra算法退化为广度优先搜索（BFS），时间复杂度 $O(V+E)$。BFS 在无权图中保证找到的是边数最少的路径。

A*搜索算法：A* 是 Dijkstra 的启发式推广，使用估计函数 $f(v)=g(v)+h(v)$ 来优先搜索”更有希望”的顶点：

• $g(v)$：从起点到 $v$ 的实际最短路径长度
• $h(v)$：从 $v$ 到终点的估计距离（启发式，必须满足可采纳性 $h(v)\le h^{\ast }(v)$）
• 若 $h\equiv 0$，A* 退化为 Dijkstra
• 若 $h$ 一致且满足 $h(t)=0$（$t$ 是目标），A* 能高效找到最短路径

A* 的经典应用：电子游戏寻路、机器人导航、拼图求解。

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]:
        报告：图中存在负环

正确性：Bellman-Ford 的核心观察是：最短路径（若无负环）至多包含 $|V|-1$ 条边。因此，迭代 $|V|-1$ 轮松弛操作足以收敛。若在第 $|V|$ 轮仍有改进，则必然存在负环。

复杂度：$O(VE)$

SPFA（Shortest Path Faster Algorithm）是 Bellman-Ford 的队列优化版本，将被松弛的顶点加入队列而非常规扫描所有边。在实践中通常远快于 $O(VE)$ 最坏情况，但在对手构造的输入上仍可能退化到 $O(VE)$。

处理负权边时注意：即使存在负权边（但无负环），Dijkstra 也不能直接使用（因为负权会导致”绕路反而更短”的现象）。Bellman-Ford 和 SPFA 是处理负权边的主流方法。

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])

动态规划思想：$d_{ij}^{(k)}$ = 只经过前 $k$ 个顶点（即顶点子集 $\{1,\dots ,k\}$）时 $i$ 到 $j$ 的最短路径长度。递推关系：$d_{ij}^{(k)}=\min (d_{ij}^{(k-1)},d_{ik}^{(k-1)}+d_{kj}^{(k-1)})$。

复杂度：$O(V^3)$ 时间，$O(V^2)$ 空间（可用两行优化到 $O(V^2)$ 空间）。

适用范围：适合 $V\le 500$ 左右的稠密图。对于稀疏图，使用 $|V|$ 次 Dijkstra 或 Johnson 算法（$O(VE\log V)$）更优。

Johnson算法：结合 Dijkstra 和 Bellman-Ford：

1. 对原图添加虚拟源点 $s$，连接 $s$ 到所有其他顶点（边权为 0），用 Bellman-Ford 检测负环并计算势能 $h(v)$。
2. 对所有边重赋权：$w^{\prime }(u,v)=w(u,v)+h(u)-h(v)$（保证非负）。
3. 对每个源点运行 Dijkstra。

总复杂度 $O(VE\log V)$，适合稀疏图。

2.5 最短路径树与最短路算法

最短路径树（Shortest Path Tree, SPT）：从源点 $s$ 出发的最短路径构成一棵树，连接 $s$ 和所有可达顶点。最短路径树不唯一（除非图严格正权且无等长路径）。

BFS树：无权图的最短路径树，每层对应距离（边数）相等的顶点。

分层图（Layered Graph）：将 APSP 的结果按距离分层，用于可视化或特定路径规划。

---

三、连通性与图遍历

3.1 连通分量

无向图的连通分量：极大连通子图。可以用 BFS/DFS 一次遍历找到所有连通分量。

有向图的连通性：

• 强连通（Strongly Connected）：对于有向图 $G$，若对任意 $u,v\in V$，都有 $u\to v$ 和 $v\to u$ 路径，则 $G$ 是强连通的。
• 弱连通（Weakly Connected）：忽略方向后的无向版本是连通的。
• 强连通分量（Strongly Connected Components, SCC）：极大强连通子图。

Kosaraju算法（两遍 DFS）：

1. 第一次 DFS 记录拓扑排序的逆序出栈顺序。
2. 反转所有边的方向。
3. 按步骤1的逆序进行第二遍 DFS，每棵 DFS 树就是一个 SCC。

复杂度 $O(V+E)$。

Tarjan算法（一遍 DFS）：使用 DFS 递归栈和 lowlink 值识别 SCC。单次遍历即可找到所有 SCC，同样 $O(V+E)$。

3.2 DFS与BFS的性质

DFS（深度优先搜索）：

• 时间戳：每个顶点有发现时间 $d[v]$ 和完成时间 $f[v]$
• 括号定理：区间 $[d[u],f[u]]$ 与 $[d[v],f[v]]$ 之间只有三种关系：嵌套、不相交、相等（对应不同 DFS 树结构）
• 后向边：$v$ 的 DFS 树祖先 $u$ 满足 $f[u]>d[v]$。若存在后向边，则图中存在环。
• 拓扑排序：对于 DAG，所有边满足 $d[u]<d[v]$（前向边性质）

BFS（广度优先搜索）：

• 发现的所有顶点与源点距离等于 BFS 树的层数
• BFS 树中从源点到任意顶点的路径是最少边数的路径
• 用于无权图的最短路径

割点与桥（Articulation Points and Bridges）：

• 割点：删除后使连通分量不连通的顶点
• 桥（割边）：删除后使连通分量不连通的边
• Tarjan 的 DFS 算法可以在 $O(V+E)$ 时间内找到所有割点和桥，利用 lowlink 值判断：
  • 顶点 $u$ 是割点：若存在子节点 $v$ 使得 $low[v]\ge d[u]$
  • 边 $(u,v)$ 是桥：若 $low[v]>d[u]$

---

四、匹配与网络流

4.1 匹配的基本概念

匹配（Matching）$M\subseteq E$ 是两两无公共端点的边集。匹配的边之间互不相交。

匹配的大小：$|M|$ 是匹配中的边数。

匹配顶点：被匹配的顶点。

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

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

完全匹配（在二分图中）：左右两边各有 $|M|$ 个匹配顶点。

增广路径（Augmenting Path）：关于匹配 $M$ 的增广路径是两端均未被匹配的交替路径（即非匹配边和匹配边交替出现）。Berge 定理：匹配 $M$ 是最大匹配，当且仅当不存在关于 $M$ 的增广路径。

4.2 Hall定理

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

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

Hall 定理的推广（Hall-Koenig 定理）：最大匹配的大小为 ${\min }_{S\subseteq X}(|X\setminus S|+|N(S)|)$，这给出了最大匹配大小的精确界。

Hall定理应用

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

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

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

König定理：在二分图中，最大匹配的大小等于最小顶点覆盖的大小（最小顶点覆盖是覆盖所有边的最小顶点集）。这是图论中最重要的对偶定理之一，因为它将组合优化中的”匹配”和”覆盖”两个问题联系起来，且两者都可以用网络流高效求解。

4.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)$（即从源点流出的净流量）。

4.4 最大流最小割定理

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

割的容量：$c(S,\bar{S})={\sum }_{e\in (S,\bar{S})}c(e)$，即从 $S$ 指向 $\bar{S}$ 的所有弧的容量之和。

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

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

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

定理的意义

这个定理不仅给出了最大流的上界（任何流的值不超过任何割的容量），还证明了存在某个流和某个割使得等号成立。这是组合优化中最重要的对偶定理之一，与线性规划对偶理论紧密相连。最大流-最小割定理可以视为 LP 对偶的一个特例。

割的类型：

• 最小 $s$-$t$ 割：使 $c(S,\bar{S})$ 最小的 $s$-$t$ 割
• 全局最小割：使 $c(S,\bar{S})$ 最小的割（不一定区分 $s$ 和 $t$）
• $(S,\bar{S})$ 的补割：$(\bar{S},S)$ 的容量等于 $(S,\bar{S})$ 中反向弧的容量之和

4.5 最大流算法

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

while 存在增广路径 P (使用 DFS/BFS):
    找到 P 的最小剩余容量 b = min(c(e) - f(e))
    沿 P 增加 b 单位流量
    更新剩余图 G_f

• 若所有容量均为整数，则 Ford-Fulkerson 的每次增广使流值至少增加 1，故最多迭代 $|f^{\ast }|$ 次（$f^{\ast }$ 是最大流值）。
• 时间复杂度：$O(E\cdot |f^{\ast }|)$（整数容量）。若容量很大（$C$），可能很慢。
• 关键问题：若用 DFS，增广路径选择不当可能导致迭代次数过多。Edmonds-Karp算法通过使用 BFS 寻找最短（边数最少）的增广路径，解决了这个问题。

Edmonds-Karp算法（Ford-Fulkerson + BFS）：$O(V{E}^2)$。BFS 保证每次增广都增加最短路径长度，从而限制迭代次数至 $O(VE)$。

Dinic算法：使用层次图（level graph）和阻塞流（blocking flow），在单位容量网络中达到 $O(\min \{V^{2/3},E^{1/2}\}\cdot E)$，一般网络中 $O(V^{2}E)$，实际中通常比 Edmonds-Karp 快得多。

BFS 构建层次图
while BFS 成功:
    使用 DFS 在层次图中寻找阻塞流
    增加流量
    删除不可达的顶点和边

推送-重标记算法（Push-Relabel）：不使用增广路径，而是维护预流并在顶点间”推送”流量，最后”重标记”高度函数。最高标号选择规则下达到 $O(V^3)$，实际中通常很快。GLPK 和许多工业级求解器基于此方法。

ISAP/GAP：改进的推送-重标记算法，利用标签间隔（GAP）启发式加速。

4.6 最小费用最大流

最小费用最大流（Minimum Cost Maximum Flow, MCMF）：在最大流约束下最小化总成本 ${\sum }_{e}f(e)\cdot w(e)$。

** SSP 算法**：每次迭代用 Bellman-Ford（在剩余网络中找最小费用路径）增加单位流量，重复直到达到最大流。总复杂度 $O(F\cdot VE)$（$F$ 是最大流值）。

网络单纯形：专门针对最小费用流问题的单纯形法，在实践中非常高效。

应用：

• 运输问题：工厂到仓库的运输（最小成本）
• 任务分配：匈牙利算法是最小费用流的一种特例
• 图像分割：GraphCut 方法

---

五、图的着色问题

5.1 色数与基本性质

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

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

贪心着色：按任意顺序给顶点着色，每个顶点分配与邻接已着色顶点不同的最小颜色。贪心着色最多使用 $\Delta (G)+1$ 种颜色（$\Delta (G)$ 是最大度）。

下界：

• $\chi (G)\ge \omega (G)$（最大团大小 $\omega (G)$，即图中最大完全子图的顶点数）
• $\chi (G)\ge \lceil \Delta (G)\rceil$（最大度）
• $\chi (G)\ge \frac{|V|}{\alpha (G)}$（由 $\chi \cdot \alpha \ge |V|$ 推导，其中 $\alpha (G)$ 是最大独立集大小）

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

临界图：若删除任意一条边都会降低色数，则图 $G$ 是 $\chi$-临界 的。$\chi$-临界图的最小度至少为 $\chi (G)-1$。

5.2 平面图着色

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

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

这是图论最著名的定理之一，历史上首个借助计算机证明的主要定理。证明依赖于计算机对大量构型的穷举验证。

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

• 使用归纳法
• 平面图存在度数至多为5的顶点（由欧拉公式可证）
• 若最小度 $\delta \le 5$，必有可删除的顶点
• 删除顶点，递归着色，再加回顶点（使用 Kempe 链反驳法处理特殊构型）

四色定理的实际意义

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

Hadwiger猜想（未解决）：每个 $\chi (G)$-色的图都有一个子图与 $K_{\chi (G)}$ 的一个细分同构。这是图着色理论中最深远的未解猜想之一。

5.3 着色算法的复杂度

判断 $\chi (G)=2$：等价于判断图是否为二分图。可通过 BFS 检查是否存在奇环（奇环 $⟺$ 不是二分图），$O(V+E)$。

判断 $\chi (G)=3$：3-着色问题是 NP-完全 的（即使是平面图，3-着色仍是 NP-完全）。

一般着色问题：着色问题是 NP-hard。已知最好近似算法保证 $\chi (G)\le O(\frac{\Delta }{\log \Delta }\sqrt{\log \log \Delta })$（Björklund et al.）。

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

着色与时间表调度：着色问题等价于”无冲突分配”问题（如考试安排：课程为顶点，若两门课有学生同时选修则连边，求最小时间片数）。

---

六、平面图与欧拉公式

6.1 平面图的基本性质

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

Kuratowski定理（平面性的判定，1930）：

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

$K_5$（5个顶点的完全图）和 $K_{3,3}$（完全二分图）是平面性的两个”障碍”。 subdivisions（细分：在边上插入新顶点）也是障碍。

Wagner定理（等价表述）：图是平面的当且仅当它的叉宽（treewidth）和图的子式（minor）不包含 $K_5$ 或 $K_{3,3}$ 作为子式。

平面性测试算法：Hopcroft-Tarjan 的平面性测试算法可在 $O(V)$ 时间内判定。

6.2 欧拉公式

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

$V-E+F=2$

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

推论：

1. 对于平面图，若 $V\ge 3$，则 $E\le 3V-6$（因为每个面至少有3条边，$2E\ge 3F$，结合欧拉公式）
2. 平面图的平均度小于6：$\frac{2E}{V}<6$
3. 任何平面图都有度数为5或更小的顶点（鸽巢原理）

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

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

欧拉公式与多面体

欧拉公式 $V-E+F=2$ 对所有凸多面体成立（因为凸多面体可以投影为平面图）。这意味着五种正多面体（Platonic solids）必须满足此关系：四面体(4,6,4)、立方体(8,12,6)、八面体(6,12,8)、十二面体(20,30,12)、二十面体(12,30,20)。

6.3 平面图的对偶

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

自对偶：若 $G\cong G^{\ast }$，则 $G$ 是自对偶的（如 wheel 图 $W_n$、网格图的无限平面版本）。

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

• $G$ 的环对应 $G^{\ast }$ 的桥
• $G$ 是连通图当且仅当 $G^{\ast }$ 连通
• $G$ 的欧拉公式可从 $G^{\ast }$ 推导（实际上它们是同一个欧拉公式的不同形式）

应用：

• 地图着色 $⟺$ 对偶图的顶点着色
• 平面电阻网络与有效电阻
• 平面图的 Kirchhoff 定律和电势求解

---

七、谱图理论

7.1 谱图理论的基本框架

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

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

• $L$ 是对称正半定的：所有特征值 ${\lambda }_1\le {\lambda }_2\le \cdots \le {\lambda }_n$
• 最小特征值 ${\lambda }_1=0$，对应特征向量 $1=(1,1,\dots ,1{)}^T$
• 特征值之和：${\sum }_i{\lambda }_i=\text{tr}(L)={\sum }_{v}d(v)=2m$

邻接矩阵的特征值：记作 ${\mu }_1\ge {\mu }_2\ge \cdots \ge {\mu }_n$。完全图 $K_n$ 的特征值是 $n-1$（重数 $n-1$）和 $-1$（重数 $n-1$）。

拉普拉斯矩阵的特征向量与图的性质密切相关。例如，$L$ 的第二小特征值 ${\lambda }_2$（代数连通度）度量了图的连通程度。

7.2 谱与图属性的联系

连通性与谱：

• $G$ 连通 $\iff$ ${\lambda }_2>0$（第二小特征值称为代数连通度）
• ${\lambda }_2$ 越大，$G$ 越”连通得好”
• 完全图 $K_n$ 的 ${\lambda }_2=n$（最大连通性），路径图 $P_n$ 的 ${\lambda }_2\approx O(1/n^2)$（近似不连通）

Cheeger不等式（双重 Cheeger 不等式）：

$\frac{\varphi (G)}{2}\le {\lambda }_2\le 2\varphi (G)$

其中 $\varphi (G)={\min }_{S\subset V,0<|S|\le |V|/2}\frac{|\partial S|}{|S|}$ 是图的 Cheeger 常数（边缘比），衡量图的连通性。Cheeger 不等式将代数连通度 ${\lambda }_2$（谱量）与几何连通度 $\varphi (G)$（组合量）联系起来，在图分割、社区发现、随机游走等领域有广泛应用。

谱半径与正则性：

• ${\mu }_1\le \Delta (G)$，且对于连通正则图，${\mu }_1=\Delta (G)$。
• 无向图的 ${\mu }_1$ 与图的平均距离、热核扩散时间等有复杂联系。

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

路径图的谱：$P_n$ 的拉普拉斯特征值为 ${\lambda }_k=2-2\cos (\frac{(k-1)\pi }{n})$，$k=1,\dots ,n$。

7.3 谱聚类

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

无向图上的归一化谱聚类算法（Ng, Jordan, Weiss 2002）：

1. 构建相似度矩阵 $W$（如高斯核 $w_{ij}=\exp (-\Vert x_i-x_j{\Vert }^2/(2{\sigma }^2))$）
2. 构建度矩阵 $D$（$D_{ii}={\sum }_j{w}_{ij}$）
3. 计算归一化拉普拉斯 $L_{sym}=I-D^{-1/2}W{D}^{-1/2}$
4. 取 $k$ 个最小特征值对应的特征向量（或最大的 $k$ 个若用 $I-L$），组成矩阵 $U\in {\mathbb{R}}^{n\times k}$
5. 对 $U$ 的行（归一化后）运行 K-means 聚类
6. 将聚类标签映射回原始顶点

未归一化谱聚类（Shi-Malik 2000）：使用 $L_{rw}=D^{-1}L$，取 $L_{rw}$ 的 $k$ 个最小特征向量（除第一个），然后用 K-means 或模糊聚类分割。

谱聚类的优势

• 不需要凸区域假设（不同于 K-means）
• 可以发现非凸形状的簇
• 计算效率高（只需特征分解 $O(n^3)$ 或稀疏特征分解 $O(n^2)$）
• 理论基础与图分割的自然目标（RatioCut / Ncut）相关

RatioCut 和 Ncut：

• $\text{RatioCut}(S_1,\dots ,S_k)={\sum }_{i=1}^k\frac{|\partial S_i|}{|S_i|}$
• $\text{Ncut}(S_1,\dots ,S_k)={\sum }_{i=1}^k\frac{|\partial S_i|}{\text{vol}(S_i)}$，其中 $\text{vol}(S_i)={\sum }_{v\in S_i}d(v)$

谱聚类通过拉普拉斯特征向量近似最小化 Ncut（放松整数约束后变成特征分解问题）。

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

图卷积网络（GCN, Graph Convolutional Network）的核心操作：

$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}$ 是对应的度矩阵，$H^{(l)}$ 是第 $l$ 层的节点特征矩阵，$W^{(l)}$ 是可学习的权重矩阵，$\sigma$ 是激活函数。

谱域解释：GCN 的操作对应于对图的拉普拉斯矩阵进行谱滤波。${\tilde{D}}^{-1/2}\tilde{A}{\tilde{D}}^{-1/2}=I-{\tilde{L}}_{sym}$（归一化拉普拉斯）。在谱域中，一个可学习的滤波器 $g_{\theta }(\Lambda )$ 作用在拉普拉斯特征值上：

$H^{(l+1)}=U{g}_{\theta }(\Lambda )U^T{H}^{(l)}$

ChebNet（Defferrard et al., 2016）使用切比雪夫多项式近似谱滤波，避免计算特征分解：

$g_{\theta }(\Lambda )\approx {\sum }_{k=0}^K{\theta }_k{T}_k(\tilde{\Lambda })$

其中 $\tilde{\Lambda }=2\Lambda /{\lambda }_{\max }-I$。

空间域方法（GraphSAGE, GAT）：

• GraphSAGE：通过采样和聚合邻居特征 $h_v^{(l+1)}=\sigma (W\cdot \text{AGG}(\{h_u^{(l)}:u\in \mathcal{N}(v)\}))$
• GAT（Graph Attention Network）：使用注意力机制分配不同邻居不同权重

7.5 图的扩散与随机游走

随机游走：在图上从某顶点出发，每步等概率选择一条邻边（或按转移概率）移动。

转移矩阵（行随机矩阵）：$P=D^{-1}A$（若无向）或更一般的 $P_{ij}=p(j|i)$。

平稳分布：$\pi$ 满足 $\pi P=\pi$，即 $\pi$ 是 $P^T$ 的特征值 1 对应的左特征向量。对于无向连通非二部图，平稳分布为 ${\pi }_i=d(i)/(2|E|)$。

PageRank（随机游走的中心性度量）：阻尼因子 $\alpha$ 的 PageRank 满足：

$\pi =(1-\alpha )P^T\pi +(1-\alpha )r$

其中 $r$ 是重启/均匀分布向量。PageRank 在 Google 搜索排序和推荐系统中扮演核心角色。

个性化 PageRank：将重启向量 $r$ 替换为用户特定的分布，可用于个性化推荐和节点分类。

热核 PageRank：$h_t(i,j)=(e^{tL}{)}_{ij}$ 是图上的热核，与图的局部结构密切相关。

---

八、欧拉回路与哈密顿回路

8.1 欧拉回路

欧拉回路：遍历图中每条边恰好一次的回路（回到起点）。

欧拉定理（Hierholzer 算法）：

• 连通无向图存在欧拉回路，当且仅当所有顶点度数为偶数。
• 连通无向图存在从 $u$ 到 $v$ 的欧拉路径（不要求回到起点），当且仅当 $u$ 和 $v$ 度数为奇数（恰好两个），其余顶点度数为偶数。

Hierholzer 算法（$O(E)$）：

1. 从任意顶点开始，贪心遍历直到回到起点（得到一个回路）
2. 若回路未覆盖所有边，在回路的顶点中找一个有未覆盖边的顶点，从该顶点开始找新回路并插入原回路
3. 重复直到覆盖所有边

有向图版本：将”度数为偶数”替换为”每个顶点的出度等于入度”。

8.2 哈密顿回路

哈密顿回路：遍历图中每个顶点恰好一次的回路（边数不限）。

与欧拉回路的本质区别：哈密顿回路问题是 NP-完全的，即使判定是否存在哈密顿回路也是如此（而欧拉回路可 $O(E)$ 判定）。

Dirac 定理（充分条件）：若图 $G$ 是 $n\ge 3$ 的简单图，且所有顶点度 $d(v)\ge n/2$，则 $G$ 存在哈密顿回路。

Ore 定理：若对每一对不相邻顶点 $u,v$，都有 $d(u)+d(v)\ge n$，则 $G$ 存在哈密顿回路（Dirac 是 Ore 的特例）。

旅行商问题（TSP, Traveling Salesman Problem）：在加权完全图中寻找最小权哈密顿回路。TSP 是 NP-hard 的，但有多种近似算法：

• 最近邻（最近邻启发式）：$O(V^2)$，近似比无保证
• Christofides 算法：$O(V^3)$，在满足三角不等式的度量空间中达到 1.5-近似
• Lin-Kernighan 启发式：实践中最有效的启发式 TSP 算法

---

九、极值图论

9.1 Turán定理

Turán 问题：在禁止包含完全图 $K_r$ 作为子图的前提下，最多能在 $n$ 个顶点上放置多少条边？

Turán 定理（1941）：最大边数为 $t_{r-1}(n)=\left(1-\frac{1}{r-1}\right)\frac{n^2}{2}$，当且仅当图恰好是 $r-1$ 部 Turán 图 $T_{n,r-1}$（将顶点分成 $r-1$ 个尽可能均衡的部分，每个部分内部无边，跨部之间全连接）时达到。

Mantel 定理（Turán 定理的 $r=3$ 特例）：不含三角形（$K_3$）的图最多有 $\lfloor n^2/4\rfloor$ 条边。

Turán 定理是极值图论的开创性工作，也是 Erdős-Faber-Lovász 猜想等后续研究的起点。

9.2 Ramsey理论

Ramsey 数 $R(s,t)$：最小的 $n$ 使得任何含 $n$ 个顶点的图（及其补图）中必含一个 $K_s$ 或其补图中含一个 $K_t$。

Ramsey 定理：$R(s,t)$ 存在（有限）。已知：

• $R(3,3)=6$
• $R(4,4)=18$
• 已知界：$R(5,5)\in [43,48]$

Erdős-Szekeres 定理：任意 $R{S}^2(n)+1$ 个实数序列中必存在长度为 $n+1$ 的单调递增或单调递减子序列。其中 $R{S}^2(n)=\left(\genfrac{}{}{0ex}{}{2n-1}{n-1}\right)$ 是精确界（Dilworth 定理的应用）。

鸽巢原理的深化：Ramsey 理论告诉我们，即使图的结构”混乱”到没有明显的模式，在足够大的规模下，某种特定的结构仍然不可避免。

---

十、随机图

10.1 Erdős–Rényi 随机图

$G(n,p)$ 模型：$n$ 个顶点，每对顶点独立以概率 $p$ 连边。

$G(n,m)$ 模型：$n$ 个顶点，均匀随机选择 $m$ 条边。

基本性质：

• 期望边数：$\left(\genfrac{}{}{0ex}{}{n}{2}\right)p$
• 顶点 $v$ 的度服从 $\text{Binomial}(n-1,p)$
• 当 $p=1/2$ 时，$G(n,1/2)$ 是所有 $\left(\genfrac{}{}{0ex}{}{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}{}\right)$ 个图上均匀分布

度分布：在 $G(n,p)$ 中，当 $np=\lambda$ 固定、$n\to \infty$ 时，度分布趋近于泊松分布 $\text{Poisson}(\lambda )$。

渗流理论：$G(n,p)$ 的连通性转变（phase transition）发生在 $p=\frac{\log n}{n}$ 附近：

• 若 $p<\frac{\log n+\omega }{n}$，图不连通（存在孤立顶点）
• 若 $p>\frac{\log n+\omega }{n}$，图连通（除孤立点外）

大偏差与图极限：随机图的许多性质可以用大偏差原理描述，图序列的极限对象是 graphon（可测函数 $W:[0,1{]}^2\to [0,1]$）。

10.2 随机图上的算法问题

子图检测：在 $G(n,p)$ 中寻找特定子图（如三角形、团）是随机图理论的核心问题。

社区发现问题：SBM（Stochastic Block Model）是社区结构的随机图模型，各社区内部连边概率高，跨社区连边概率低。

图同构：对于随机图，图同构问题在平均情况下可能比最坏情况简单得多。

---

十一、图算法复杂度分类

11.1 P、NP与图问题

P 类（图算法）：

• SSSP、BFS/DFS、连通分量、拓扑排序：$O(V+E)$
• 最小生成树（Kruskal, Prim）：$O(E\log V)$
• 二分图匹配：$O(VE)$
• 最大流（Edmonds-Karp）：$O(V{E}^2)$
• 平面图算法：许多 NP-hard 问题在平面图上是多项式可解的

NP-hard 图问题：

• 哈密顿回路（TSP）
• 顶点覆盖（Vertex Cover）
• 最大割（Max Cut）
• 图着色
• 最大团（Maximum Clique）

11.2 图的参数化复杂性

树宽（Treewidth）：图分解中子图交叉大小的度量。树宽小的图（如树、串联-并联图）在许多 NP-hard 问题上具有多项式时间算法。

核化（Kernelization）：将参数化问题通过预处理压缩到与参数相关的规模。

固定参数可解（FPT）：若算法复杂度为 $O(f(k)\cdot poly(n))$，则问题是 FPT 的。经典例子：$k$-顶点覆盖是 FPT（$O(2^k\cdot n)$）。

---

十二、知识图谱与图机器学习

12.1 知识图谱的表示

知识图谱：多关系有向图 $\mathcal{G}=(V,R,E)$，其中 $E\subseteq V\times R\times V$ 是三元组 $(h,r,t)$ 的集合。

知识图谱嵌入（Knowledge Graph Embedding, KGE）：将实体和关系嵌入到低维向量空间。

TransE（Bordes et al., 2013）：$h+r\approx t$，翻译模型。优化 $\max (0,\gamma +d(h+r,t))$。

DistMult（Yang et al., 2014）：双线性模型，$h^{T}Rt=h_i{r}_{ij}{t}_j$。

RotatE（Sun et al., 2019）：将关系建模为复数空间中的旋转。

12.2 图神经网络的应用

节点分类：利用邻居信息增强节点表示（半监督学习）。

链接预测：预测图中缺失的边（用于推荐、知识图谱补全）。

图分类：将整个图作为输入进行分类（如分子性质预测、蛋白质功能预测）。

图生成：生成具有特定性质的图（如药物分子生成）。

---

十三、典型习题

习题 1：握手定理的应用

证明：在任意聚会中，与奇数个人握手的人数是偶数。

答案：由握手定理 ${\sum }_{v}d(v)=2|E|$，即所有顶点度数之和为偶数。偶数个奇数之和为偶数，因此奇数度顶点的个数必为偶数。

习题 2：Dijkstra 算法的边界

给出右图（带权无向图）中从源点 $s$ 出发的 Dijkstra 算法的执行过程，计算每个顶点的最短距离。

答案：（根据具体图示回答。核心是每次提取最小 dist 的顶点，并用之更新邻居的距离。）

习题 3：最大流最小割的构造

使用 Ford-Fulkerson 算法找到下图的最大流，并构造对应的最小割。

答案：（根据具体图示。关键是找到剩余图中不存在从 $s$ 到 $t$ 的增广路径时，$s$-可达集 $S$ 即定义了最小割。）

习题 4：Hall 定理的应用

男生集合 $X=\{A,B,C,D\}$，女生集合 $Y=\{1,2,3,4,5\}$。A 认识 {1,2,3}，B 认识 {2,3,4}，C 认识 {1,4}，D 认识 {3,5}。判断是否存在完美匹配。

答案：检查 Hall 条件：$S=\{A,B\}$，$N(S)=\{1,2,3,4\}$，$|N|=4\ge 2$ ✓；$S=\{A,C\}$，$N(S)=\{1,2,3,4\}$，$|N|=4\ge 2$ ✓；$S=\{B,C\}$，$N(S)=\{1,2,3,4\}$，$|N|=4\ge 2$ ✓；$S=\{A,B,C\}$，$N(S)=\{1,2,3,4,5\}$，$|N|=5\ge 3$ ✓；$S=\{C,D\}$，$N(S)=\{1,3,4,5\}$，$|N|=4\ge 2$ ✓。所有子集满足，存在完美匹配。

习题 5：谱图理论

证明拉普拉斯矩阵 $L=D-A$ 的特征值非负。

答案：对于任意向量 $x\in {\mathbb{R}}^n$，有 $x^{T}Lx=\frac{1}{2}{\sum }_{ij}{A}_{ij}(x_i-x_j{)}^2\ge 0$（利用 $L$ 的对称性和 $D_{ii}={\sum }_j{A}_{ij}$）。因此 $L$ 是正半定的，所有特征值 $\ge 0$。

习题 6：平面图边数上界

利用欧拉公式证明：任意平面图（$V\ge 3$）满足 $E\le 3V-6$。

答案：每个面至少由 3 条边围成，故 $2E\ge 3F$。结合欧拉公式 $V-E+F=2$，消去 $F$ 得 $V-E+\frac{2E}{3}\ge 2$，即 $\frac{E}{3}\le V-2$，故 $E\le 3V-6$。

---

十四、图算法实现要点

14.1 邻接表 vs 邻接矩阵

表示方式	空间	边查询	遍历邻居	适用场景
邻接矩阵	$O(V^2)$	$O(1)$	$O(V)$	稠密图、矩阵运算
邻接表	$O(V+E)$	$O(\mathrm{deg}(v))$	$O(\mathrm{deg}(v))$	稀疏图、遍历

14.2 图算法的数值稳定性

• 浮点数比较时使用 $ϵ$ 容差（$|x-y|<ϵ$）
• 网络流中可能出现浮点容量或分数流量
• PageRank 迭代需要监测收敛（$\Vert {\pi }_{k+1}-{\pi }_k{\Vert }_1<ϵ$）

14.3 并行与分布式图处理

• Pregel（Google）：BSP 模型的顶点中心计算
• GraphLab/PowerGraph：Gas 模型处理幂律图（度分布不均）
• Ligra：轻量级共享内存图处理
• Pregel+：支持 OSS 和 OSSS 模式的图分割

---

十五、历史注记与延伸阅读

15.1 发展简史

• 1736：Euler 的哥尼斯堡七桥问题——图论的起源。
• 1847：Kirchhoff 将树的理论应用于电网络（生成树）。
• 1852：四色猜想提出（1976 年 Appel-Haken 证明）。
• 1936：Kőnig 的《有限图理论》——图论第一本专著。
• 1930：Kuratowski 平面性判定定理。
• 1941：Turán 的极值图论开创性工作。
• 1956：Ford-Fulkerson 最大流最小割定理。
• 1959：Dijkstra 最短路径算法。
• 1959：Berge 的《图论》——匹配理论的系统性研究。
• 1971：Karp 的 21 个 NP-完全问题，其中许多是图论问题。
• 1983：Kosaraju 和 Tarjan 的 SCC 算法。
• 1990s：随机图与渗流理论的系统研究。
• 2000s：谱图理论在大规模数据分析中的广泛应用。
• 2017-2019：图神经网络（GCN, GraphSAGE, GAT）的兴起。

15.2 经典教材

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. Doyle, P. G., & Snell, J. L. (1984). Random Walks and Electric Networks. arXiv. —— 随机游走与网络的谱联系。
6. Van Lint, J. H., & Wilson, R. M. (2001). A Course in Combinatorics (2nd ed.). Cambridge University Press. —— 组合数学（含图论部分）。

15.3 论文精选

7. Ford, L. R., & Fulkerson, D. R. (1956). Maximal Flow Through a Network. Can. J. Math., 8, 399-404.
8. Dijkstra, E. W. (1959). A Note on Two Problems in Connexion with Graphs. Numer. Math., 1, 269-271.
9. Shi, J., & Malik, J. (2000). Normalized Cuts and Image Segmentation. IEEE TPAMI, 22(8), 888-905.
10. Ng, A. Y., Jordan, M. I., & Weiss, Y. (2001). On Spectral Clustering: Analysis and an Algorithm. NeurIPS, 849-856.
11. Kipf, T. N., & Welling, M. (2017). Semi-Supervised Classification with Graph Convolutional Networks. ICLR.
12. Velickovic, P., Cucurull, G., Casanova, A., et al. (2018). Graph Attention Networks. ICLR.

---

相关文档

• 线性代数深度指南 - 图矩阵的线性代数基础
• 概率论深度指南 - 马尔可夫链与图模型
• 博弈论基础 - 网络博弈与图结构博弈
• 凸优化深度指南 - 图割与组合优化
• 统计学深度指南 - 图模型与贝叶斯网络