二分图

定义：可以分为两个部分的图（称为左部和右部），同一个部分内没有边。

由此得到：

• 二分图是可以被二染色的图。
• 若二分图 \(G=(V,E)\) 包含 \(C\) 个连通分量，则其二染色的方案为 \(2^C\) 。

二分图的判定

定理：一张无向图是二分图，当且仅当图中无奇环 。

推论：

• 二分图的任意子图为二分图。

• 一张无向图是二分图当且仅当其每个连通分量都是二分图。

• 二分图中任意两点间路径经过的边数奇偶性确定。

使用黑白交替染色法，时间复杂度 \(O(n + m)\) 。

应用

染色法

P2774 方格取数问题

考虑对棋盘黑白染色，将所有黑点白点建立一张二分图。

先假设所有点都取，那么这张二分图的最小割就是要删去的点，剩下的点必然就是权值和最大且互不相邻的点。

二分图最大匹配

定义

• 匹配：一个满足任意两边无公共点的边集。
• 完美匹配 : 若两侧点集为 \(X, Y\) , 匹配数达到 \(\min(|X|, |Y|)\) 称之为完美匹配。
• 完备匹配（完全匹配）：\(|X| = |Y|\) 时的完美匹配。
• 增广路：一条连接两个非匹配点、满足非匹配边与匹配边交替出现的路径，有如下性质：
  • 长度为奇数。
  • 奇数边是非匹配边，偶数边是匹配边。
  • 如果把路径上所有边的状态（是否为匹配边）取反，那么得到的新的边集 \(S'\) 仍然是一组匹配，并且匹配的边数增加了 \(1\) 。

结论：\(P\) 是二分图的最大匹配，当且仅当图中不存在增广路。

匈牙利算法

• 初始时设 \(S\) 为空集，即所有边都是非匹配边。
• 枚举左部的一个点 \(u\) ，与其连接的右部点 \(v\) 尝试匹配，当 \(v\)​ 点未匹配过或 \(v\)​​ 点已经和另外一个点匹配但这个点还可以找到与其匹配的点时，匹配成功。
• 重复第二步，直到图中不存在增广路。

时间复杂度 \(O(nm)\) 。

bool Hungary(int u, const int tag) {
    for (int v : G.e[u]) {
        if (vis[v] == tag)
            continue;
        
        vis[v] = tag;

        if (!obj[v] || Hungary(obj[v], tag))
            return obj[v] = u, true;
    }

    return false;
}

void solve() {
    int ans = 0;

    for (int i = 1; i <= n; ++i)
        if (Hungary(i, i))
            ++ans;

    return ans;
}

匈牙利算法基于贪心原则：一旦一个点进入匹配，就不会重新成为非匹配点，因此当找不到增广路时表示 \(i\) 在保持 \(1,\ldots,i-1\) 的匹配情况不变时一定无法加入最大匹配中。

由此，我们可以知道：若将匹配的左部点记为 \(1\) ，未匹配的左部点记为 \(0\) ，则按照枚举顺序拼接左部点的匹配情况，匈牙利算法求出的最大匹配是字典序最大的。

必须边和可行边

模仿网络流求解二分图时那样进行如下建图：

• 建立源点 \(s\) 和汇点 \(t\)，从 \(s\) 向左部非匹配点连边，左部匹配点向 \(s\) 连边；从 \(t\) 向右部匹配点连边，右部非匹配点向 \(t\) 连边；
• 对于原二分图中的边，如果属于当前最大匹配，就从右部点连向左部点，否则就从左部点连向右部点。

考虑新图，一条不经过 \(s,t\) 的路径必然是交替出现匹配边和非匹配边的，而一个不经过 \(s,t\) 的环就是增广环。

再考虑经过 \(s,t\) 的环，例如经过 \(s\) 的一个环，其实就对应了环上与 \(s\) 相邻的一对匹配点和非匹配点之间的半增广路。

所以在新的有向图 \(G'\) 中，一个简单环就对应了原来的一个增广环或半增广路，也就是说包含一条边的增广环或半增广路存在等价于这条边的两端在同一 SCC 中。

整理得到：边 \((u,v)\) 是二分图最大匹配的可行边，当且仅当它属于当前匹配或 \(u,v\) 属于 \(G'\) 中同一 SCC，而边 \((u,v)\) 是二分图最大匹配的必经边，当且仅当它属于当前匹配且 \(u,v\) 不属于 \(G'\) 中同一 SCC。

值得一提的是，上面的 \(G'\) 其实就是网络流建图求二分图匹配后的残量网络。

可行点和必须点

任何度数不为 \(0\) 的点都是可行点，考虑随便选择一条出边，就能找到长度至少为 \(2\) 的半增广路。

从每个未匹配点 \(x\) 开始遍历，将经过的同侧点打上标记，最后检验是否有匹配点被打上标记，有则图中至少有一个非必须点。

网络流算法

建立超级源点 \(S\) 和超级汇点 \(T\) ，左侧向源点连边，右侧向汇点连边，左右之间连边，流量均为 \(1\) 。

输出方案：遍历左部点，找出残余流量为 \(0\) 的边，输出对应点即可。

使用 Dinic 算法，复杂度上界 \(O(m \sqrt{n})\) ，一般快于朴素匈牙利算法。

多重匹配

对于一张二分图 \(((A, B), E)\) ，从 \(E\) 中选出尽量多的边是 \(x \in A\) 最多与 \(l_x\) 条选出的边相连， \(y \in B\) 最多与 \(r_y\) 条选出的边相连，则称选出的边为二分图的多重匹配

实现：将每个 \(x \in A\) 拆成 \(l_x\) 个点，每个 \(y \in B\) 拆成 \(r_y\) 个点，跑二分图最大匹配（也可以使用网络流解决）。

二分图最小点覆盖

点覆盖：一个点集 \(V\) 满足对于每条边均有至少一个端点在 \(V\) 中。

定理

\(\mathrm{K\ddot{o}nig}\) 定理：最小点覆盖数 = 最大匹配数

构造

考虑如下构造：从左部未匹配点出发求增广路，并给经过的节点上打标记，所有左侧未打标记的节点和所有右侧打了标记的节点构成的点集即为所构造的集合。

首先，这个集合的大小等于最大匹配。

对于每条匹配边，两个端点被标记状态相同，因此必定恰有一个点被选。而对于一条非匹配边，假设左侧点不是匹配点，那么必然被标记，假设右侧点不是匹配点，那么必然不被标记（否则找到了一条增广路），因此只有所有匹配边的恰好一边在这组点覆盖中。

其次，这个集合是一个点覆盖。

如果存在一条边两端都没有选，说明其左侧是标记点，右侧是非标记点，且其必为非匹配边。但是在左侧点被标记后，右侧的点随后就会被经过，所以这是不可能的。

同时，不存在更小的点覆盖。为了覆盖最大匹配的所有边，至少要有最大匹配边数的点数。

若用网络流算法，从每个点开始 DFS，只走残余流量 \(\not = 0\) 的边，然后沿途标记输出当前节点即可。

实际上，我们还容易证明任何一组点覆盖大小不小于任何一组匹配大小，根据上面的构造，也可以得到定理。

二分图最大独立集

独立集：一个点集 \(V\) 满足对于每条边均有至少一个端点不在 \(V\) 中。

定理

最大独立集大小与最小点覆盖大小之和等于点数（独立集与点覆盖互补）。

应用

互不攻击问题

P3355 骑士共存问题 P5030 长脖子鹿放置

我们把每个点与其可以攻击到的点连边，那么这张图一定是一张二分图，求最大独立集即可。

Hall 定理

定理：不妨设 \(|X| \leq |Y|\) ，二分图存在完美匹配等价于对于 \(S \subseteq X\) ，称 \(X\) 中点集 \(S\) 连向 \(Y\) 的点集为邻域 \(N(S)\) ，则 \(|N(S)| \geq |S|\) 。

必要性：对于某 \(k\) 个点，它们连向对面不足 \(k\) 个点，显然无法全部匹配。

充分性：先构造一种最大匹配，此时有未匹配的点存在。

该未匹配点必然有出边，否则违反右侧。如果出边到达的点也不在匹配中，则可以多匹配一条边，矛盾。

若对面的点存在于匹配中，我们找出与其匹配的点，此时我们拥有两个 \(X\) 中的点。

根据右侧，\(N(S)\) 中会多出一个点和我们已有的点连边。如果这个点未被匹配,则可以匹配。

若已经被匹配，就会在 \(X\) 中引入新的点。如此可以不断增大集合，然而 \(X\) 是有限的，必然导出矛盾。

推论：二分图最大匹配为 \(|X| - \max(|S| - |N(S)|) = \min(|X| - |S| + |N(S)|)\) 。

如果建立二分图匹配的网络流模型，把 \(|X| - |S|\) 看做左侧割掉的点，\(|N(S)|\) 即为右侧割掉的点，取个 \(\min\) 就是最小割。根据最小割定理得证。

扩展：考虑多重匹配（带容量匹配）的情况，某个点能匹配的次数是 \(W_u\) ，这可以视作将 \(u\) 复制 \(W_u\) 次的经典二分图。我们选择 \(u\) 复制出的所有点 \(S\) ，要满足 \(|N(S)| \geq |S|\) 。不难发现，由于边是相同的，\(S\) 中的任意一个元素 \(x\) 都满足 \(N(x) = N(S)\) 。这样，若 \(S\) 满足条件，则 \(S\) 的任意子集都满足条件，我们可以把同一个点的复制点集当做整体看待。不妨称作 \(T_u\) 。选择原图中左侧的点集 \(S\) ，设原图中其邻域为 \(N(S)\) ，设 \(W(S) = \sum_{u \in S} W_u\) 。那么在新图中，\(S\) 的复制点集大小为 \(W(S)\) ，而 \(N(S)\) 的复制点集大小为 \(W(N(S))\) 。这就引出多重匹配有完美匹配的充要条件：\(\forall S, W(S) \geq W(N(S))\) 。

二分图最小边覆盖

边覆盖：一个覆盖了所有点的边集。

定理

如果存在孤立点，则无边覆盖，否则二分图最小边覆盖等于最大独立集。

最大独立集中任何两个点一定不能由一条边覆盖，因此最小边覆盖不小于最大独立集。

构造：选出所有匹配边，再对于所有未匹配点单独选一条和它相连的边，就得到了一组等于最大独立集的边覆盖，因此结论得证。

最大团

对于一张无向图 \((V,E)\)​ ，若存在一个点集 \(V'\)​，满足 \(V' \subseteq V\)​ ，且对于任意 \(u,v \in V'\)​，\((u,v) \in E\)​，则称 \(V'\)​​ 为这张无向图的一组团。

定理

无向图最大团等于补图最大独立集。

应用

P2423 [HEOI2012]朋友圈

观察补图可以发现， \(A\) 国中所有权值为奇数的点和所有权值为偶数的点各构成两个完全图， \(B\)​ 国中所有权值为奇数的点和所有权值为偶数的点构成一个二分图。

因为无向图最大团 = 补图最大独立集，所以最大朋友圈中 \(A\)​​ 国最多取两个人（点）。

首先求出 \(B\) 的补图的最大独立集，这是 \(A\) 中选 \(0\) 个的答案。

之后，枚举 \(A\) 中选了哪个，找到它的 \(B\) 朋友，找到 \(B\) 中这些朋友构成的子图，给它的补图跑最大独立集。

最后，枚举 \(A\) 中选了哪两个，找到它们共同的 \(B\) 朋友，找到 \(B\) 中这些朋友构成的子图，给它的补图跑最大独立集。

时间复杂度为 \(O(A^2B^2)\)。

路径覆盖与链覆盖

DAG 最小路径点覆盖

给定一张 DAG，用尽量少的不相交的简单路径覆盖所有点，这样的路径集称为最小路径点覆盖。

P2764 最小路径覆盖问题

将原图中所有点 \(x\) 拆分成 \(x\) 与 \(x+n\) 两个点。对原图中每条边 \(u \to v\) ，在新图中连 \(u \to v+n\) 的边，所构建的新二分图称为即为原图的拆点二分图。

则可以得到：最小路径点覆盖 = 总点数 - 拆点二分图的最大匹配

证明：一开始每个点都是独立的为一条路径，总共有 \(n\) 条不相交路径。每次在二分图里找一条匹配边，就相当于把两条路径拼起来，路径数减少了 \(1\) 。所以找到了几条匹配边，路径数就减少了多少。

偏序集的最小链覆盖

亦称：DAG 最小可重复路径点覆盖。

• 偏序集：元素之间存在大小关系，允许不可比（无定义）的情况出现。但是比较一定有传递性，且不能互相矛盾。换言之，比较关系构成一张 DAG 。
• 链：一个子图，任意两个点都可比较/有连边（偏序集的链可以跳过一些中间点）。

对 DAG 传递闭包，新图中的连续路径就对应着原图的一条链，求出新图的最小路径覆盖即可。

DAG 最长反链

反链：一个点集，其中任意两点相互不可到达。

Dilworth 定理：最长反链大小 = 总点数 - 最小链覆盖。

构造方案：拆出的出入点均在最大独立集内，则选中这个点到最长反链中。

若需要判定某个点能否存在于最长反链内，直接钦定这个点在，删除与其冲突的点，再跑一次算法判断能否取到最长即可。

模板：P4298 [CTSC2008] 祭祀