平面图完美匹配计数-FKT算法

参考文献:http://basics.sjtu.edu.cn/~dominik/teaching/2016-cs214/presentation-slides/2016-12-27-PerfectMatchingsInPlanarGraphs-PlusOne.pdf


先介绍几个概念:

环覆盖:用若干个不相交的环,覆盖所有的点。

有向偶环覆盖(Even Directed Cycle Cover,简称EDCC):环覆盖中所有的环都是偶环,并且给所有的环定向。

定理:任意两个完美匹配的方案,都对应一个有向偶环覆盖的方案。于是有(|PM|^2=|EDCC|)(PM:prefect matching,即完美匹配)。

现在的问题是找(EDCC)的个数。


给每个点连出去一条边,并且要求每个点的度数为(1)。这样可以形成一个轮换,对应置换(排列)(pi)

(A)为某个矩阵,计算(pi)(det(A))的贡献。则贡献为(sgn(pi)val(pi)=sgn(pi)prod A_{i,pi(i)})

问题是构造出矩阵使得只有(pi)对应着一个(EDCC)的时候才有贡献。

考虑给原图定向,对于有向边((u,v)),钦定(A_{u,v}=1,A_{v,u}=-1),如果((u,v) otin E),则(A_{u,v}=0)

如此定义(A)之后:

  1. 如果存在((i,pi(i)) otin E),则贡献为(0)
  2. 如果(pi)对应的轮换中有个奇环(C),那么存在(pi'),对于任意(iin C),满足(pi(pi'(i))=i)(也就是说(pi')(pi)将轮换(C)反向),则有(sgn(pi)=sgn(pi'))(val(pi)=-val(pi'))。贡献将会互相抵消。

因此只有(EDCC)的贡献才会被计算到。


被计算到,我们希望贡献(sgn(pi)val(pi)=1),现在的目的是给图定向使得它满足这个条件。

接下来就是FKT算法:

  1. 给图(G)建一棵生成树(T),生成树内的边任意定向。
  2. 建另一个图(G2)(G2)中的每个点对应(G)中的一个面,((u,v)in E_{G2})当且仅当分割着(u)(v)的边不在(E_T)中。显然(G2)也是一棵树。
  3. (G2)的叶子结点开始操作,调整对应(G)的面的面上不在(T)中的边,使得面上的顺时针的边个数为奇数。

显然通过这样操作之后(G)内所有的面(不包括最外面的那个),面上顺时针的边的个数都为奇数。

可以证明:这样构图之后,所有的(EDCC)都满足:对于(EDCC)中的环,顺时针的边的个数都为奇数。

首先根据平面图欧拉定理,可以得知:(e=v+f-1),其中(v)为环内(不包括环上)的点数,(f)环内的面数,(e)为环内的边数(不包括环上)。

设环中顺时针边的个数为(c),环内面的顺时针边的个数为(c_i)。归纳:由(c_iequiv 1pmod 2)(fequiv sum c_ipmod 2),又由于(sum c_iequiv c+e)(内部每条边两边个连着一个面,它必定是其一的顺时针边),得(fequiv c+eequiv c+v+f-1pmod 2),所以(cequiv v-1pmod 2)。因为(2|v)(否则内部不能形成(EDCC)),所以(cequiv 1pmod 2)

于是,对于每个(EDCC),有(sgn(pi)val(pi)=((-1)(-1))^k=1)的贡献((k)为环数)(由于给行列式同时交换两行和交换两列行列式不变,给轮换重标号后,偶环能给(sgn(pi))贡献(-1))。


梳理一下,总的过程就是:

  1. 跑FKT算法,给边定向。
  2. 搞出矩阵(A),算行列式。

时间复杂度是(O(n^3))

原文地址:https://www.cnblogs.com/jz-597/p/13935537.html