图论

概述

图论（Graph Theory）研究由顶点（vertex）和边（edge）构成的数学结构——图（graph），是离散数学的核心分支之一，也是算法导论第6篇（图算法）的数学基础。

定义

形式化定义

一个图 $G=(V,E)$ 由两个集合组成：

• 顶点集 $V$：有限非空集合，元素称为顶点（vertex）或节点（node）
• 边集 $E$：由 $V$ 中元素的无序对（或有序对）构成的集合，元素称为边（edge）

根据 $E$ 中元素的性质，图分为两大类：

• 无向图（undirected graph）：$E\subseteq \{\{u,v\}\mid u,v\in V\}$，边无方向
• 有向图（directed graph / digraph）：$E\subseteq V\times V$，边 $(u,v)$ 有方向，$u$ 为尾（tail），$v$ 为头（head）

基本概念

图的分类

分类维度	类型	说明
方向性	有向图 / 无向图	边是否有方向
权重	加权图 / 无权图	边是否带有数值权重
多重性	简单图 / 多重图	是否允许自环和重边
连通性	连通图 / 非连通图	任意两顶点间是否存在路径

关键术语

• 邻接（adjacency）：若 $(u,v)\in E$，则 $u$ 和 $v$ 互为邻接顶点
• 度（degree）：无向图中顶点 $v$ 的度 $d(v)$ = 与 $v$ 关联的边数；有向图分为入度（in-degree）和出度（out-degree）
• 路径（path）：顶点序列 $v_0,v_1,\dots ,v_k$，其中相邻顶点间均有边相连
• 环/回路（cycle/circuit）：起点与终点相同的路径，且边不重复
• 连通（connected）：无向图中任意两顶点间存在路径
• 连通分量（connected component）：图的极大连通子图
• 强连通（strongly connected）：有向图中任意两顶点互相可达

图的表示

• 邻接矩阵（adjacency matrix）：$|V|\times |V|$ 矩阵 $A$，$A[i][j]=1$ 当且仅当 $(i,j)\in E$。空间 $O(V^2)$，适合稠密图
• 邻接表（adjacency list）：每个顶点维护其邻居列表。空间 $O(V+E)$，适合稀疏图

核心性质

• 握手定理（Handshaking Lemma）：无向图中所有顶点的度之和 $=2|E|$
• 有向图中所有顶点的入度之和 $=$ 出度之和 $=|E|$
• 任何图中度数为奇数的顶点个数必为偶数
• 含 $n$ 个顶点的连通无向图至少有 $n-1$ 条边（树）

应用场景

图论是算法导论第6篇（图算法）的核心数学基础，具体应用包括：

• 最短路径：Dijkstra算法、Bellman-Ford算法、Floyd-Warshall算法
• 最小生成树：Kruskal算法、Prim算法
• 网络流：最大流问题、最大流最小割定理
• 匹配：二分匹配、二部图上的最大匹配
• 拓扑排序：有向无环图（DAG）的线性排列
• 强连通分量：Tarjan算法、Kosaraju算法

参见

• 二部图
• 完全图
• 最大流
• 二分匹配