图论 • CoderXL's Blog

图论部分简介 - OI Wiki ↗

图论 (Graph theory) 是数学的一个分支，图是图论的主要研究对象．图 (Graph) 是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系．顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系．

图的更多可视化推荐转到 D3 Graph Theory ↗。

图的概念#

顶点与边#

定义图 $G=(V,E)$ 是一个二元组。非空集 $V$ 称为点集（Vertex Set），其中的元素称为顶点（Vertex, Vertices）或节点（Node）；可重集 $E$ 称为边集（Edge Set），其中的元素称为边（Edge）。图的顶点数 $\lvert V \rvert$ 被称为图的阶（order）。

图分为 无向图 (undirected graph)，有向图 (directed graph) 等。

flowchart LR
	A((A)) --- B((B)) --- C((C)) --- D((D))
	A --- C
	B --- D
	A --- E((E))
	B --- E

无向图

flowchart LR
	A((A)) --> B((B)) --> C((C)) ---> D((D))
	A --> C
	D --> B
	A --> E((E))
	B ---> E

有向图

在无向图中， $E$ 中的元素是无序二元组 $e=\{u,v\}$ ，称为无向边， $u,v \in V$ 就是它所连接的端点（endpoint）。为了统一，有时也将无序二元组记作 $(u,v)$ .

在有向图中， $E$ 中的元素是有序二元组 $e=(u,v)$ ，也可写作 $u\to v$ ，称为有向边。 $u,v \in V$ 就是它所连接的端点（endpoint），其中 $u$ 是起点， $v$ 是终点。

在很多运行在图上的算法中，可以将无向图视作「每个边都被一对相反的边替换后」的有向图。

度量#

权#

边可以被赋予一个数，称为边的权。每条边都被赋权的图称为赋权图，如果权都是正实数，则成为正权图。

在一些问题中，也会给顶点赋权。

度#

无向图中，与顶点 $v$ 连接的边的条数称为 $v$ 的度（degree），记作 $d(v)$ . 在有向图中，以 $v$ 为起点的边的条数称为 $v$ 的出度（out-degree），记作 $d^+(v)$ ；以 $v$ 为终点的边的条数称为 $v$ 的入度（in-degree），记作 $d^-(v)$ ；出度与入度的和称为度，即 $d(v)=d^+(v)+d^-(v)$ .

握手定理：一张图中所有顶点的度之和等于边数的两倍，即 $\sum_{v\in V} d(v) = 2\lvert E \rvert$ .

推论：一张图中，「度为奇数的顶点」一定有偶数个。

对于有向图，进一步有 $\sum_{v\in V} d^+(v) = \sum_{v\in V} d^-(v) = \lvert E \rvert$ .

结构#

自环（loop）：对于 $e = (u,v) \in E$ ，如果 $u=v$ ，那么称 $e$ 为一个自环。在一些语境下，“环”指自环，而不是下文提到的环（cycle）。为了不致混淆，本文中均用环指代 cycle，自环指代 loop.

重边（multiple edge）：若 $E$ 中存在两个完全相同的元素（边） $e_1, e_2$ ，则它们被称作（一组）重边。在一些语境下，“平行边”指重边。

简单图：没有自环和重边的图称为简单图。

途径 (walk)：途径是连接一连串顶点的边的序列，可以为有限或无限长度。形式化地说，一条有限途径 $w$ 是一个边的序列 $e_1,e_2,\dots,e_k$ ，使得存在一个顶点序列 $v_1, v_2,\dots, v_k$ 满足 $e_i = (v_{i-1},v_i)$ ，其中 $i\in [1,k]$ . 这样的途径可以简写为 $v_0 \to v_1 \to v_2 \to \cdots \to v_k$ . 通常来说，边的数量 $k$ 被称作这条途径的长度（如果边是带权的，那么长度通常指途径上的边权之和）。

迹 (trail)：对于一条途径 $w$ ，若 $e_1,e_2,\dots,e_k$ 两两互不相同，则称 $w$ 是一条迹。

路径 (path)：对于一条迹 $w$ ，若其连接的点的序列中点两两不同，则称 $w$ 是一条路径。

回路 (circuit)：对于一条迹 $w$ ，若 $v_0 = v_k$ ，则称 $w$ 是一条回路。

