图论相关概念

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

Warning

图论相关定义在不同教材中往往会有所不同，遇到的时候需根据上下文加以判断。

图

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

常用表示图。

当都是有限集合时，称为 有限图。

当或是无限集合时，称为 无限图。

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

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

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

为什么起点是 tail，终点是 head？

边通常用箭头表示，而箭头是从「尾」指向「头」的。

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

若的每条边都被赋予一个数作为该边的权，则称为 赋权图。如果这些权都是正实数，就称为 正权图。

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

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

相邻

在无向图中，若点是边的一个端点，则称和是 关联的 (incident) 或 相邻的 (adjacent)。对于两顶点和，若存在边，则称和是 相邻的 (adjacent)。

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

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

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

简单图

自环 (loop)：对中的边，若，则被称作一个自环。

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

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

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

Warning

在无向图中和算一组重边，而在有向图中， $u \to v$ 和 $v \to u$ 不为重边。

Warning

在题目中，如果没有特殊说明，是可以存在自环和重边的，在做题时需特殊考虑。

度数

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

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

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

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

若，则称为 孤立点 (isolated vertex)。

若，则称为 叶节点 (leaf vertex)/悬挂点 (pendant vertex)。

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

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

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

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

在有向图中，以一个顶点为起点的边的条数称为该顶点的 出度 (out-degree)，记作。以一个顶点为终点的边的条数称为该节点的 入度 (in-degree)，记作。显然。

对于任何有向图，有：

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

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

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

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

路径

途径 (walk)：途径是连接一连串顶点的边的序列，可以为有限或无限长度。形式化地说，一条有限途径是一个边的序列 $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$ 。通常来说，边的数量被称作这条途径的长度（如果边是带权的，长度通常指途径上的边权之和，题目中也可能另有定义）。

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

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

回路 (circuit)：对于一条迹，若，则称是一条回路。

环/圈 (cycle)（又称 简单回路/简单环 (simple circuit)）：对于一条回路，若是点序列中唯一重复出现的点对，则称是一个环。

Warning

关于路径的定义在不同地方可能有所不同，如，「路径」可能指本文中的「途径」，「环」可能指本文中的「回路」。如果在题目中看到类似的词汇，且没有「简单路径」/「非简单路径」（即本文中的「途径」）等特殊说明，最好询问一下具体指什么。

子图

对一张图，若存在另一张图满足 $V' \subseteq V$ 且 $E' \subseteq E$ ，则称是的 子图 (subgraph)，记作 $H \subseteq G$ 。

若对 $H \subseteq G$ ，满足 $\forall u, v \in V'$ ，只要 $(u, v) \in E$ ，均有 $(u, v) \in E'$ ，则称是的 导出子图/诱导子图 (induced subgraph)。

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

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

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

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

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

连通

无向图

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

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

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

有向图

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

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

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

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

割

相关算法请参见割点和桥以及双连通分量。

在本部分中，有向图的「连通」一般指「强连通」。

对于连通图，若 $V'\subseteq V$ 且 $G\left[V\setminus V'\right]$ （即从中删去中的点）不是连通图，则是图的一个 点割集 (vertex cut/separating set)。大小为一的点割集又被称作 割点 (cut vertex)。

对于连通图和整数，若 $|V|\ge k+1$ 且不存在大小为的点割集，则称图是 - 点连通的 (-vertex-connected)，而使得上式成立的最大的被称作图的 点连通度 (vertex connectivity)，记作 $\kappa(G)$ 。（对于非完全图，点连通度即为最小点割集的大小，而完全图的点连通度为。）

对于图以及 $u, v\in V$ 满足 $u\ne v$ ，和不相邻，可达，若 $V'\subseteq V$ ， $u, v\notin V'$ ，且在 $G\left[V\setminus V'\right]$ 中和不连通，则被称作到的点割集。到的最小点割集的大小被称作到的 局部点连通度 (local connectivity)，记作 $\kappa(u, v)$ 。

还可以在边上作类似的定义：

对于连通图，若 $E'\subseteq E$ 且 $G' = (V, E\setminus E')$ （即从中删去中的边）不是连通图，则是图的一个 边割集 (edge cut)。大小为一的边割集又被称作 桥 (bridge)。

对于连通图和整数，若不存在大小为的边割集，则称图是 - 边连通的 (-edge-connected)，而使得上式成立的最大的被称作图的 边连通度 (edge connectivity)，记作 $\lambda(G)$ 。（对于任何图，边连通度即为最小边割集的大小。）

对于图以及 $u, v\in V$ 满足 $u\ne v$ ，可达，若 $E'\subseteq E$ ，且在 $G'=(V, E\setminus E')$ 中和不连通，则被称作到的边割集。到的最小边割集的大小被称作到的 局部边连通度 (local edge-connectivity)，记作 $\lambda(u, v)$ 。

点双连通 (biconnected) 几乎与 - 点连通完全一致，除了一条边连接两个点构成的图，它是点双连通的，但不是 - 点连通的。换句话说，没有割点的连通图是点双连通的。

边双连通 (-edge-connected) 与 - 边双连通完全一致。换句话说，没有桥的连通图是边双连通的。

与连通分量类似，也有 点双连通分量 (biconnected component)（极大点双连通子图）和 边双连通分量 (-edge-connected component)（极大边双连通子图）。

Whitney 定理：对任意的图，有 $\kappa(G)\le \lambda(G)\le \delta(G)$ 。（不等式中的三项分别为点连通度、边连通度、最小度。）

稀疏图/稠密图

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

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

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

补图

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

反图

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

特殊的图

若无向简单图满足任意不同两点间均有边，则称为 完全图 (complete graph)，阶完全图记作。若有向图满足任意不同两点间都有两条方向不同的边，则称为 有向完全图 (complete digraph)。

边集为空的图称为 无边图 (edgeless graph)、空图 (empty graph) 或 零图 (null graph)，阶无边图记作 $\overline{K}_n$ 或。与互为补图。

Warning

零图 (null graph) 也可指 零阶图 (order-zero graph) ，即点集与边集均为空的图。

若有向简单图满足任意不同两点间都有恰好一条边（单向），则称为 竞赛图 (tournament graph)。

若无向简单图 $G = \left( V, E \right)$ 的所有边恰好构成一个圈，则称为 环图/圈图 (cycle graph)，( $n \geq 3$ ) 阶圈图记作。易知，一张图为圈图的充分必要条件是，它是 - 正则连通图。

若无向简单图 $G = \left( V, E \right)$ 满足，存在一个点为支配点，其余点之间没有边相连，则称为 星图/菊花图 (star graph)，( $n \geq 1$ ) 阶星图记作。

若无向简单图 $G = \left( V, E \right)$ 满足，存在一个点为支配点，其它点之间构成一个圈，则称为 轮图 (wheel graph)，( $n \geq 3$ ) 阶轮图记作。

若无向简单图 $G = \left( V, E \right)$ 的所有边恰好构成一条简单路径，则称为 链 (chain/path graph)，阶的链记作。易知，一条链由一个圈图删去一条边而得。

如果一张无向连通图不含环，则称它是一棵 树 (tree)。相关内容详见树基础。

如果一张无向连通图包含恰好一个环，则称它是一棵 基环树 (pseudotree)。

如果一张有向弱连通图每个点的入度都为，则称它是一棵 基环外向树。

如果一张有向弱连通图每个点的出度都为，则称它是一棵 基环内向树。

多棵树可以组成一个 森林 (forest)，多棵基环树可以组成 基环森林 (pseudoforest)，多棵基环外向树可以组成 基环外向树森林，多棵基环内向树可以组成 基环内向森林 (functional graph)。

如果一张无向连通图的每条边最多在一个环内，则称它是一棵 仙人掌 (cactus)。多棵仙人掌可以组成沙漠。

如果一张图的点集可以被分为两部分，每一部分的内部都没有连边，那么这张图是一张 二分图 (bipartite graph)。如果二分图中任何两个不在同一部分的点之间都有连边，那么这张图是一张 完全二分图 (complete bipartite graph/biclique)，一张两部分分别有个点和个点的完全二分图记作 $K_{n, m}$ 。相关内容详见二分图。

如果一张图可以画在一个平面上，且没有两条边在非端点处相交，那么这张图是一张 平面图 (planar graph)。一张图的任何子图都不是或 $K_{3, 3}$ 是其为一张平面图的充要条件。对于简单连通平面图且 $V\ge 3$ ， $|E|\le 3|V|-6$ 。

同构

两个图和，如果存在一个双射 $f : V(G) \to V(H)$ ，且满足 $(u,v)\in E(G)$ ，当且仅当 $(f(u),f(v))\in E(H)$ ，则我们称为到的一个 同构 (isomorphism)，且图与图是 同构的 (isomorphic)，记作 $G \cong H$ 。

从定义可知，若 $G \cong H$ ，必须满足：

和结点度的非增序列相同
和存在同构的导出子图

无向简单图的二元运算

对于无向简单图，我们可以定义如下二元运算：

交 (intersection)：图 $G = \left( V_1, E_1 \right), H = \left( V_2, E_2 \right)$ 的交定义成图 $G \cap H = \left( V_1 \cap V_2, E_1 \cap E_2 \right)$ 。

容易证明两个无向简单图的交还是无向简单图。

并 (union)：图 $G = \left( V_1, E_1 \right), H = \left( V_2, E_2 \right)$ 的并定义成图 $G \cup H = \left( V_1 \cup V_2, E_1 \cup E_2 \right)$ 。

和 (sum)/直和 (direct sum)：对于 $G = \left( V_1, E_1 \right), H = \left( V_2, E_2 \right)$ ，任意构造 $H' \cong H$ 使得 $V \left( H' \right) \cap V_1 = \varnothing$ ( 可以等于 )。此时与 $G \cup H'$ 同构的任何图称为和的和/直和/不交并，记作或 $G \oplus H$ 。

若与的点集本身不相交，则 $G \cup H = G + H$ 。

比如，森林可以定义成若干棵树的和。

并与和的区别

可以理解为，「并」会让两张图中「名字相同」的点、边合并，而「和」则不会。

特殊的点集/边集

支配集

对于无向图，若 $V'\subseteq V$ 且 $\forall v\in(V\setminus V')$ 存在边 $(u, v)\in E$ 满足 $u\in V'$ ，则是图的一个 支配集 (dominating set)。

无向图最小的支配集的大小记作 $\gamma(G)$ 。求一张图的最小支配集是 NP 困难的。

对于有向图，若 $V'\subseteq V$ 且 $\forall v\in(V\setminus V')$ 存在边 $(u, v)\in E$ 满足 $u\in V'$ ，则是图的一个 出 - 支配集 (out-dominating set)。类似地，可以定义有向图的 入 - 支配集 (in-dominating set)。

有向图最小的出 - 支配集大小记作 $\gamma^+(G)$ ，最小的入 - 支配集大小记作 $\gamma^-(G)$ 。

边支配集

对于图，若 $E'\subseteq E$ 且 $\forall e\in(E\setminus E')$ 存在中的边与其有公共点，则称是图的一个 边支配集 (edge dominating set)。

求一张图的最小边支配集是 NP 困难的。

独立集

对于图，若 $V'\subseteq V$ 且中任意两点都不相邻，则是图的一个 独立集 (independent set)。

图最大的独立集的大小记作 $\alpha(G)$ 。求一张图的最大独立集是 NP 困难的。

匹配

对于图，若 $E'\in E$ 且中任意两条不同的边都没有公共的端点，且中任意一条边都不是自环，则是图的一个 匹配 (matching)，也可以叫作 边独立集 (independent edge set)。如果一个点是匹配中某条边的一个端点，则称这个点是 被匹配的 (matched)/饱和的 (saturated)，否则称这个点是 不被匹配的 (unmatched)。

边数最多的匹配被称作一张图的 最大匹配 (maximum-cardinality matching)。图的最大匹配的大小记作 $\nu(G)$ 。

如果边带权，那么权重之和最大的匹配被称作一张图的 最大权匹配 (maximum-weight matching)。

