图论基本概念

本页面概述了图论中的一些概念，这些概念并不全是在 OI 中常见的，对于 OIer 来说，只需掌握本页面中的基础部分即可，如果在学习中碰到了不懂的概念，可以再来查阅。

图

图 (graph) 是一个二元组 $G=(V(G), E(G))$。其中 $V(G)$ 是非空集，称为 点集 (vertex set)，对于 $V$ 中的每个元素，我们称其为 顶点 (vertex) 或 节点 (node)，简称 点；$E(G)$ 为 $V(G)$ 各结点之间边的集合，称为 边集 (edge set)。

常用 $G=(V,E)$ 表示图。

当 $V,E$ 都是有限集合时，称 $G$ 为 有限图。

当 $V$ 或 $E$ 是无限集合时，称 $G$ 为 无限图。

图有多种，包括 无向图 (undirected graph)，有向图 (directed graph)，混合图 (mixed graph) 等。

若 $G$ 为无向图，则 $E$ 中的每个元素为一个无序二元组 $(u, v)$，称作 无向边 (undirected edge)，简称 边 (edge)，其中 $u, v \in V$。设 $e = (u, v)$，则 $u$ 和 $v$ 称为 $e$ 的 端点 (endpoint)。

若 $G$ 为有向图，则 $E$ 中的每一个元素为一个有序二元组 $(u, v)$，有时也写作 $u \to v$，称作 有向边 (directed edge) 或 弧 (arc)，在不引起混淆的情况下也可以称作 边 (edge)。设 $e = u \to v$，则此时 $u$ 称为 $e$ 的 起点 (tail)，$v$ 称为 $e$ 的 终点 (head)，起点和终点也称为 $e$ 的 端点 (endpoint)。并称 $u$ 是 $v$ 的直接前驱，$v$ 是 $u$ 的直接后继。

若 $G$ 为混合图，则 $E$ 中既有 有向边，又有 无向边。

若 $G$ 的每条边 $e_k=(u_k,v_k)$ 都被赋予一个数作为该边的 权，则称 $G$ 为 赋权图。如果这些权都是正实数，就称 $G$ 为 正权图。

图 $G$ 的点数 $\left| V(G) \right|$ 也被称作图 $G$ 的 阶 (order)。

形象地说，图是由若干点以及连接点与点的边构成的。

相邻

在无向图 $G = (V, E)$ 中，若点 $v$ 是边 $e$ 的一个端点，则称 $v$ 和 $e$ 是 关联的 (incident) 或 相邻的 (adjacent)。对于两顶点 $u$ 和 $v$，若存在边 $(u, v)$，则称 $u$ 和 $v$ 是 相邻的 (adjacent)。

一个顶点 $v \in V$ 的 邻域 (neighborhood) 是所有与之相邻的顶点所构成的集合，记作 $N(v)$。

一个点集 $S$ 的邻域是所有与 $S$ 中至少一个点相邻的点所构成的集合，记作 $N(S)$，即：

$$N(S) = \bigcup_{v \in S} N(v)$$

简单图

自环 (loop)：对 $E$ 中的边 $e = (u, v)$，若 $u = v$，则 $e$ 被称作一个自环。

重边 (multiple edge)：若 $E$ 中存在两个完全相同的元素（边）$e_1, e_2$，则它们被称作（一组）重边。

简单图 (simple graph)：若一个图中没有自环和重边，它被称为简单图。具有至少两个顶点的简单无向图中一定存在度相同的结点。

如果一张图中有自环或重边，则称它为 多重图 (multigraph)。

度数

与一个顶点 $v$ 关联的边的条数称作该顶点的 度 (degree)，记作 $d(v)$。特别地，对于边 $(v, v)$，则每条这样的边要对 $d(v)$ 产生 $2$ 的贡献。

对于无向简单图，有 $d(v) = \left| N(v) \right|$。

握手定理（又称图论基本定理）：对于任何无向图 $G = (V, E)$，有 $\sum_{v \in V} d(v) = 2 \left| E \right|$。

推论：在任意图中，度数为奇数的点必然有偶数个。

若 $d(v) = 0$，则称 $v$ 为 孤立点 (isolated vertex)。

若 $d(v) = 1$，则称 $v$ 为 叶节点 (leaf vertex)/悬挂点 (pendant vertex)。

若 $2 \mid d(v)$，则称 $v$ 为 偶点 (even vertex)。

若 $2 \nmid d(v)$，则称 $v$ 为 奇点 (odd vertex)。图中奇点的个数是偶数。