环/圈 (cycle)：对于一条回路 $w$ ，若 $v_0=v_k$ 是点序列中唯一重复出现的点对，则称 $w$ 是一个环。自环也是一种环。

子图#

对一张图 $G = (V, E)$ ，若存在另一张图 $H = (V', E')$ 满足 $V' \subseteq V$ 且 $E' \subseteq E$ ，则称 $H$ 是 $G$ 的 子图 (subgraph)，记作 $H \subseteq G$ . 如果 $H \ne G$ ，可以进一步记作 $H \subsetneq G$ .

若 $H \subseteq G$ 满足 $V' = V$ ，则称 $H$ 为 $G$ 的 生成子图/支撑子图 (spanning subgraph)。

补图#

对于简单无向图 $G=(V,E)$ ，其补图 $\overline{G}=(V,\overline{E})$ 定义为：先以它的顶点构建一张完全图，再从中除去 $E$ 中的边得到的图。

形式化地，就是 $\overline{E} = \{(u,v) \mid u,v\in V, (u,v) \notin E\}$ .

同构#

如果两张图 $G_1 = (V_1, E_1),\ G_2 = (V_2, E_2)$ 的点集和边集分别都能存在双射，那么 $G_1$ 和 $G_2$ 就是同构的。

连通#

无向图的连通性#

对于一张无向图 $G = (V, E)$ ，对于 $u, v \in V$ ，若存在一条途径使得 $v_0 = u, v_k = v$ ，则称 $u$ 和 $v$ 是 连通的 (connected)。由定义，任意一个顶点和自身连通，任意一条边的两个端点连通。

若无向图 $G = (V, E)$ ，满足其中任意两个顶点均连通，则称 $G$ 是 连通图 (connected graph)。

若 $H$ 是 $G$ 的一个连通子图，且不存在 $F$ 满足 $H\subsetneq F \subseteq G$ 且 $F$ 为连通图，则 $H$ 是 $G$ 的一个 连通块/连通分量 (connected component)（极大连通子图）．

有向图的连通性#

对于一张有向图 $G = (V, E)$ ，对于 $u, v \in V$ ，若存在一条途径使得 $v_0 = u, v_k = v$ ，则称 $u$ 可达 $v$ . 由定义，任意一个顶点可达自身，任意一条边的起点可达终点。（无向图中的连通也可以视作双向可达。）

若一张有向图的节点两两互相可达，则称这张图是 强连通的 (strongly connected)。有时也称无向连通图是强连通的。

类比无向图的连通分量，可以定义有向图的 强连通分量（Strongly Connected Component, SCC）。

特殊的图#

完全图：若无向简单图 $G$ 满足任意不同两点间均有边，则称 $G$ 为 完全图。

稀疏图 (sparse graph)：边数 $\lvert E \rvert$ 远小于点数的平方 $\lvert V \rvert^2$ 的图称为稀疏图。

稠密图 (sparse graph)：边数 $\lvert E \rvert$ 接近点数的平方 $\lvert V \rvert^2$ 的图称为稠密图。可以说完全图是简单图中最稠密的情况。

有向无环图（Directed Acyclic Graph, DAG）：若有向图 $G$ 不含环，则称 $G$ 为有向无环图。

锦标赛图/竞赛图（Tournament Graph）：如果有向图 $G$ 中的每条边都被替换为一条无向边之后，形成的图是一个完全图，则称 $G$ 为锦标赛图。锦标赛图的任何两个顶点之间都有且只有一条有向边。

二分图/二部图（Bipartite Graph）：如果一张图 $G=(V,E)$ 的顶点集合 $V$ 可以被分为两部分 $X$ 和 $Y$ ，使得 $X \cup Y = V$ 且 $X \cap Y = \varnothing$ ，并且任何 $e=(u,v) \in E$ ，都有 $u \in X \Leftrightarrow v \in Y$ ，那么就称 $G$ 为二分图。通俗地说，二分图就是能把顶点分为两部分，且两部分顶点内部之间没有连边的图。

树#

树（tree） 是没有环的无向连通图。

树一些性质也可以作为其等价定义：

