图的相关概念

一张图 $G$ 由点集 $V$ 和边集 $E$ 构成。我们用 $d(v)$ 代表节点 $v$ 的度数，如果 $d(v)=|V|-1$，则称 $v$ 为支配点。如果每个点的度数都是 $k$，则该图为 $k-$正则图。

子图

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

若对 $H \subseteq G$，满足 $\forall u, v \in V'$，只要 $(u, v) \in E$，均有 $(u, v) \in E'$，则称 $H$ 是 $G$ 的导出子图。点集为 $V'(V' \subseteq V)$ 的导出子图称为 $V'$ 导出的子图，记作 $G \left[ V' \right]$。

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

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

如果有向图 $G = (V, E)$ 的导出子图 $H = G \left[ V^\ast \right]$ 满足 $\forall v \in V^\ast, (v, u) \in E$，有 $u \in V^\ast$，则称 $H$ 为 $G$ 的一个闭合子图。也就是说，图内部是闭合的，不存在一个点在导出子图内，可以通过原图的一条边连到一个不在导出子图内的点。

特殊的图

对于无向简单图，所有本来在图上的边都不在，本来不在的都在，那么这个图就是原无向图的补图。

对于有向图，每条边的方向取反，得到的图就是原图的反图。

特殊集合

一些特殊的点和边的集合有着特殊的意义，这里我们介绍一些常见的。

支配集

对于无向图，如果一个点集的点可以连接到原图的所有点，那么这个点集为原图的支配集。

最小支配集是 NPH 的，我们通常使用 $O(2^n)$ 的枚举算法来求解支配集。

独立集

就是任意两点不相邻的点集。对于树和二分图我们有高效做法，但是一般图上，这个问题是 NPH 的。

匹配

对于图 $G=(V,E)$，若 $E'\in E$ 且 $E'$ 中任意两条边都没有公共端点，且 $E'$ 中没有自环，那么 $E'$ 是 $G$ 的一个匹配，也称为边独立集。如果一个点被匹配的边连接了，那么它就是被匹配的，否则就是不被匹配的。

边数最多的称为最大匹配，如果边带权，那么权重之和最大的匹配称为图的最大权匹配。

如果一个匹配在加入任何一条边后都不再是一个匹配，那么这个匹配就是极大匹配，最大匹配一定是极大匹配。

如果所有点都被匹配了，那么这个匹配是完美匹配。如果在一个匹配中只有一个点不被匹配，那么该匹配为准完美匹配。

对于一个匹配 $M$，若一条路径以非匹配点为起点，每相邻两条边中的一条在匹配中而另一条不在匹配中，那么这条路径称为交替路径；一条非匹配点终止的交替路径称为增广路径。

点覆盖

如果所有边都至少有一个端点在这个点集中，那么这个点集被称为点覆盖集。

点覆盖集一定是支配集，但是极小点覆盖集不一定是极小支配集（考虑一个三元环）。

点覆盖集拥有以下性质：

• 一个点集是点覆盖的充要条件是其补集是独立集。
• 一张图的任何一个匹配的大小都不超过其任何一个点覆盖的大小。

边覆盖

当前边集满足任何一个点都至少是其中一条边的一个端点，那么这个边集称为边覆盖集。

如果知道了最大匹配，那么将所有非匹配点都连一条边加入最大匹配，那么就得到了一个最小边覆盖。同理，如果知道了最小边覆盖，那么将有公共点的边删去到只剩一条就得到了最大匹配。

团

一个图的子点集 $V'$ 中任意两个不同的顶点都相邻，则称 $V'$ 是图 $G$ 的一个团。团对应的导出子图是完全图。说白了最大团就是最大完全子图。

求解一个图的最大团是 NPH 的，可以使用最大团搜索算法（在暴力枚举的基础上加一个不可能成为答案的最优性剪枝）来解决规模较小的图的问题。

例题

你可能会问：这里为什么有题呢？嗯，主要是建立在图结构上的一些奇奇怪怪的问题。

[CF1810E] Monsters

Portal.

如果直接做的话，考虑一个被一个大点分割成两部分的图，这样左半部分和右半部分都是跑满的。

但实际上，如果一个出生点可以从另一个出生点走过来，那么这个出生点就没必要重新计算了。我直觉感觉这玩意儿是 $O(n\log n)$ 的，但是这不对。

设 $D(x)$ 表示 $x$ 为出生点可以走到的点集。假设 $u\in D(x),D(y)$，而且 $|D(x)|< |D(y)|$，那么 $y$ 能够走到 $x$ 但是 $x$ 不能走到 $y$。以中间那个阻止 $x$ 继续前进的点分割，$y$ 必然有不小于 $x$ 的规模，因此 $2|D(x)|\le |D(y)|$。因此任意一个点最多只会被计算 $\log n$ 个有效出生点计算到。证得 $O(n\log^2 n)$。代码。