图论 · lianqingyun

Graph Theory 图论

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

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

一、基本概念与术语

1.1 图的要素

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

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

$\sum_{v \in V} de g (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 (de g (v))$	$O (de g (v))$	稀疏图、遍历为主
边列表	$O (E)$	$O (E)$	$O (E)$	Kruskal 等按边操作的算法
链式前向星	$O (V + E)$	$O (de g (v))$	$O (de g (v))$	竞赛常用，内存紧凑

三、图的遍历

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

3.1 深度优先搜索 (DFS)

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

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

3.2 广度优先搜索 (BFS)

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

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

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

四、最短路径问题

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

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

五、生成树与连通性

5.1 最小生成树 (MST)

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

算法	策略	时间复杂度	适用场景
Kruskal	按边权排序，逐边加入（并查集判环）	$O (E lo g E)$	稀疏图
Prim	从单点扩展，每次加最小跨边	$O (E lo g 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	树、回路
生物信息学	蛋白质交互网络	图聚类
推荐系统	用户-物品关系	二部图匹配
运筹学	资源分配、调度	网络流、匹配

八、学习路径

基本概念 → 图的存储 → 遍历（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	与顶点关联的边数；有向图分为入度 $de g^{-} (v)$ 和出度 $de g^{+} (v)$

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

$\sum_{v \in V} de g (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 (de g (v))$	$O (de g (v))$	稀疏图、遍历为主
边列表	$O (E)$	$O (E)$	$O (E)$	Kruskal 等按边操作的算法
链式前向星	$O (V + E)$	$O (de g (v))$	$O (de g (v))$	竞赛常用，内存紧凑

三、图的遍历

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

3.1 深度优先搜索 (DFS)

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

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

3.2 广度优先搜索 (BFS)

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

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

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

四、最短路径问题

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

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

五、生成树与连通性

5.1 最小生成树 (MST)

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

算法	策略	时间复杂度	适用场景
Kruskal	按边权排序，逐边加入（并查集判环）	$O (E lo g E)$	稀疏图
Prim	从单点扩展，每次加最小跨边	$O (E lo g 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	树、回路
生物信息学	蛋白质交互网络	图聚类
推荐系统	用户-物品关系	二部图匹配
运筹学	资源分配、调度	网络流、匹配

八、学习路径

基本概念 → 图的存储 → 遍历（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

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

怜清韵

图论

一、基本概念与术语

1.1 图的要素

1.2 图的分类

1.3 路径与连通性

二、图的表示与存储

三、图的遍历

3.1 深度优先搜索 (DFS)

3.2 广度优先搜索 (BFS)

四、最短路径问题

五、生成树与连通性

5.1 最小生成树 (MST)

5.2 连通性相关问题

六、经典图论问题

6.1 欧拉路径与回路

6.2 拓扑排序

6.3 网络流

6.4 图着色

6.5 匹配问题

6.6 旅行商问题 (TSP)

七、图论的应用领域

八、学习路径

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

一、基本概念与术语

1.1 图的要素

1.2 图的分类

1.3 路径与连通性

二、图的表示与存储

三、图的遍历

3.1 深度优先搜索 (DFS)

3.2 广度优先搜索 (BFS)

四、最短路径问题

五、生成树与连通性

5.1 最小生成树 (MST)

5.2 连通性相关问题

六、经典图论问题

6.1 欧拉路径与回路

6.2 拓扑排序

6.3 网络流

6.4 图着色

6.5 匹配问题

6.6 旅行商问题 (TSP)

七、图论的应用领域

八、学习路径

线性代数视角

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

四个基本子空间

关系图谱

最新笔记

知识集

lianqingyun

实践论

秋水

Basic-Concepts

目录

反向链接