Part 1 公共部分
1.1 定义
- 补图:
- 无向图 的补图中存在一条边 当且仅当 中不存在边
- 有向图 的补图中存在一条边 当且仅当 中不存在边 ;
- 子图:图中某些点和它们之间的边构成的新图;
- 链覆盖:把图划分为若干条链的方案;
- 反链:满足 , 不能到达 且 不能到达 的点集 。
1.2 定理
-
最小链覆盖等于最长反链
证明
考虑不得不用两条链覆盖的结构,即一个分叉,显然不同分支上的点不能相互到达,那么最长反链中的每个点都可以代表一条链。
Q.E.D.
-
最长链等于最小反链覆盖
证明
对于一条链,链上的任意两点都不能被放到同一个反链中,所以最小反链覆盖不大于最长链。
而对于两条链同一个位置的点,显然要么是同一个点,要么可以放到同一个反链中,所以最小反链覆盖等于最长链。
Q.E.D.
-
最小链覆盖等于点数减去拆点二分图的最大匹配
证明
二分图每匹配一对点,就相当于合并了两条链。
Q.E.D.
Part 2 无向图
2.1 定义
- 点的邻点:无向图中, 为点 的邻点当且仅当它们有边直接相连, 为 的邻点集;
- 团:无向图中满足点两两之间都有连边的点集;
- 独立集:无向图中满足点两两之间没有连边的点集;
- 直径:无向图中所有点对的最短路的最大值;
- 点覆盖:无向图中所有边两端的点都至少有一个在其中的点集;
2.2 定理
-
最大团等于补图的最大独立集
证明
原图的一个团内的点显然在补图上两两没有连边,所以原图的最大团在补图上一定是独立集。
反过来即可证明补图的最大独立集在原图上一定是团。
Q.E.D.
-
无向图中 到其它点最短路的最大值 和图的直径 满足
证明
显然, 则是因为要先走到直径上,再走到直径的两个端点。
Q.E.D.
2.3 二分图
2.3.1 定义
- 二分图:无向图,满足可以分成左部点集 和右部点集 使得对于所有边 都有 或 ;
- 拆点二分图:把每个点拆成入点和出点,对于一条边 ,在二分图中连一条从 的出点到 的入点的边;
- 正则二分图:所有点的度数都为 的二分图,易知 正则二分图中 ;
- 匹配:二分图中满足每个点度数都是 的子图;
- 完美匹配:某一部中的点都在其中的匹配;
2.3.2 定理
-
二分图最小点覆盖等于最大匹配:
证明
网络流,源点向每个左部点连流量为 的边,左部点向原图中有连边的右部点连流量为 的边,右部点向汇点连流量为 的边,最小割等于最大流。
Q.E.D.
-
二分图最大独立集等于点数减去最小点覆盖:
证明
每条边都至少有一个端点在最小点覆盖中,那么把最小点覆盖中的点删掉后就是最大独立集了。
Q.E.D.
-
正则二分图可以被拆解为 组完美匹配
证明
归纳:
- 正则二分图显然满足;
- 正则二分图满足 Hall 定理:, 连出去的边集 是 连出去的边集 的子集,所以 ,那么显然 ,;
- 由于 二分图满足 ,所以找到 二分图的一组完美后去掉它可以转化为 正则二分图;
Q.E.D.
2.3.3 Hall 定理
2.3.3.1 基本形式
对于左部点集为 ,右部点集为 的二分图 ,其存在大小为 的匹配的充要条件为:
证明
必要性显然,充分性考虑反证。
若满足了基本 Hall 定理但是不存在大小为 的匹配,则一定存在一个 满足 不在最大匹配中,那么 , 一定在最大匹配中。
考虑匈牙利算法,对于每一个 ,都不断找到它匹配的点 ,把 当作 继续进行这个过程。设遍历过的 的集合为 (包含刚开始的那个 ),则若 , 中都不存在未被匹配的点,那么一定有 ,即只有刚开始的那个 找不到和它匹配的点。与定理相悖。
Q.E.D.
2.3.3.2 拓展形式
对于左部点集为 ,右部点集为 的二分图 ,其最大匹配为:
证明是简单的。
对于类似这样的二分网络流图,即源点向左边第 个点连一条流量 的边,左边第 个点向右边第 个点连一条流量 的边,右边第 个点向汇点连一条流量 的边:
它左边的所有点能满流(经过左边第 个点的流量为 )当且仅当以下条件成立:
- 设左边点集合为 ,则 ;
即与 相连的右边点集能承受的总流量要至少为 中点输出的总流量。
证明
把基本形式证明中的匈牙利换成 EK(每次暴力找一条增广路)即可。
2.3.3.3 点和区间匹配形
数轴上有 个点和 个区间,一个点能匹配一个区间当且仅当这个点被这个区间包含。
存在大小为 的匹配当且仅当:
- 把值域离散化到 后,对于所有区间 ,被 完全包含的区间个数 ;
证明
考虑反证。
对于区间集合 ,若 且 可以分成若干个极长的不交且不相邻区间 ,则设 。
注意到对于任意不同的 ,必然有 ,也就是说,对于任意不同的 , 且 。
所以对于任意不同的 , 和 独立。
那么必然存在某个 满足 ,此时区间 不合法。
Q.E.D.
2.3.3.4 例题
2.4 生成树
2.4.1 定义
- 生成树:无向图 的一个边集,满足所有点都可以通过该边集联通且该边集的边数最小;
- 最小生成树:边权和最小的生成树;
- dfs 树:所有非树边两端的节点都互为祖孙关系的生成树;
- 本源环:dfs 树中只有一条非树边的环;
2.4.2 定理
-
所有最小生成树中每种边权的边的条数对应相等:
证明
考虑 Kruskal 算法的过程,显然边权小的边会选尽量多条。
Q.E.D.
例题:
-
所有简单环都可以由任意生成树中的若干本源环异或得出:
证明
每个简单环都等价于环中非树边对应的本源环异或起来。
Q.E.D.
例题:
Part3 有向图
3.1 定义
- 强连通子图:有向图的满足所有点对都能互相到达的子图;
- SCC:有向图的极大强连通子图(即加入任意节点都不强连通的强连通子图);
3.2 偏序图
3.2.1 定义
- 偏序图:有向图,满足若存在边 和边 则存在边 ;
3.2.2 定理
-
偏序图上的独立集和反链等价
证明
考虑反证,设独立集中有两个点 满足 能到达 ,由于偏序图满足 能到达 则存在边 ,所以 不能同时存在于独立集中。
Q.E.D.
3.3 竞赛图
3.3.1 定义
- 竞赛图:有向图,满足可以由点数相同的完全图定向得到;
3.3.2 定理
-
竞赛图缩点(把每个 SCC 都缩成一个大点)后,满足拓扑序唯一且每个大点向它拓扑序中后面的所有大点都有连边
-
把竞赛图中的点按出度从小到大排序后,每个 SCC 对应一个区间
证明
竞赛图缩点后,满足拓扑序唯一且每个大点向它拓扑序中后面的所有大点都有连边。
也就是说对于每个 SCC,设拓扑序在它后面的 SCC 共有 个点,则这个 SCC 中的每个点都会向这 个点连一条边。
而一个大小为 的 SCC 中的点向这个 SCC 内部的其它点最多连 条边。
所以把所有点按出度从小到大排序相当于把 SCC 按照拓扑序从后往前排序,每个 SCC 对应一个区间。
Q.E.D.
-
竞赛图中的 SCC 个数即为其中的点按出度 从小到大排序后满足 的 的个数
证明
根据上一条定理的证明,把所有点按出度从小到大排序后相当于把 SCC 按照拓扑序从后往前排序,每个 SCC 对应一个区间。
那么 的区间 与拓扑序的后缀构成双射。
Q.E.D.
题外话:不难发现 Sum of SCC 那题的结论和这个本质相同。
例题: