图论常见定理，和各种特殊的图

· · 个人记录

合订版

二部图就是二分图。 定理：最小点覆盖和最大独立集互为补集。 证明：分别表示成整数规划的形式，观察性质。 最小点覆盖：$n$ 个变量 $x_i\in\{0,1\}$，满足 $\forall (a,b)\in E,x_a+x_y\ge 1$，最小化 $\sum_{i}x_i$。 最大独立集：$n$ 个变量 $x_i\in\{0,1\}$，满足 $\forall (a,b)\in E,x_a+x_y\le 1$，最大化 $\sum_{i}x_i$。 容易看出它们互为补集。 # 一些基本定理的证明和拓展 ## 门杰（Menger）定理 定义： 对于一个有向图 $G=(V,E)$，$x,y\in V,x\neq y$，记 $\mathscr P_{x,y}(G)$ 是 $G$ 中始 $x$ 终 $y$ 的路径集，$P,Q\in \mathscr P_{x,y}$。 若 $V(P)\cap V(Q)=\{x,y\}$，则称它们内点不交。 若 $E(P)\cap E(Q)=\mathbb\empty$，则称它们边不交。 若 $\forall P,Q\in \mathscr P_{x,y}(G),P\neq Q$，$P,Q$ 都是内点不交的，则称 $\mathscr P_{x,y}(G)$ 是 $G$ 中内点不交的 $(x,y)$ 路集。类似地定义 $G$ 中边不交的 $(x,y)$ 路集。 用 $\zeta_G(x,y)$ 与 $\eta_G(x,y)$ 分别表示 $G$ 中内点不交和边不交的 $(x,y)$ 路径的最大条数。 $G$ 中最小 $(x,y)$ 割中的边数定义为 $G$ 的 $(x,y)$-边连通度，记作 $\lambda_G(x,y)$。类似地在无向图上定义 $\lambda_G(x,y)$。 引理：$\forall x,y\in G,\eta_G(x,y)\le\lambda_G(x,y)$。 证明：比较显然，至少要在边不交的路径集中每条选择一条割边。 边形式的门杰定理：$\forall x,y\in G,\eta_G(x,y)=\lambda_G(x,y)$。 证明：定义一个整流量网络 $N=\left(G_{x,y},C\right)$，其中函数 $\bm c$ 满足 $\forall e\in E,\bm c(e)=1$。由最大流最小割定理立即得其上存在最大流 $\bm f$ 与最小割 $B=\left(S,\bar{S}\right)$，使得 $$\mathrm{val}\,\bm f=\mathrm{cap}\,B$$ 引理已经帮助我们证明一部分，因此我们接下来要证明的就只有 $$\eta_G(x,y)\ge\mathrm{val}\,\bm f,\mathrm{cap}\, B\ge\lambda_G(x,y)$$ 令 $H$ 是由 $G$ 中满足 $\bm f(e)\neq 0$ 的边构成的集合的导出子图。由定义得此时 $\bm f(e)=1$。因而可得 $$d_H^+(x)-d_H^-(x)=\mathrm{val}\,\bm f=d_H^-(y)-d_H^+(y)\\\forall v\in V(H)\setminus\{x,y\},d_H^+(v)=d_H^-(v)$$ 因此 $H$ 是 $\mathrm{val}\,\bm f$ 条边不交的 $(x,y)$ 路之并，即 $\eta_G(x,y)\ge \mathrm{val}\,\bm f$。 又由于 $\forall e\in E,\bm c(e)=1$，所以 $\mathrm{cap}\,B=|B|\ge \lambda_G(x,y)$，定理得证。 在无向图上也有类似的定理，证法类似。 还有点形式的门杰定理，这里不再展开。但是证明方式不太一样。 ## 柯尼希（Kőnig）定理 引理：对于一般图 $G=(V,E)$，$\alpha'(G)\le\beta(G)$。 证明：比较显然，至少要在匹配的边的端点中二选一。 柯尼希定理：对于二部图 $G=(V,E)$，$\alpha'(G)=\beta(G)$。 证明：记其左、右部点集分别为 $L,R$，在 $G$ 基础上添加两个点 $s,t$，并从 $s$ 到所有 $l\in L$ 连边，所有 $r\in R$ 到 $t$ 连边。 由点形式的门杰定理可知，$s,t$ 之间最大内点不交的路径个数等于其 $(s,t)$-点连通度，记作 $\zeta_G(x,y)=\kappa_G(x,y)$。以下简记它们的值为 $k$。 首先可知这些路径的长度都至少为 $3$，所以可以在 $G$ 中找到 $k$ 个匹配，所以 $\alpha'(G)\ge k$。 再设 $(s,t)$-最小点割集为 $S$。于是 $S\sube V$。 接下来断言 $S$ 是一个点覆盖。若不是，则有 $e\in E$ 未被覆盖，则存在 $s,t$ 间一条路径，与 $S$ 是 $(s,t)$-最小点割集矛盾。因此 $\beta(G)\le k$。 至此我们证明了 $\alpha'(G)\ge\beta(G)$。再结合引理可知，$\alpha'(G)=\beta(G)$，定理得证。 ## 霍尔（Hall）定理 霍尔定理：对于二部图 $G=(V,E)$，其左、右部点集分别为 $L,R$，假设 $|L|\le|R|$。则如下两种表述等价： $(a):$ $G$ 存在一种匹配，使得 $L$ 中点都有对应的 $R$ 中点。 $(b):$ $\forall T\sube L,|T|\le|N_G(T)|$，其中 $N_G(T)$ 指的是 $G$ 中 $T$ 中点的邻居集合。 易证 $\forall T\sube L,N_G(T)\sube R$，反之亦然。 证明：我们将分别证明 $(a)\Rightarrow(b)$ 与 $(b)\Rightarrow(a)$。 $(a)\Rightarrow(b)$：令 $S$ 是一个使得 $L$ 中点都有对应的 $R$ 中点的匹配。则可以构造一个函数 $f:L\to R$ 使得 $f(x)$ 的值为它的匹配。由于 $S$ 是匹配，所以 $f$ 自然是双射。因此 $\forall T\sube L$，由于 $f(T)\sube N_G(T)$，可知 $|T|=|f(T)|\le|N_G(T)|$。 $(b)\Rightarrow(a)$：先考虑最简单的情况。对于 $|L|=1$ 时，由于 $|N_G(L)|\ge |L|$存在一条边连接唯一一个 $l\in L$ 与 $R$ 中任意一点，把这条边记作 $lr$。因而 $S=\{lr\}$ 是一个满足条件的匹配。 接下来假设 $\forall L'\sub L,R'\sub R$，若对于 $L',R'$ 而言满足 $(b)$，则满足 $(a)$，接下来从两个方面证明 $L,R$ 间的关系： 情况一：$\forall T\subsetneq L,T\neq\mathbb\empty$，都有 $|T|<|N_G(T)|$。 选择 $l\in L,r\in N_G(L)$，然后删去这两个点及与它相连的边。记现在的图为 $G'$。则有 $\forall A\sube L\setminus\{l\}$，都有 $$|N_{G'}(A)|\ge|N_G(A)|-1\ge|A|$$ 前一个大于等于比较好说，后一个成立是因为 $A\sub L$。因此根据假设，存在 $L\setminus\{l\}$ 与 $R\setminus\{r\}$ 的一个满足条件的匹配 $S'$，那么 $S'\cup\{lr\}$ 就是 $L$ 与 $R$ 的一个满足条件的匹配。 情况二：$\exist A\subsetneq L,A\neq\mathbb\empty,|A|=|N_G(A)|$。 记 $G$ 在点集 $A\cup N_G(A)$ 上的导出子图 为 $H$，$G$ 删去 $A\cup N_G(A)$ 及与它相连的边后得到的图为 $I$。因此它们均为二部图。接下来证明它们都满足 $(b)$。 $H$ 满足 $(b)$：任取 $T\sube A$，因此有 $N_H(T)=N_G(T)$，所以 $|N_H(T)|=|N_G(T)|\ge|T|$，得证。 $I$ 满足 $(b)$：任取 $T'\sube L\setminus A$，结合上面假设，我们有 $$\left|N_I\left(T'\right)\right|=|N_G(T'\cup A)|-|N_G(A)|\ge|T'\cup A|-|A|=|T'|$$ 这样就说明了 $I$ 满足 $(b)$，得证。 至此，由于 $|A|<|L|,|L\setminus A|<|L|$，$H,I$ 都存在各自的满足条件的匹配 $S_H$ 与 $S_I$。因此 $G$ 的一个满足条件的匹配 $S=S_H\cup S_I$，定理得证。 拓展：若 $|L|\le|R|$，则最大匹配数为 $|L|-\max_{T\sube L}(|T|-N_G(T),0)$。 ## 曼特尔（Mantel）定理 曼特尔定理：对于一个 $n$ 点无向简单图 $G$，若 $m>\frac{n^2}{4}$，则 $G$ 有三元环。 证明：归纳 $n$。 - $n\le 3$：显然。 - 假设对于 $|V|\le n-1$，定理都成立。对于 $n$ 个点的 $G$，假设 $|E|=\frac{n^2}{4}+1$，任选 $e=uv\in E$，$H=(V',E')$ 为 $G$ 中 $V\setminus\{u,v\}$ 的诱导子图。分类讨论： - 如果 $|E'|>\frac{(n-2)^2}{4}$，则 $H$ 有三元环。 - 否则 $H$ 与 $\{u,v\}$ 之间至少有 $\left(\frac{n^2}{4}+1\right)-\frac{(n-2)^2}{4}-1=n-1$ 条边。由抽屉原理可得 $H$ 中至少有一个点和 $u,v$ 都相邻，结合 $e$ 的存在性，可知 $G$ 有三元环。 定理得证。 它的拓展是图兰（Turán）定理： 若 $n$ 点无向简单图 $G=(V,E)$ 满足 $m>\frac{p-2}{2(p-1)}n^2$，则 $G$ 包含大小为 $p$ 的团。 证明和上面的类似。 证明：归纳 $n$。 - $n<p$：显然。 - 假设对于 $|V|<n-1$，定理都成立。假设 $G$ 已包含大小为 $p-1$ 的团 $C$，剩下的记作 $R$。因此 $|E(R)|\le \frac{p-2}{2(p-2)}(n-p+1)^2$。由于假设，$C,R$ 间的边数 $E(C,R)\le (p-2)(n-p+1)$。所以有 $$\begin{aligned}|E|&=|E(C)|+|E(C,R)|+|E(R)|\\ &\le{n-1\choose 2}+\frac{p-2}{2(p-1)}(n-p+1)^2+(p-2)(n-p+1)\\&=\frac{p-2}{2(p-1)}n^2\end{aligned}$$ 定理得证。 # 各种图 ## 竞赛图 定义：竞赛图是点两两之间都有一条有向边的图。 竞赛图缩点后呈链状，且前面的点向后面的所有点连边。 证明：若 $x,y$ 不在一个强连通分量里，由于一定有 $x\to y$ 或 $y\to x$，则缩点后是全序的，命题得证。 定理：竞赛图有哈密顿路径。 证明：归纳竞赛图点数 $n$。$n=1$ 时显然。假设点数为 $n-1$ 时有哈密顿路径，不妨设就是 $1\to 2\to \cdots \to n-1$，那么： - 若有边 $n\to 1$ 或 $n-1\to n$，直接放进去。 - 否则（即 $1\to n$ 且 $n\to n-1$），则一定存在一个 $x\in [1,n-2]$ 使得 $x\to n,n\to x+1$，放进去。 综上，定理得证。 这样做的时间复杂度是 $\mathcal O\left(n^2\right)$ 的。 定理（Camion）：强连通的竞赛图有哈密顿回路。 证明：首先它一定有一条哈密顿路径，不妨设就是 $1\to 2\to\cdots\to n$。接下来寻找最大的 $t$，使得存在边 $1\to t+1,1\to t+2,\dots 1\to n$。于是有环 $1\to 2\to \cdots\to t\to 1$，尝试将 $t+1,t+2,\dots,n$ 塞进环中。 由于一定存在一条从不在环上的点到在环上的点的边（不然就不强连通了），记作 $x\to y$，又由于 $1\to x$，可以找到环上一点 $1\le z\le y$ 使得 $z\to x\to z+1$。 综上，定理得证。 这样做的时间复杂度也是 $\mathcal O\left(n^2\right)$ 的。 没查过论文，不知道有没有更好的做法。 这就可以做[P3561](https://www.luogu.com.cn/problem/P3561)了。 兰道（Landau）定理：存在竞赛图 $G$ 满足每个点 $i$ 的出度为 $s_i$ 当且仅当将 $s$ 从小到大排序，$\forall k\in[1,n],\sum_{i=1}^k s_i\ge {k\choose 2}$ 且 $k=n$ 时等号成立。 证明：必要性显然，前 $k$ 个点的导出子图已经有 $k\choose 2$ 条边了。接下来证明充分性。 考虑从一个特殊的出度序列 $r$ 开始不断调整，直到它变成 $s$。 这个序列是 $r_i=i-1$。显然它有对应的竞赛图：从 $n$ 开始满足要求即可。 若 $r$ 和 $s$ 不完全一致，我们可以找到一个最小的不同位置 $x$ 使得 $r_x\neq s_x$。可以发现这其实预示着 $r_x<s_x$。 接下来考虑将 $r_x$ 不断扩大，直到 $r_x'=s_x$。 找到最大的 $y$ 使得 $r_x=r_{x+1}=\cdots=r_y$，再找到最小的 $z$ 使得 $r_z>s_z$。于是 $z>y$。 综上，得到 $r_z>s_z\ge s_y>r_x$，因此 $r_z-r_x\ge 2$。 这意味着 $\exist p,z\to p\to x$。将这两条边反转，于是 $r_x\gets r_x+1,r_z\gets r_z-1$。 这样就实现了 $r_x\gets r_x+1$，不断增量最终一定可以使 $r,s$ 完全一致。综上，定理成立。 还有拓展：记 $s$ 从小到大排序后的序列为 $p$，则 $G$ 中所有强连通分量在 $p$ 中构成连续段，且 $k$ 是其中一个区间的右端点当且仅当 $\sum_{i=1}^k s_{p_i}={k\choose 2}$。 若将兰道定理中的出度换成入度，很好证明结论仍然成立。 现在你可以不用询问做[CF1498E](https://www.luogu.com.cn/problem/CF1498E)了。 定理：$n(n\ge 4)$ 个点的强连通竞赛图存在 $n-1$ 个点的强连通子图。 证明：将大小为 $n-1$ 的竞赛图 $G$ 分解成 $k$ 个强连通分量，拓扑序排序后的序列为 $a_1,a_2\dots a_k$，加入点 $n$ 和对应的边后的新竞赛图 $G'$ 是强连通的。分类讨论： - $k=1$，显然成立。 - $k\ge 3$：一定存在 $a_k\to n,n\to a_1$，否则不强连通。可以在 $a_2,a_3,\dots,a_{k-1}$ 中任选一点删掉，任意两点 $u,v$ 都可以通过类似 $u\to a_k\to n\to a_1\to v$ 的方式走过去，因此这样做之后原图仍强连通。 - $k=2$：由于 $n\ge 4$，$a_1,a_2$ 中一定可以找到一个有至少 $2$ 个元素，不妨设就是 $a_1$，在其中删一个点。在 $a_1$ 中选择一点 $r$ 满足 $r\to n$，在 $a_1$ 中构建以 $r$ 为根的生成树（或是支配树？），任意删去一个叶子节点即可。 定理得证。 定理：$n(n\ge 4)$ 个点的强连通竞赛图可以翻转以一个点为端点的所有边的方向（以下简称翻转点），使得操作后的图仍强连通。 证明：根据 $n-1$ 个点的强连通子图的存在性，可以翻转剩下那个点，使得强连通性质不变。定理得证。 定理：$n(n\ge 7)$ 个点的竞赛图可以翻转至多一个点使得操作后的图强连通。 证明：仍然设 $G$ 分解成 $k$ 个强连通分量，拓扑序排序后的序列为 $a_1,a_2\dots a_k$。分类讨论： - $k=1$：不需翻转。 - $k\ge 3$：任意翻转 $a_2,a_3,\dots a_{k-1}$ 中的一个点 $x$。 - $k=2$：此时 $a_1,a_2$ 中一定可以找到一个有至少 $4$ 个元素，不妨设就是 $a_1$。根据上面定理，可以在里面翻转一个点，使得 $a_1$ 仍强连通，且出现边 $a_2\to a_1$。 综上，定理得证。 这样就可以做[CF1268D](https://www.luogu.com.cn/problem/CF1268D)了。$n<7$ 时暴力枚举即可，用兰道定理判定是否强连通，时间复杂度 $\mathcal O\left(n^2\right)$（桶排实现）。 定理：若竞赛图中有环，则一定有三元环。 证明：先找到任意一个环 $c_1,c_2,\dots,c_k$，其中 $c_i\to c_{i\bmod k+1}$。假设不存在包含 $c_1$ 的三元环，那么由于 $c_1\to c_2\to c_3$，因此 $c_1\to c_3$，以此类推。可知 $c_1\to c_i(1<i\le k)$，与 $c_k\to c_1$ 矛盾。因此，一定存在包含 $c_1$ 的三元环，定理得证。 定理：竞赛图中任一 $k\ge 3$ 个点的强连通分量中一定存在 $[3,k]$ 元环。 证明：$k=3$ 时显然，否则可以发现上面“$k-1$ 个点的强连通子图的存在性”已经告诉我们这一点，不断规约使 $k\gets k-1$ 即可。因此定理得证。 竞赛图三元环计数。 三个点之间的关系只有两种：出度要么是 $1,1,1$，要么是 $0,1,2$。因此假设一个点的出度为 $d$，则它会使三元环个数减少 $\frac{d^2-d}{2}$（它指向的那些点两两配对的结果，即${d\choose 2}$），则最终答案为 $${n\choose 3}-\sum_{i=1}^n\frac{d_i^2-d_i}{2}$$ 例题：[CF1264E](https://www.luogu.com.cn/problem/CF1264E) 题目简述：一张 $n(n\le 50)$ 点的竞赛图，一些边定了向而另一些不确定，欲最小化定向后的三元环个数，请你求出这个值。单测。 由于 $\sum_{i=1}^nd_i=\frac{n^2-n}{2}$ 是个定值，所以只需要让 $\sum_{i=1}^nd_i^2$ 最小。 用所谓“差分建图”，将 $d^2$ 表示成 $1+3+5+\cdots$，然后跑费用流。由于费用流先选小边的性质，可以保证正确性。 这样的时间复杂度是 $\mathcal O\left(n^6\right)$，但是远远跑不满。 竞赛图三元环期望。 就是上面那个题把“最小化”变成了“期望个数”。 和上面类似，利用补集容斥计算。这里直接说结论：令 $d_i$ 表示 $i$ 的出度，$u_i$ 表示以 $i$ 为端点的未确定方向的边数，则答案为 $${n\choose 3}-\sum_{i=1}^n\left(\frac{d_i^2-d_i}{2}+\frac{d_iu_i}{2}+\frac{u_i^2-u_i}{8}\right)$$ 有定理：任意竞赛图 $T$ 与它的补图 $\overline{T}$ 的哈密顿路径和哈密顿回路的条数都是相同的。 证明：这个就不能找我了，见[论文](https://arxiv.org/abs/2101.00713)。 ## 广义串并联图 广义串并联图是一种不存在 $K_4$ 的细分的图。它是平面图。为了叙述简便，接下来讨论的所有图都是连通的。 它最被广为人知的性质是通过广义串并联图方法后可以缩成一个孤立点。广义串并联图方法包括删一度点，缩二度点，叠合重边。$K_4$ 也是最小的不能缩成孤立点的图，因为每个点的度数都 $\ge 3$。 这种缩点很好的地方在于可以在缩的块上维护性质，比如 DP 之类的。 有定理：对于任意一张满足 $m-n\le k$ 的无向图，使用广义串并联图方法后的小图一定有 $n\le 2k,m\le 3k$。 证明：较为简单，缩到最后所有点的度数一定至少为三，一条多余的边可以贡献两个度数，就可以简单看出来了。 因此在这样的小图上就可以运用某些复杂度更高的算法（比如搜索）了。 例题：[[SNOI2020] 生成树](https://www.luogu.com.cn/problem/P6790) 首先可以证明这样的图一定是广义串并联图。 接下来设计 $dp_{e,0/1}$ 表示编号为 $e$ 的边选或不选的方案数。接下来对广义串并联图方法中的每一个加以讨论： - 删一度点：令唯一一条和它相连的边为 $e$，直接令 $ans\gets ans\times dp_{e,1}$。 - 缩二度点：不选新边的方案数为两条边仅选一条的方案数之和，否则点被孤立。选新边的方案数即为两条边均选的方案数。 - 叠合重边：选新边的方案数为两条重边中仅选一条的方案数之和，不选新边的方案数为两条重边均不选的方案数。 由此可以快速计算。实际实现中可以使用 `map` 存储边的编号，使用拓扑排序维护广义串并联图方法。 例题：寻找一个 $m-n\le k$ 的图的三染色方案，或报告无解。$n\le 10^5,k\le 8$。 可以简单地用 $dp_{e,c1,c2}$ 表示对于 $e=uv$ 这条边，$u$ 的颜色和 $v$ 的颜色能否分别同时为 $c1$ 和 $c2$，其中 $c1,c2\in\{0,1,2\}$。接下来的讨论和上面的结构类似，这里就不再阐述了。对于缩完的小图，直接搜索即可。 例题：寻找一个点数最多的无法再用广义串并联图方法缩的图，满足 $m-n\le k$。 直接搞两个长度相等的环，环间编号相同的相连即可。这样每个点的度数都为 $3$，且无浪费。 事实上，这种合并和 top cluster 很类似，所以可以用数据结构维护，乃至可以动态 DP，这里就不深入了。