8.12
匹配
概念
1
设一般无向图 𝐺 = (𝑉 , 𝐸)。匹配 𝑀 ⊆ 𝐸 中任意两条边没有公共端点。
交错路：匹配边和非匹配边交错
增广路（匹配图）：两端不匹配的交错路
增广路（Dinic）：在“当前残量网络”中，从源点 S 到汇点 T 的一条路径，并且路径上的每一条边都必须严格满足“剩余容量 > 0” 且 “层级（Level）逐层 +1
两个定义本质相同，匹配里的增广路，是“去掉 S 和 T 后，将容量全设为 1 的残量网络增广路”。
沿增广路把“匹配/非匹配”取反，内部点仍恰好关联一条匹配边，两端由未匹配变为已匹配，因此 |𝑀| 增加 1。
2
一条关于 M 的增广路 P，必须同时满足以下 3 个条件：
条件1：这条路的起点和终点，在当前的匹配 M 中，都必须是尚未匹配的顶点
条件2：这条路上的边，必须是“未匹配边 -> 匹配边 -> 未匹配边 -> 匹配边……”这样交替出现的。
条件3：因为路径两端的边都是“未匹配边”，所以这条路上未匹配边的数量，永远比匹配边多 1 条，整条路径的边数一定是奇数。
引理
匹配的对称差：两个匹配的对称差等于他们的边集的异或
-
其每个连通分量都是 𝑀, 𝑀′ 边交替的路或偶环。
-
环与首尾分属 𝑀, 𝑀′ 的交错路中，两类边数相同；
-
首尾均为 𝑀′ 边时 𝑀′ 边多一条，首尾均为 𝑀 边时反之。
Berge 引理：匹配 𝑀 最大，当且仅当不存在关于 𝑀 的增广路。
定理
柯尼希定理：二分图的最大匹配大小等于最小点覆盖大小。
算法
匈牙利(kuhn)算法
求解二分图最大匹配问题
暴力找增广路，翻转
优势在于写法简单 \(O(EV)\)
HK(Hopcroft-Karp)算法
分层图加速匈牙利
比Dinic常数小一点，都是 \(O(E\sqrt V\))，但是其写法和Dinic惊人相似，本质是一个算法
KM算法（❌️）
求解二分图最大权匹配，不建议用网络流替代，会很慢
KM 算法：复杂度是 O(n³)。
替代品（最小费用最大流）：在稠密图（带权匹配通常是完全二分图）中，复杂度约为 O(n³ log n) 甚至 O(n⁴)（取决于具体实现，如 SSP 增广路算法）。
偏序集最长反链（两两不可比较）
有限集合 𝑃 上的关系 ≼ 若满足自反、反对称、传递，则称 (𝑃, ≼)
为偏序集；记 𝑢 ≺ 𝑣 表示 𝑢 ≼ 𝑣 且 𝑢 ≠ 𝑣。
链中的元素两两可比较，反链中的元素两两不可比较。链划分要求
每个元素恰属于一条链。
Dilworth定理：有限偏序集的最长反链大小等于最小链划分大小。
Hall定理
Hall定理：二分图 𝐺 = (𝑋, 𝑌 , 𝐸) 存在 𝑋 的完美匹配，当且仅当任意 𝑆 ⊆ 𝑋 都满足|𝑁(𝑆)| ≥ |𝑆|.
缺陷Hall定理：义缺陷 def(𝑆) = |𝑆| − |𝑁(𝑆)|.最大匹配覆盖的左部点数满足 \(|𝑀∗| = |𝑋| − max_{𝑆⊆𝑋}def(𝑆).\)
P14598：如果左部点若干集合独立，可以分别求解再相加
带权hall定理：
网络流
杂七杂八
可行流即满足三大约束（容量限制，流量守恒，斜对称性）的流
流网络->流矩阵
残量网络->残量矩阵
网络与矩阵满足双射关系，故可以从矩阵角度分析网络流
增广路径定理（引理）
-
残量流叠加引理：原始网络中的一个合法流 \(f\)，加上其残留网络 \(G_f\) 中的任意一个合法流 \(g\)，叠加后仍然是原始网络 \(G\) 中的一个合法流。
-
残量路径增广引理：\(𝑝_𝑃\) 是流值为 \(𝛿\) 的可行残量流；因此 \(𝑓 + 𝑝_𝑃\) 是可行流，且 \(|𝑓 + 𝑝𝑃 | = |𝑓| + 𝛿\)。
以上引理引出了网络流算法
-
增广路判定定理：可行流 𝑓 是最大流，当且仅当其残量网络不存在 𝑠-𝑡 路径。
-
最大流最小割定理：最大流值等于最小割容量。
流分解
流分解定理：任意满足 \(|𝑓| ≥ 0\) 的可行流 \(𝑓\) 都能分解成若干条总流量为 \(|𝑓|\) 的 \(𝑠-𝑡\) 路径流与若干循环流。
循环流是指不与s和t链接的可行流，它满足三大限制，但是对于最大流算法无用，所以dinic给他忽略了，但是客观上是存在的
增广路径是合成，而流分解是拆分
平面图与最小割
- 平面割与对偶路径定理：原图最小 \(𝑠-𝑡\) 割的容量等于对偶图中 \(𝑠∗\) 到 \(𝑡∗\) 的最短路长度。
最小割树
非常好教程
最小割树定理：对于任意一个带非负权重的无向图 G，都存在一棵带权树 T（即Gomory-Hu树），使得树 T 上任意两点间路径上的最小边权，等于在原图 G 中这两点间的最小割值
最小割树收缩引理：若 \(cut(u,v)\) 将图分为 \(U\) 和 \(V\) 两部分，则任意 \(x \in U, y \in V\) 有 \(|cut(x,y)|<=|cut(u,v)|\)
Gomory–Hu 构造定理：在一张图上选取(u,v)跑网络流，最小割权值作为边权，将图割开，分治（表述不太规范）。
割等价性：对于树上的两点u,v，他们的最小割是他们之间简单路径的最小路径权值。
Dinic
阻塞流：当前分层图下的局部最大流
时间复杂度 \(O(V^2E)\)，这是一个很松的上界
当 \(V≥5000\) 且 \(E≥10000\) 时，心里要敲一下警钟，考虑一图是不是太密了；但如果 \(V≤1000\)，无论怎么建图，Dinic 都能轻松拿下。
Dinic二分图匹配复杂度为 \(O(E\sqrt V)\)
费用流
SSP+SPFA
\(O(n*m*f)\)
SSP+Dijkstra(Primal-Dual 原始对偶算法)
这是SPFA的优化版本，通过势能（Potential）函数将负权边转为非负，从而使用更快的Dijkstra算法
\(O(f * m * log n)\)
模拟费用流
模拟费用流AGC034D：即模拟费用流过程，优化边数
EX
点覆盖与独立集
互补性：一个点集是点覆盖，当且仅当它的补集是独立集。
极值对偶性：最小点覆盖的补集，一定是最大独立集。