平面图完美匹配计数

command_block · 2024-04-07 16:15:52 · 个人记录

有向偶环覆盖：用若干个点不相交的偶环覆盖所有点。

引理：一对完美匹配与有向偶环覆盖一一对应。

证明：（有向偶环覆盖 \to 一对完美匹配）考虑有向偶环覆盖，取出每个环，从编号最小的点开始，第一条边分给 E_1，第二条边分给 E_2，以此类推。最后 E_1,E_2 都是完美匹配。

（一对完美匹配 \to 有向偶环覆盖）对于完美匹配 E_1,E_2，将 E_1 中的边记为蓝色，将 E_2 中边记为红色。每个点拥有两条有色边，这形成若干个颜色相间的偶环。定向时，取出每个环内编号最小的点，从蓝边开始。

于是，我们只需算出有向偶环覆盖的方案数，再开根即可。

对于 n 个点的无向图 G，记其邻接矩阵为 A。注意到环覆盖 \leftrightarrow 置换 \leftrightarrow 排列，记 \mathcal P_n 为 n 元排列集合，则有向偶环覆盖方案数为

S=\sum_{p\in\mathcal P_n}[p\text{ 的每个环长均为偶数}]\prod_{i=1}^nA_{i,p_i}

然而“每个环长均为偶数”我们不会做。为了除去奇环，给图 G 定向，使其变成有向图。对于边 u\to v，令 A_{u,v}=1,\ A_{v,u}=-1。

此时考虑“带符号有向环覆盖”

S'=\sum_{p\in\mathcal P_n}(-1)^{{\rm inv}(p)}\prod_{i=1}^nA_{i,p_i}

可以发现，如果存在奇环，则该环会被正反各计算一次，而两次的 \prod_{i=1}^nA_{i,p_i} 符号恰好相反，因此抵消。

现在问题是，每个有向偶环覆盖的符号变得乱七八糟了。我们希望 A 的乘积恰好能和 (-1)^{{\rm inv}(p)} 抵消掉，即对于任何有向偶环覆盖 p，都有

\prod_{i=1}^nA_{i,p_i}=(-1)^{{\rm inv}(p)}

这样两者乘起来之后就是 1 了。

这样的定向方法被称作 Pfaffian 定向，接下来的问题是，如何构造 Pfaffian 定向？

1963 年，Kasteleyn 发现

欧拉定理：对于简单多面体，V+F-E=2。其中 V 是顶点数，F 是面数，E 是边数。

将平面图的外轮廓缩成一个点，可得 v+f-e=1。其中 v 内部顶点数，f 为内部面数，e 为内部边数。
引理：对于每个有向偶环覆盖，取出其中一个偶环，记偶环上顺时针边、逆时针边的个数均为奇数。

证明：对于每个有向偶环覆盖，取出其中一个偶环，记偶环上偶环上顺时针边的个数为 e_{\text{外顺}}。

考虑按顺时针方向把内部每个面绕一遍，计数顺着的边的总数。这会使得外轮廓上的边顺时针经过一次，不在外轮廓上的边正反经过各一次，贡献总是 1。

另一方面，每个面对奇偶性的贡献总是 1，这说明 f\equiv e_{\text{外顺}}+e_{\text{内}}\pmod 2。

根据欧拉定理 v_{\text{内}}+f-e_{\text{内}}=1（v 是偶数），可得 v_{\text{内}}+1\equiv e_{\text{外顺}}\pmod 2。

因为内部也是有向偶环覆盖，所以 v_{\text{内}} 是偶数，因此 1\equiv e_{\text{外顺}}\pmod 2。又因为是偶环，所以逆时针边也是奇数。

接下来可以证明定理中的 2。熟知逆序对奇偶性等于环个数的奇偶性，而每个有向偶环必然会在 A 中配上奇数个 -1（逆向边），故抵消。

接下来介绍构造方法：

先找出平面图 G 的任意一棵生成树 T，T 中的边随意定向。
建立对偶图 G'，每个面对应一个点，每条不在生成树中的边产生一条边。显然 G' 也是一棵树。
在 G' 上 dfs，在返回时（子树已经构造完毕），该面一定有一个父亲节点，取出与父亲面之间的分界边，根据目前奇偶性调节之。因为一定有一条这样的边，调节一定能成功。