图论

#Mathematics #ComputerScience #Algorithm

Graph Theory 图论

本质概括：研究由顶点与边构成的离散结构及其性质的数学分支，是组合数学与离散数学的核心领域。

图论起源于 1736 年欧拉对柯尼斯堡七桥问题的研究，是数学与计算机科学的交叉基础学科。其研究对象——图——由顶点集 $V$ 和边集 $E$ 构成，记作 $G = (V, E)$ 。图论为网络分析、优化问题、算法设计提供了统一的数学语言。

一、基本概念与术语

1.1 图的要素

术语	英文	定义
顶点	Vertex / Node	图中的基本元素，代表研究对象
边	Edge / Arc	连接两个顶点的关系，可有向或无向
邻接	Adjacency	两顶点由边直接相连
关联	Incidence	边与其端点之间的关系
度	Degree	与顶点关联的边数；有向图分为入度 $\deg^{-} (v)$ 和出度 $\deg^{+} (v)$

握手定理：对于任意图 $G = (V, E)$ ，所有顶点度数之和等于边数的两倍：

\sum_{v \in V} \deg (v) = 2 | E |

1.2 图的分类

分类维度	类型	说明
方向性	无向图 / 有向图	边是否具有方向
权重	无权图 / 加权图	边是否赋予数值权重
连通性	连通图 / 非连通图	任意两顶点间是否存在路径
环路	有环图 / 无环图（DAG）	是否包含环路
密度	稀疏图 / 稠密图	边数相对于 $
特殊结构	二部图 / 完全图 / 平面图 / 树	满足特定拓扑约束的图

1.3 路径与连通性

路径 (Path)：顶点序列 $v_{0}, v_{1}, \dots, v_{k}$ ，其中相邻顶点由边相连
简单路径：不重复经过顶点的路径
环路 (Cycle)：起点与终点相同的路径，长度 $\geq 3$
连通分量：无向图中的极大连通子图
强连通分量 (SCC)：有向图中任意两点可互达的极大子图，可用 Tarjan 或 Kosaraju 算法求解

二、图的表示与存储

图在计算机中的存储方式直接影响算法效率。详见图。

表示方法	空间复杂度	查边	遍历邻居	适用场景
邻接矩阵	$O (V^{2})$	$O (1)$	$O (V)$	稠密图、频繁查边
邻接表	$O (V + E)$	$O (\deg (v))$	$O (\deg (v))$	稀疏图、遍历为主
边列表	$O (E)$	$O (E)$	$O (E)$	Kruskal 等按边操作的算法
链式前向星	$O (V + E)$	$O (\deg (v))$	$O (\deg (v))$	竞赛常用，内存紧凑

三、图的遍历

图的遍历是几乎所有图算法的基础。详见图的遍历。

3.1 深度优先搜索 (DFS)

沿一条路径尽可能深入，回溯后再探索其他分支。时间复杂度 $O (V + E)$ 。

应用：连通分量检测、环路检测、拓扑排序、强连通分量（Tarjan 算法）。

3.2 广度优先搜索 (BFS)

逐层向外扩展，使用队列实现。时间复杂度 $O (V + E)$ 。

应用：无权图最短路径、层序遍历、二部图判定。

相关页面：深度优先搜索、广度优先搜索

四、最短路径问题

最短路径是图论中最重要的优化问题之一。详见最短路径算法。

算法	适用条件	时间复杂度	核心策略
Dijkstra	非负权边，单源	$O (E \log V)$ （优先队列）	贪心算法
Bellman-Ford	可处理负权边，单源	$O (V E)$	动态规划 / 松弛
SPFA	Bellman-Ford 的队列优化	平均 $O (E)$ ，最差 $O (V E)$	松弛 + 队列
Floyd算法	全源最短路径	$O (V^{3})$	动态规划
Johnson	全源，稀疏图	$O (V^{2} \log V + V E)$	Bellman-Ford + Dijkstra

五、生成树与连通性

5.1 最小生成树 (MST)

在加权连通无向图中，找到边权之和最小的生成树。详见最小生成树。

算法	策略	时间复杂度	适用场景
Kruskal	按边权排序，逐边加入（并查集判环）	$O (E \log E)$	稀疏图
Prim	从单点扩展，每次加最小跨边	$O (E \log V)$ （优先队列）	稠密图

切割性质：对于图的任意切割，跨越切割的最小权边必定属于某棵 MST。

5.2 连通性相关问题

