图论相关概念

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

图

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

常用 表示图。

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

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

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

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

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

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

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

图 的点数 也被称作图 的 阶 (order)。

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

相邻

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

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

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

度数

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

对于无向简单图，有 。

握手定理（又称图论基本定理）：对于任何无向图 ，有 。

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

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

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

若 ，则称 为 偶点 (even vertex)。

若 ，则称 为 奇点 (odd vertex)。图中奇点的个数是偶数。

若 ，则称 为 支配点 (universal vertex)。

对一张图，所有节点的度数的最小值称为 的 最小度 (minimum degree)，记作 ；最大值称为 最大度 (maximum degree)，记作 。即：，。

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

对于任何有向图 ，有：

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

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

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

简单图

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

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

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

鸽巢原理）

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

路径

途径 (walk)：途径是连接一连串顶点的边的序列，可以为有限或无限长度。形式化地说，一条有限途径 是一个边的序列 ，使得存在一个顶点序列 满足 ，其中 。这样的途径可以简写为 。通常来说，边的数量 被称作这条途径的 长度（如果边是带权的，长度通常指途径上的边权之和，题目中也可能另有定义）。

迹 (trail)：对于一条途径 ，若 两两互不相同，则称 是一条迹。

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

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

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

子图

对一张图 ，若存在另一张图 满足 且 ，则称 是 的 子图 (subgraph)，记作 。

若对 ，满足 ，只要 ，均有 ，则称 是 的 导出子图/诱导子图 (induced subgraph)。

容易发现，一个图的导出子图仅由子图的点集决定，因此点集为 () 的导出子图称为 导出的子图，记作 。

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

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

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

如果有向图 的导出子图 满足 ，有 ，则称 为 的一个 闭合子图 (closed subgraph)。

连通

无向图

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

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

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

有向图

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

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

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

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

相关算法请参见

强连通分量。

割

相关算法请参见

割点和桥 以及

双连通分量。

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

对于连通图 ，若 且 （即从 中删去 中的点）不是连通图，则 是图 的一个 点割集 (vertex cut/separating set)。大小为一的点割集又被称作 割点 (cut vertex)。

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

对于图 以及 满足 ， 和 不相邻， 可达 ，若 ，，且在 中 和 不连通，则 被称作 到 的点割集。 到 的最小点割集的大小被称作 到 的 局部点连通度 (local connectivity)，记作 。

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

对于连通图 ，若 且 （即从 中删去 中的边）不是连通图，则 是图 的一个 边割集 (edge cut)。大小为一的边割集又被称作 桥 (bridge)。

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

对于图 以及 满足 ， 可达 ，若 ，且在 中 和 不连通，则 被称作 到 的边割集。 到 的最小边割集的大小被称作 到 的 局部边连通度 (local edge-connectivity)，记作 。

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

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

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

Whitney 定理：对任意的图 ，有 。（不等式中的三项分别为点连通度、边连通度、最小度。）

稀疏图/稠密图

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

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

这两个概念并没有严格的定义，一般用于讨论

时间复杂度 为 的算法与 的算法的效率差异（在稠密图上这两种算法效率相当，而在稀疏图上 的算法效率明显更高）。

补图

对于无向简单图 ，它的 补图 (complement graph) 指的是这样的一张图：记作 ，满足 ，且对任意节点对 ， 当且仅当 。

反图

对于有向图 ，它的 反图 (transpose graph) 指的是点集不变，每条边反向得到的图，即：若 的反图为 ，则 。

特殊的图

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

边集为空的图称为 无边图 (edgeless graph)、空图 (empty graph) 或 零图 (null graph)， 阶无边图记作 或 。 与 互为补图。

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

若无向简单图 的所有边恰好构成一个圈，则称 为 环图/圈图 (cycle graph)，() 阶圈图记作 。易知，一张图为圈图的充分必要条件是，它是 - 正则连通图。

若无向简单图 满足，存在一个点 为支配点，其余点之间没有边相连，则称 为 星图/菊花图 (star graph)，() 阶星图记作 。

若无向简单图 满足，存在一个点 为支配点，其它点之间构成一个圈，则称 为 轮图 (wheel graph)，() 阶轮图记作 。

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

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

树基础。

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

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

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

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

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

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

二分图。

如果一张图可以画在一个平面上，且没有两条边在非端点处相交，那么这张图是一张 平面图 (planar graph)。一张图的任何子图都不是 或 是其为一张平面图的充要条件。对于简单连通平面图 且 ，。

同构

两个图 和 ，如果存在一个双射 ，且满足 ，当且仅当 ，则我们称 为 到 的一个 同构 (isomorphism)，且图 与图 是 同构的 (isomorphic)，记作 。

从定义可知，若 ，必须满足：

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

无向简单图的二元运算

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

交 (intersection)：图 的交定义成图 。

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

并 (union)：图 的并定义成图 。

和 (sum)/直和 (direct sum)：对于 ，任意构造 使得 ( 可以等于 )。此时与 同构的任何图称为 和 的和/直和/不交并，记作 或 。

若 与 的点集本身不相交，则 。

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

特殊的点集/边集

支配集

对于无向图 ，若 且 存在边 满足 ，则 是图 的一个 支配集 (dominating set)。

无向图 最小的支配集的大小记作 。求一张图的最小支配集是

NP 困难 的。

对于有向图 ，若 且 存在边 满足 ，则 是图 的一个 出 - 支配集 (out-dominating set)。类似地，可以定义有向图的 入 - 支配集 (in-dominating set)。

有向图 最小的出 - 支配集大小记作 ，最小的入 - 支配集大小记作 。

边支配集

对于图 ，若 且 存在 中的边与其有公共点，则称 是图 的一个 边支配集 (edge dominating set)。

求一张图的最小边支配集是

NP 困难 的。

独立集

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

图 最大的独立集的大小记作 。求一张图的最大独立集是

NP 困难 的。

匹配

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

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

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

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

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

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

#P 完全 的。

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

托特定理： 阶无向图 有完美匹配当且仅当对于任意的 ，奇，其中 奇 表示奇数阶连通分支数。

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

点覆盖

对于图 ，若 且 满足 的至少一个端点在 中，则称 是图 的一个 点覆盖 (vertex cover)。

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

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

NP 困难 的。

一张图的任何一个匹配的大小都不超过其任何一个点覆盖的大小。完全二分图 的最大匹配和最小点覆盖大小都为 。

边覆盖

对于图 ，若 且 满足 与 中的至少一条边相邻，则称 是图 的一个 边覆盖 (edge cover)。

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

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

一张图的最小边覆盖的大小加上最大匹配的大小等于图的点数，即 。

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

一张图的任何一个独立集的大小都不超过其任何一个边覆盖的大小。完全二分图 的最大独立集和最小边覆盖大小都为 。

团

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

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

一张图的最大团的大小记作 ，最大团的大小等于其补图最大独立集的大小，即 。求一张图的最大团是

NP 困难 的。

参考资料

OI 中转站 - 图论概念梳理

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

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

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