如果一个匹配在加入任何一条边后都不再是一个匹配，那么这个匹配是一个 极大匹配 (maximal matching)。最大的极大匹配就是最大匹配，任何最大匹配都是极大匹配。极大匹配一定是边支配集，但边支配集不一定是匹配。最小极大匹配和最小边支配集大小相等，但最小边支配集不一定是匹配。求最小极大匹配是 NP 困难的。

如果在一个匹配中所有点都是被匹配的，那么这个匹配是一个 完美匹配 (perfect matching)。如果在一个匹配中只有一个点不被匹配，那么这个匹配是一个 准完美匹配 (near-perfect matching)。

求一张普通图或二分图的匹配或完美匹配个数都是 #P 完全的。

对于一个匹配，若一条路径以非匹配点为起点，每相邻两条边的其中一条在匹配中而另一条不在匹配中，则这条路径被称作一条 交替路径 (alternating path)；一条在非匹配点终止的交替路径，被称作一条 增广路径 (augmenting path)。

托特定理：阶无向图有完美匹配当且仅当对于任意的 $V' \subset V(G)$ ， $p_{\text{odd}}(G-V')\leq |V'|$ ，其中 $p_{\text{odd}}$ 表示奇数阶连通分支数。

托特定理（推论）：任何无桥 3 - 正则图都有完美匹配。

点覆盖

对于图，若 $V'\subseteq V$ 且 $\forall e\in E$ 满足的至少一个端点在中，则称是图的一个 点覆盖 (vertex cover)。

点覆盖集必为支配集，但极小点覆盖集不一定是极小支配集。

一个点集是点覆盖的充要条件是其补集是独立集，因此最小点覆盖的补集是最大独立集。求一张图的最小点覆盖是 NP 困难的。

一张图的任何一个匹配的大小都不超过其任何一个点覆盖的大小。完全二分图 $K_{n, m}$ 的最大匹配和最小点覆盖大小都为 $\min(n, m)$ 。

边覆盖

对于图，若 $E'\subseteq E$ 且 $\forall v\in V$ 满足与中的至少一条边相邻，则称是图的一个 边覆盖 (edge cover)。

最小边覆盖的大小记作 $\rho(G)$ ，可以由最大匹配贪心扩展求得：对于所有非匹配点，将其一条邻边加入最大匹配中，即得到了一个最小边覆盖。

最大匹配也可以由最小边覆盖求得：对于最小边覆盖中每对有公共点的边删去其中一条。

一张图的最小边覆盖的大小加上最大匹配的大小等于图的点数，即 $\rho(G)+\nu(G)=|V(G)|$ 。

一张图的最大匹配的大小不超过最小边覆盖的大小，即 $\nu(G)\le\rho(G)$ 。特别地，完美匹配一定是一个最小边覆盖，这也是上式取到等号的唯一情况。

一张图的任何一个独立集的大小都不超过其任何一个边覆盖的大小。完全二分图 $K_{n, m}$ 的最大独立集和最小边覆盖大小都为 $\max(n, m)$ 。

团

对于图，若 $V'\subseteq V$ 且中任意两个不同的顶点都相邻，则是图的一个 团 (clique)。团的导出子图是完全图。

如果一个团在加入任何一个顶点后都不再是一个团，则这个团是一个 极大团 (maximal clique)。

一张图的最大团的大小记作 $\omega(G)$ ，最大团的大小等于其补图最大独立集的大小，即 $\omega(G)=\alpha(\bar{G})$ 。求一张图的最大团是 NP 困难的。

参考资料

OI 中转站 - 图论概念梳理

Wikipedia（以及相关概念的对应词条）

离散数学（修订版），田文成周禄新编著，天津文学出版社，P184-187

戴一奇，胡冠章，陈卫。图论与代数结构 [M]. 北京：清华大学出版社，1995.

本页面最近更新：2024/1/3 13:30:44，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：ouuan, Backl1ght, CCXXXI, EndlessCheng, Enter-tainer, Great-designer, IceySakura, Ir1d, Kaiser-Yang, mgt, shuzhouliu, sshwy, Steaunk, StudyingFather, Tiphereth-A, xiaoh1024, zidian257, zjxx
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用