桥与割点：删除后使图不再连通的边/点，可用 Tarjan 算法 $O (V + E)$ 求解
边/点连通度：使图不连通所需删除的最少边/点数
强连通分量：有向图中的极大强连通子图

六、经典图论问题

6.1 欧拉路径与回路

研究是否能不重复地遍历图中所有边。详见欧拉路径。

欧拉回路存在条件：连通图中每个顶点度数为偶数
欧拉路径存在条件：恰好有 0 或 2 个奇度顶点

6.2 拓扑排序

对有向无环图 (DAG) 的顶点进行线性排序。详见拓扑排序。

Kahn 算法（BFS）：反复删除入度为 0 的顶点
DFS 后序逆序

应用：任务调度、编译依赖、课程先修关系。

6.3 网络流

研究网络中的最大传输量。详见最大流问题。

最大流最小割定理：网络最大流量等于最小割的容量
Ford-Fulkerson 方法、Edmonds-Karp 算法、Dinic 算法

6.4 图着色

用最少颜色为顶点着色，使得相邻顶点颜色不同。

色数 $χ (G)$ ：所需最少颜色数
四色定理：任何平面图 $χ (G) \leq 4$
图着色是 NP 完全问题

6.5 匹配问题

在图中找到最大的边集，使得没有两条边共享端点。

二部图最大匹配：匈牙利算法 $O (V E)$
最大权匹配：Kuhn-Munkres (KM) 算法

6.6 旅行商问题 (TSP)

寻找经过所有顶点恰好一次并返回起点的最短回路。NP-hard 问题，常用近似算法和启发式方法求解。

七、图论的应用领域

领域	应用	对应图论概念
计算机网络	路由协议（OSPF）	最短路径
社交网络	社区发现、影响力传播	连通分量、中心性
交通规划	GPS 导航、物流优化	最短路径、网络流
编译器	依赖分析、寄存器分配	拓扑排序、图着色
电路分析	网络拓扑、KVL/KCL	树、回路
生物信息学	蛋白质交互网络	图聚类
推荐系统	用户-物品关系	二部图匹配
运筹学	资源分配、调度	网络流、匹配

八、学习路径

unknown

基本概念 → 图的存储 → 遍历（DFS/BFS）
    ↓
最短路径（Dijkstra → Bellman-Ford → Floyd）
    ↓
最小生成树（Kruskal / Prim）
    ↓
拓扑排序 → 强连通分量
    ↓
网络流 → 匹配 → 图着色
    ↓
NP 问题（TSP、图着色、哈密顿回路）

推荐教材：

Bondy & Murty,《Graph Theory》——经典数学向教材
CLERTA（Cormen 等），《算法导论》第六部分——算法实现向
Diestel,《Graph Theory》——研究生级别参考

图数学计算机科学数据结构算法
 最短路径算法 Dijkstra Bellman-Ford Floyd算法
 最小生成树拓扑排序欧拉路径最大流问题
 深度优先搜索广度优先搜索四色定理电路
 贪心算法动态规划

AI 结构化补充（2026-05-02）

Graph Theory 图论

本质概括：研究由顶点与边构成的离散结构及其性质的数学分支，是组合数学与离散数学的核心领域。

线性代数阅读路径：若关注图怎样产生矩阵，可直接跳到本文后半的“线性代数视角”。具体的 $K_{4}$ 关联矩阵、树矩阵和行空间判别见关联矩阵；环路流与 Kirchhoff 方程见基尔霍夫电路定律和网络。

一、基本概念与术语

1.1 图的要素

术语	英文	定义
顶点	Vertex / Node	图中的基本元素，代表研究对象
边	Edge / Arc	连接两个顶点的关系，可有向或无向
邻接	Adjacency	两顶点由边直接相连
关联	Incidence	边与其端点之间的关系
度	Degree	与顶点关联的边数；有向图分为入度 $\deg^{-} (v)$ 和出度 $\deg^{+} (v)$

握手定理：对于任意图 $G = (V, E)$ ，所有顶点度数之和等于边数的两倍：

\sum_{v \in V} \deg (v) = 2 | E |

1.2 图的分类

分类维度	类型	说明
方向性	无向图 / 有向图	边是否具有方向
权重	无权图 / 加权图	边是否赋予数值权重
连通性	连通图 / 非连通图	任意两顶点间是否存在路径
环路	有环图 / 无环图（DAG）	是否包含环路
密度	稀疏图 / 稠密图	边数相对于 $
特殊结构	二部图 / 完全图 / 平面图 / 树	满足特定拓扑约束的图