若 $d(v) = \left| V \right| - 1$，则称 $v$ 为 支配点 (universal vertex)。

对一张图，所有节点的度数的最小值称为 $G$ 的 最小度 (minimum degree)，记作 $\delta (G)$；最大值称为 最大度 (maximum degree)，记作 $\Delta (G)$。即：$\delta (G) = \min_{v \in G} d(v)$，$\Delta (G) = \max_{v \in G} d(v)$。

在有向图 $G = (V, E)$ 中，以一个顶点 $v$ 为起点的边的条数称为该顶点的 出度 (out-degree)，记作 $d^+(v)$。以一个顶点 $v$ 为终点的边的条数称为该节点的 入度 (in-degree)，记作 $d^-(v)$。显然 $d^+(v)+d^-(v)=d(v)$。

对于任何有向图 $G = (V, E)$，有：

$$\sum_{v \in V} d^+(v) = \sum_{v \in V} d^-(v) = \left| E \right|$$

若对一张无向图 $G = (V, E)$，每个顶点的度数都是一个固定的常数 $k$，则称 $G$ 为 $k$- 正则图 ($k$-regular graph)。

如果给定一个序列 a，可以找到一个图 G，以其为度数列，则称 a 是 可图化 的。

如果给定一个序列 a，可以找到一个简单图 G，以其为度数列，则称 a 是 可简单图化 的。

路径

途径 (walk)：途径是连接一连串顶点的边的序列，可以为有限或无限长度。形式化地说，一条有限途径 $w$ 是一个边的序列 $e_1, e_2, \ldots, e_k$，使得存在一个顶点序列 $v_0, v_1, \ldots, 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, \ldots, e_k$ 两两互不相同，则称 $w$ 是一条迹。

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

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

环/圈 (cycle)（又称 简单回路/简单环 (simple circuit)）：对于一条回路 $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 \subseteq G$，满足 $\forall u, v \in V'$，只要 $(u, v) \in E$，均有 $(u, v) \in E'$，则称 $H$ 是 $G$ 的 导出子图/诱导子图 (induced subgraph)。

容易发现，一个图的导出子图仅由子图的点集决定，因此点集为 $V'$($V' \subseteq V$) 的导出子图称为 $V'$ 导出的子图，记作 $G \left[ V' \right]$。

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

显然，$G$ 是自身的子图，支撑子图，导出子图；无边图是 $G$ 的支撑子图。原图 $G$ 和无边图都是 $G$ 的平凡子图。

如果一张无向图 $G$ 的某个生成子图 $F$ 为 $k$- 正则图，则称 $F$ 为 $G$ 的一个 $k$- 因子 ($k$-factor)。

如果有向图 $G = (V, E)$ 的导出子图 $H = G \left[ V^\ast \right]$ 满足 $\forall v \in V^\ast, (v, u) \in E$，有 $u \in V^\ast$，则称 $H$ 为 $G$ 的一个 闭合子图 (closed subgraph)。

连通

无向图

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

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

若 $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)。

若一张有向图的边替换为无向边后可以得到一张连通图，则称原来这张有向图是 弱连通的 (weakly connected)。

与连通分量类似，也有 弱连通分量 (weakly connected component)（极大弱连通子图）和 强连通分量 (strongly connected component)（极大强连通子图）。

相关算法请参见强连通分量。

稀疏图/稠密图

若一张图的边数远小于其点数的平方，那么它是一张 稀疏图 (sparse graph)。

若一张图的边数接近其点数的平方，那么它是一张 稠密图 (dense graph)。

这两个概念并没有严格的定义，一般用于讨论时间复杂度为 $O(|V|^2)$ 的算法与 $O(|E|)$ 的算法的效率差异（在稠密图上这两种算法效率相当，而在稀疏图上 $O(|E|)$ 的算法效率明显更高）。

补图

对于无向简单图 $G = (V, E)$，它的 补图 (complement graph) 指的是这样的一张图：记作 $\bar G$，满足 $V \left( \bar G \right) = V \left( G \right)$，且对任意节点对 $(u, v)$，$(u, v) \in E \left( \bar G \right)$ 当且仅当 $(u, v) \notin E \left( G \right)$。

反图

对于有向图 $G = (V, E)$，它的 反图 (transpose graph) 指的是点集不变，每条边反向得到的图，即：若 $G$ 的反图为 $G'=(V, E')$，则 $E'=\{(v, u)|(u, v)\in E\}$。