有 $n$ 个结点， $n-1$ 条边的连通无向图
任意两个结点之间有且仅有一条路径的简单无向图
没有环，且在任意不同两点间添加一条边之后所得图含唯一的一个环的图

由树直接并置形成的图称为森林。

如果给树指定一个顶点作为根，那么这棵树就是有根树，否则是无根树。

无根树的结构#

叶子节点（leaf node）：度数不超过 $1$ 的节点。

有根树的结构#

*图片来自 OI Wiki.

父亲（parent node）：对于除根以外的每个结点，定义为从该结点到根路径上的第二个结点。根结点没有父结点。
祖先（ancestor）：一个结点到根结点的路径上，除了它本身外的结点。根结点的祖先集合为空。
子结点（child node）：如果 $u$ 是 $v$ 的父亲，那么 $v$ 是 $u$ 的子结点。子结点的顺序一般不加以区分，二叉树是一个例外。
结点的深度（depth）：到根结点的路径上的边数。
树的高度（height）：所有结点的深度的最大值。
兄弟（sibling）：同一个父亲的多个子结点互为兄弟。
后代（descendant）：子结点和子结点的后代。或者理解成：如果 $u$ 是 $v$ 的祖先，那么 $v$ 是 $u$ 的后代。
叶子节点（leaf node）：没有子节点的节点。这个定义与无根树叶子节点的定义有所差别，它实际上排除了度为 $1$ 的根节点被算作叶子节点的可能性。

子树（subtree）：删掉与父亲相连的边后，该结点所在的子图。

特殊的树#

*图片来自 OI Wiki.

有根二叉树（rooted binary tree）：每个结点最多只有两个儿子（子结点）的有根树称为二叉树。常常对两个子结点的顺序加以区分，分别称之为左子结点和右子结点。大多数情况下，二叉树 一词均指有根二叉树。
完整二叉树（full/proper binary tree）：每个结点的子结点数量均为 $0$ 或者 $2$ 的二叉树。换言之，每个结点或者是树叶，或者左右子树均非空。

完全二叉树（complete binary tree）：只有最下面两层结点的度数可以小于 2，且最下面一层的结点都集中在该层最左边的连续位置上。

完美二叉树（perfect binary tree） / 满二叉树：所有叶结点的深度均相同，且所有非叶节点的子节点数量均为 2 的二叉树称为完美二叉树。

图的存储#

邻接矩阵#

对于 $G=(V,E)$ ，建立一张 $\lvert V \rvert \times \lvert V \rvert$ 的矩阵 $\boldsymbol{A}$ ，其中每个元素 $\boldsymbol{A}_{u,v} \in \{0,1\}$ 表示是否存在边 $u\to v$ . 对于赋权图来说，可以令 $\boldsymbol{A}_{u,v}$ 的值等于边 $u \to v$ 的权值。

可以看出，邻接矩阵只能用于没有重边的图；无向图的邻接矩阵是对称矩阵。

查询某条边的存在性： $O(1)$ . 遍历某个点的所有出边： $O(\lvert V \rvert)$ . 遍历整张图： $O(\lvert V \rvert^2)$ . 空间复杂度 $O(\lvert V \rvert^2)$ .

邻接矩阵在稀疏图上时空效率均很低，在稠密图上却往往优于其他存储方式（因为内存缓存机制对邻接矩阵优化更好）。

邻接表#

如果某个顶点的出边远没有 $\lvert V \rvert$ 那么多，那么邻接矩阵中的很多元素都将是空的。如果我们可以根据点的实际出边数量分配空间，那么存图的空间效率以及遍历出边的时间复杂度都能得到优化。

邻接表的思想就是：对每个节点使用一个可以动态扩容的列表，维护其出边。

使用 C++ STL 库的 std::vector 可以方便地实现邻接表。此外，还可以手动用链表实现邻接表，该方法称为链式前向星。

查询某条边 $(u,v)$ 是否存在： $O(d^+(u))$ ；如果事先排好序，可以用二分查找优化到 $O(\log d^+(u))$ . 遍历点 $u$ 的所有出边： $O(d^+(u))$ . 遍历整张图： $O(\lvert V \rvert + \lvert E \rvert)$ . 空间复杂度： $O(\lvert E \rvert)$ .