1.3 路径与连通性

路径 (Path)：顶点序列 $v_{0}, v_{1}, \dots, v_{k}$ ，其中相邻顶点由边相连
简单路径：不重复经过顶点的路径
环路 (Cycle)：起点与终点相同的路径，长度 $\geq 3$
连通分量：无向图中的极大连通子图
强连通分量 (SCC)：有向图中任意两点可互达的极大子图，可用 Tarjan 或 Kosaraju 算法求解

二、图的表示与存储

图在计算机中的存储方式直接影响算法效率。详见图。

表示方法	空间复杂度	查边	遍历邻居	适用场景
邻接矩阵	$O (V^{2})$	$O (1)$	$O (V)$	稠密图、频繁查边
邻接表	$O (V + E)$	$O (\deg (v))$	$O (\deg (v))$	稀疏图、遍历为主
边列表	$O (E)$	$O (E)$	$O (E)$	Kruskal 等按边操作的算法
链式前向星	$O (V + E)$	$O (\deg (v))$	$O (\deg (v))$	竞赛常用，内存紧凑

三、图的遍历

图的遍历是几乎所有图算法的基础。详见图的遍历。

3.1 深度优先搜索 (DFS)

沿一条路径尽可能深入，回溯后再探索其他分支。时间复杂度 $O (V + E)$ 。

应用：连通分量检测、环路检测、拓扑排序、强连通分量（Tarjan 算法）。

3.2 广度优先搜索 (BFS)

逐层向外扩展，使用队列实现。时间复杂度 $O (V + E)$ 。

应用：无权图最短路径、层序遍历、二部图判定。

相关页面：深度优先搜索、广度优先搜索

四、最短路径问题

最短路径是图论中最重要的优化问题之一。详见最短路径算法。

算法	适用条件	时间复杂度	核心策略
Dijkstra	非负权边，单源	$O (E \log V)$ （优先队列）	贪心算法
Bellman-Ford	可处理负权边，单源	$O (V E)$	动态规划 / 松弛
SPFA	Bellman-Ford 的队列优化	平均 $O (E)$ ，最差 $O (V E)$	松弛 + 队列
Floyd算法	全源最短路径	$O (V^{3})$	动态规划
Johnson	全源，稀疏图	$O (V^{2} \log V + V E)$	Bellman-Ford + Dijkstra

五、生成树与连通性

5.1 最小生成树 (MST)

在加权连通无向图中，找到边权之和最小的生成树。详见最小生成树。

算法	策略	时间复杂度	适用场景
Kruskal	按边权排序，逐边加入（并查集判环）	$O (E \log E)$	稀疏图
Prim	从单点扩展，每次加最小跨边	$O (E \log V)$ （优先队列）	稠密图

切割性质：对于图的任意切割，跨越切割的最小权边必定属于某棵 MST。

5.2 连通性相关问题

桥与割点：删除后使图不再连通的边/点，可用 Tarjan 算法 $O (V + E)$ 求解
边/点连通度：使图不连通所需删除的最少边/点数
强连通分量：有向图中的极大强连通子图

六、经典图论问题

6.1 欧拉路径与回路

研究是否能不重复地遍历图中所有边。详见欧拉路径。

欧拉回路存在条件：连通图中每个顶点度数为偶数
欧拉路径存在条件：恰好有 0 或 2 个奇度顶点

6.2 拓扑排序

对有向无环图 (DAG) 的顶点进行线性排序。详见拓扑排序。

Kahn 算法（BFS）：反复删除入度为 0 的顶点
DFS 后序逆序

应用：任务调度、编译依赖、课程先修关系。

6.3 网络流

研究网络中的最大传输量。详见最大流问题。

最大流最小割定理：网络最大流量等于最小割的容量
Ford-Fulkerson 方法、Edmonds-Karp 算法、Dinic 算法

6.4 图着色

用最少颜色为顶点着色，使得相邻顶点颜色不同。

色数 $χ (G)$ ：所需最少颜色数
四色定理：任何平面图 $χ (G) \leq 4$
图着色是 NP 完全问题

6.5 匹配问题

在图中找到最大的边集，使得没有两条边共享端点。

二部图最大匹配：匈牙利算法 $O (V E)$
最大权匹配：Kuhn-Munkres (KM) 算法

6.6 旅行商问题 (TSP)

寻找经过所有顶点恰好一次并返回起点的最短回路。NP-hard 问题，常用近似算法和启发式方法求解。

