一些图论的定理

Part 1 公共部分

1.1 定义

补图：
- 无向图 $G$ 的补图中存在一条边 $(x,y)$ 当且仅当 $G$ 中不存在边 $(x,y)$
- 有向图 $G$ 的补图中存在一条边 $x\to y$ 当且仅当 $G$ 中不存在边 $x\to y$ ；
子图：图中某些点和它们之间的边构成的新图；
链覆盖：把图划分为若干条链的方案；
反链：满足 $\forall x,y\in S$ ， $x$ 不能到达 $y$ 且 $y$ 不能到达 $x$ 的点集 $S$ 。

1.2 定理

最小链覆盖等于最长反链

证明

考虑不得不用两条链覆盖的结构，即一个分叉，显然不同分支上的点不能相互到达，那么最长反链中的每个点都可以代表一条链。

Q.E.D.
最长链等于最小反链覆盖

证明

对于一条链，链上的任意两点都不能被放到同一个反链中，所以最小反链覆盖不大于最长链。

而对于两条链同一个位置的点，显然要么是同一个点，要么可以放到同一个反链中，所以最小反链覆盖等于最长链。

Q.E.D.
最小链覆盖等于点数减去拆点二分图的最大匹配

证明

二分图每匹配一对点，就相当于合并了两条链。

Q.E.D.

Part 2 无向图

2.1 定义

点的邻点：无向图中， $v$ 为点 $u$ 的邻点当且仅当它们有边直接相连， $N(u)$ 为 $u$ 的邻点集；
团：无向图中满足点两两之间都有连边的点集；
独立集：无向图中满足点两两之间没有连边的点集；
直径：无向图中所有点对的最短路的最大值；
点覆盖：无向图中所有边两端的点都至少有一个在其中的点集；

2.2 定理

最大团等于补图的最大独立集

证明

原图的一个团内的点显然在补图上两两没有连边，所以原图的最大团在补图上一定是独立集。

反过来即可证明补图的最大独立集在原图上一定是团。

Q.E.D.
无向图中 $1$ 到其它点最短路的最大值 $dis$ 和图的直径 $d$ 满足 $\lceil\frac{d}{2}\rceil\le dis \le d$

证明

$dis\le d$ 显然， $\lceil\frac{d}{2}\rceil\le dis$ 则是因为要先走到直径上，再走到直径的两个端点。

Q.E.D.

2.3 二分图

2.3.1 定义

二分图：无向图，满足可以分成左部点集 $S$ 和右部点集 $T$ 使得对于所有边 $(u,v)$ 都有 $u\in S,v\in T$ 或 $u\in T,v\in S$ ；
拆点二分图：把每个点拆成入点和出点，对于一条边 $x\to y$ ，在二分图中连一条从 $x$ 的出点到 $y$ 的入点的边；
$k-$ 正则二分图：所有点的度数都为 $k$ 的二分图，易知 $k-$ 正则二分图中 $|S|=|T|$ ；
匹配：二分图中满足每个点度数都是 $1$ 的子图；
完美匹配：某一部中的点都在其中的匹配；

2.3.2 定理

二分图最小点覆盖等于最大匹配：

证明

网络流，源点向每个左部点连流量为 $1$ 的边，左部点向原图中有连边的右部点连流量为 $\infin$ 的边，右部点向汇点连流量为 $1$ 的边，最小割等于最大流。

Q.E.D.
二分图最大独立集等于点数减去最小点覆盖：

证明

每条边都至少有一个端点在最小点覆盖中，那么把最小点覆盖中的点删掉后就是最大独立集了。

Q.E.D.
$k-$ 正则二分图可以被拆解为 $k$ 组完美匹配
证明
归纳：
- $1-$ 正则二分图显然满足；
- $k-$ 正则二分图满足 Hall 定理： $\forall A\subseteq S$ ， $A$ 连出去的边集 $EA$ 是 $N(A)$ 连出去的边集 $EB$ 的子集，所以 $|EA|\le |EB|$ ，那么显然 $k|A|\le k|N(A)|$ ， $|A|\le |N(A)|$ ；
- 由于 $k-$ 二分图满足 $|S|=|T|$ ，所以找到 $k-$ 二分图的一组完美后去掉它可以转化为 $(k-1)-$ 正则二分图；
Q.E.D.

2.3.3 Hall 定理

2.3.3.1 基本形式

对于左部点集为 $S$ ，右部点集为 $T$ 的二分图 $G$ ，其存在大小为 $|S|$ 的匹配的充要条件为：

$\forall A\subseteq S,|\cup_{u\in A}N(u)|\ge|A|$

证明

必要性显然，充分性考虑反证。

若满足了基本 Hall 定理但是不存在大小为 $|S|$ 的匹配，则一定存在一个 $u\in S$ 满足 $u$ 不在最大匹配中，那么 $\forall v\in N(u)$ ， $v$ 一定在最大匹配中。

考虑匈牙利算法，对于每一个 $v$ ，都不断找到它匹配的点 $b_v$ ，把 $b_v$ 当作 $u$ 继续进行这个过程。设遍历过的 $u$ 的集合为 $B$ （包含刚开始的那个 $u$ ），则若 $\forall u\in B$ ， $N(u)$ 中都不存在未被匹配的点，那么一定有 $|N(B)|=|B|-1$ ，即只有刚开始的那个 $u$ 找不到和它匹配的点。与定理相悖。

Q.E.D.

2.3.3.2 拓展形式

对于左部点集为 $S$ ，右部点集为 $T$ 的二分图 $G$ ，其最大匹配为：

$|S|-\max\left(\max\limits_{A\subseteq S}\{|A|-|\cup_{u\in A}N(u)|\},0\right)$

证明是简单的。

对于类似这样的二分网络流图，即源点向左边第 $i$ 个点连一条流量 $a_i$ 的边，左边第 $i$ 个点向右边第 $j$ 个点连一条流量 $c_{i,j}$ 的边，右边第 $i$ 个点向汇点连一条流量 $b_{i}$ 的边：

它左边的所有点能满流（经过左边第 $i$ 个点的流量为 $a_i$ ）当且仅当以下条件成立：

设左边点集合为 $S$ ，则 $\forall T\subseteq S,\sum\limits_{u\in T}a_u\le\sum\limits_{u\in N(T)}\min\left(b_u,\sum\limits_{v\in T} c_{v,u}\right)$ ；

即与 $T$ 相连的右边点集能承受的总流量要至少为 $T$ 中点输出的总流量。

证明

把基本形式证明中的匈牙利换成 EK（每次暴力找一条增广路）即可。

2.3.3.3 点和区间匹配形

数轴上有 $n$ 个点和 $n$ 个区间，一个点能匹配一个区间当且仅当这个点被这个区间包含。

存在大小为 $n$ 的匹配当且仅当：

把值域离散化到 $[1,n]$ 后，对于所有区间 $[l,r]$ ，被 $[l,r]$ 完全包含的区间个数 $\le r-l+1$ ；

证明

考虑反证。

对于区间集合 $S$ ，若 $|S|>|\cup_{u\in S} [l_u,r_u]|$ 且 $\cup_{u\in S} [l_u,r_u]$ 可以分成若干个极长的不交且不相邻区间 $[lb_1,rb_1],[lb_2,rb_2],\dots,[lb_k,rb_k]$ ，则设 $A_i=\{x|x\in S,[l_x,r_x]\subseteq [lb_i,rb_i]\}$ 。

注意到对于任意不同的 $i,j$ ，必然有 $A_i\cap A_j=\emptyset$ ，也就是说，对于任意不同的 $i,j$ ， $A_i\cap A_j=\emptyset$ 且 $(\cup_{u\in A_i} [l_u,r_u])\cap(\cup_{u\in A_j} [l_u,r_u])=\emptyset$ 。

所以对于任意不同的 $i,j$ ， $A_i$ 和 $A_j$ 独立。

那么必然存在某个 $i$ 满足 $|A_i|>|\cup_{u\in A_i} [l_u,r_u]|$ ，此时区间 $\cup_{u\in A_i} [l_u,r_u]$ 不合法。

Q.E.D.

2.3.3.4 例题

2.4 生成树

2.4.1 定义

生成树：无向图 $G$ 的一个边集，满足所有点都可以通过该边集联通且该边集的边数最小；
最小生成树：边权和最小的生成树；
dfs 树：所有非树边两端的节点都互为祖孙关系的生成树；
本源环：dfs 树中只有一条非树边的环；

2.4.2 定理

所有最小生成树中每种边权的边的条数对应相等：

证明

考虑 Kruskal 算法的过程，显然边权小的边会选尽量多条。

Q.E.D.

例题：
- P4208 [JSOI2008] 最小生成树计数
所有简单环都可以由任意生成树中的若干本源环异或得出：

证明

每个简单环都等价于环中非树边对应的本源环异或起来。

Q.E.D.

例题：
- P4151 [WC2011] 最大XOR和路径
- CF19E Fairy | 题解

Part3 有向图

3.1 定义

强连通子图：有向图的满足所有点对都能互相到达的子图；
SCC：有向图的极大强连通子图（即加入任意节点都不强连通的强连通子图）；

3.2 偏序图

3.2.1 定义

偏序图：有向图，满足若存在边 $x\to y$ 和边 $y\to z$ 则存在边 $x\to z$ ；

3.2.2 定理

偏序图上的独立集和反链等价

证明

考虑反证，设独立集中有两个点 $x,y$ 满足 $x$ 能到达 $y$ ，由于偏序图满足 $x$ 能到达 $y$ 则存在边 $x\to y$ ，所以 $x,y$ 不能同时存在于独立集中。

Q.E.D.

3.3 竞赛图

3.3.1 定义

竞赛图：有向图，满足可以由点数相同的完全图定向得到；

3.3.2 定理

竞赛图缩点（把每个 SCC 都缩成一个大点）后，满足拓扑序唯一且每个大点向它拓扑序中后面的所有大点都有连边
把竞赛图中的点按出度从小到大排序后，每个 SCC 对应一个区间

证明

竞赛图缩点后，满足拓扑序唯一且每个大点向它拓扑序中后面的所有大点都有连边。

也就是说对于每个 SCC，设拓扑序在它后面的 SCC 共有 $m$ 个点，则这个 SCC 中的每个点都会向这 $m$ 个点连一条边。

而一个大小为 $k$ 的 SCC 中的点向这个 SCC 内部的其它点最多连 $k-1$ 条边。

所以把所有点按出度从小到大排序相当于把 SCC 按照拓扑序从后往前排序，每个 SCC 对应一个区间。

Q.E.D.
竞赛图中的 SCC 个数即为其中的点按出度 $d_u$ 从小到大排序后满足 $\sum\limits_{j=1}^id_j=\binom{i}{2}$ 的 $i$ 的个数

证明

根据上一条定理的证明，把所有点按出度从小到大排序后相当于把 SCC 按照拓扑序从后往前排序，每个 SCC 对应一个区间。

那么 $\sum\limits_{j=1}^id_j=\binom{i}{2}$ 的区间 $[1,i]$ 与拓扑序的后缀构成双射。

Q.E.D.

题外话：不难发现 Sum of SCC 那题的结论和这个本质相同。

例题：

Part 1 公共部分

1.1 定义

1.2 定理

Part 2 无向图

2.1 定义

2.2 定理

2.3 二分图

2.3.1 定义

2.3.2 定理

2.3.3 Hall 定理

2.3.3.1 基本形式

2.3.3.2 拓展形式

2.3.3.3 点和区间匹配形

2.3.3.4 例题

2.4 生成树

2.4.1 定义

2.4.2 定理

Part3 有向图

3.1 定义

3.2 偏序图

3.2.1 定义

3.2.2 定理

3.3 竞赛图

3.3.1 定义

3.3.2 定理

感谢您的支持，我会继续努力的!