七、图论的应用领域

领域	应用	对应图论概念
计算机网络	路由协议（OSPF）	最短路径
社交网络	社区发现、影响力传播	连通分量、中心性
交通规划	GPS 导航、物流优化	最短路径、网络流
编译器	依赖分析、寄存器分配	拓扑排序、图着色
电路分析	网络拓扑、KVL/KCL	树、回路
生物信息学	蛋白质交互网络	图聚类
推荐系统	用户-物品关系	二部图匹配
运筹学	资源分配、调度	网络流、匹配

八、学习路径

unknown

基本概念 → 图的存储 → 遍历（DFS/BFS）
    ↓
最短路径（Dijkstra → Bellman-Ford → Floyd）
    ↓
最小生成树（Kruskal / Prim）
    ↓
拓扑排序 → 强连通分量
    ↓
网络流 → 匹配 → 图着色
    ↓
NP 问题（TSP、图着色、哈密顿回路）

延伸读物：

Bondy & Murty,《Graph Theory》——经典数学向参考书
CLERTA（Cormen 等），《算法导论》第六部分——算法实现向
Diestel,《Graph Theory》——研究生级别参考

线性代数视角

给有向图任意固定边方向后，可以构造关联矩阵 $A$ ：行对应边，列对应节点，每条有向边只含一个 $- 1$ 和一个 $+ 1$ 。若 $x$ 是节点电势，则 $A x$ 给出每条边的电势差。对连通图， $A x = 0$ 表示所有边上电势差都为 $0$ ，所以零空间由常向量 $(c, c, \dots, c)$ 构成，秩为 $n - 1$ 。

回路会使关联矩阵的行相关，树的边则给出独立行。平面连通图中，若只数有界小回路，则维数计数可写成

nodes - edges + small loops = 1,

这与通常的 Euler 公式 $V - E + F = 2$ 是同一件事的不同计数方式。

树、完全图与环路的矩阵对比

设连通图有 $n$ 个节点、 $m$ 条边。任意给每条边选定参考方向后，可取边为行、节点为列的关联矩阵 $A \in R^{m \times n}$ 。一条从节点 $i$ 指向节点 $j$ 的边，对应行在第 $i$ 列为 $- 1$ 、第 $j$ 列为 $+ 1$ ，其余为 $0$ 。这个方向只是代数参考方向；实际流量可以为负，表示沿反方向流动。

树是连通且无环的图，满足 $m = n - 1$ 。树的 $n - 1$ 条边给出 $A$ 的 $n - 1$ 个独立行，没有独立环路。
完全图 $K_{n}$ 连接每一对不同节点，边数达到最大值 $m = \frac{n (n - 1)}{2}$ 。例如 $K_{4}$ 有 $4$ 个节点、 $6$ 条边，但关联矩阵秩仍为 $3$ ，多出的 $3$ 个自由度来自独立环路。
每加入一条不属于生成树的边，就形成一个基本环路，并带来一条行相关关系。消元时，环路对应的依赖会变成零行；保留下来的非零行可看作某棵生成树的边。

因此，连通图的维数关系是

rank (A) = n - 1, \dim N (A^{T}) = m - n + 1.

其中 $m - n + 1$ 正是独立环路数。若图有 $c$ 个连通分量，则秩降为 $n - c$ ，独立环路数变为 $m - n + c$ ，每个连通分量各自允许一个常数电势自由度。

四个基本子空间

关联矩阵把线性代数四个基本子空间直接翻译成图论语言：

子空间	维数（连通图）	图论含义
$N (A)$	$1$	所有节点电势相等， $x = (c, c, \dots, c)$ ，边上电势差为零
$C (A^{T})$	$n - 1$	由生成树边张成的割空间或节点势差空间
$C (A)$	$n - 1$	可由节点电势产生的边电压差，必须绕任意环路求和为零
$N (A^{T})$	$m - n + 1$	环路流空间，电流沿闭合环路循环时每个节点仍保持平衡

电路语言中， $A x$ 是边电压差；若 $y$ 是边电流，则节点平衡写成

A^{T} y = f .

这里 $f$ 是外部注入或抽取的节点流量，符号取决于“流入为正”还是“流出为正”的约定。没有外部源汇时 $f = 0$ ，环路流正好落在 $N (A^{T})$ 中。平面连通图若只计有界小环路，Euler 计数

n - m + (m - n + 1) = 1

说明“节点、边、独立环路”的维数平衡与拓扑计数是一回事。