P5807 Which Dreamed It /【模板】BEST 定理

· · 题解

欧拉图相关中唯一需要点证明的东西，我尝试从偏理解的角度出发但不失严谨。

题意

给你一个有向图，求从 1 出发的欧拉回路的方案数。

两种回路不同当且仅当边序列中某一位置两序列中的边不同。

解法

首先这得是个欧拉图才能有欧拉回路，判定结论是入度等于出度。

证明的话必要性显然，1 有出必有入，其他点有入必有出。

充分性的话用套圈证明，先随便走一个回路，可能导致有些边没走到，再走那些没走过的边走一个回路，当成一个圈套进当前回路直至套完所有边。

那么当前图是欧拉图了，我们考虑计数回路方案。

先考虑不好计数的地方在哪里：

比如这个图，第一次走到 3 的时候就只能走 3\to 4 而不能走 3\to 1。

显然问题在于不加限制的走的话可能走了一条当前图的割边导致图不连通，那么我们需避开这些边，但这使得计数十分困难，我们需要寻求一种平凡的方式来避开这些边。

考虑一条欧拉回路，发现对于除了 1 号点的节点的最后一条出边是特别的。

具体来说，将他们都拿出来一定不会形成环。

证明：

假设成了环：

图一直满足半欧拉图的度数性质，如果取出的边形成了环，由于 x_1\to x_2 已经是 x_1 的最后一条出边，那么不可能还有入边，故一定不会有 x_m\to x_1 这条边。

考虑除了 1 都有出边且不会形成环的图是什么？内向树啊！所有我们得到结论，一个欧拉图通过取出每个节点的最后一条出边得到一棵内向树。

实际上可以证明，将结论反过来是成立的，即一个欧拉图的每个点都以一个内向树上的边为最后一条出边时，其他怎么走都可以形成一个欧拉回路。

证明：

设内向树上 x 指向的节点为 fa_x。

对于一条边 x\to y，如果它不是割边，说明还有路径 y\to x。

对于一张对于当前的半欧拉图（或欧拉图）来说，走过过后的度数一定仍然满足半欧拉图的性质，同时连通性也可以保证，那么还是一张半欧拉图，直到走完所有边。

而除了在内向树上的边，其他边都不可能成为割边。

因为走了 x\to y 后起码还有 x\to fa_x\to fa_{fa_x}\to\dots\to 1 的路径，同时也有 y\to fa_y\to fa_{fa_y}\to\dots\to 1 的路径。

那么 x,y 还是连通的，故只有 x\to fa_x 时才可能导致 x,y 不连通，由于内向树上的边 x\to fa_x 为 x 的最后一条出边，所以 x 已经成为了一个孤立点，没有关系。

那么我们钦定一棵内向树，然后对于其他边任意定顺序，一定唯一对应了一个欧拉回路。

这样的计数得到的一组方案是唯一对应一条欧拉回路的，充分性有了，必要性呢？

显然也有，我们才证明了对于每条欧拉回路都能拿出最后一条出边得到一棵内向树，其他边依次定顺序即可对应计数唯一的一种方案。

所以计数的答案就是：ans=\sum_{T\text{是原图的一棵内向树}}\text{任意定顺序走出一条欧拉回路的方案数}

只剩下随意走的方案数了，对于每个点 x，第 i 次经过它时会带来 du'_ x-i+1 种不同的方案，即从 du'_ x-i+1 条出边中任选一条走都是不同的方案。

那么一个点 x 对方案的总贡献贡献就是 du' _ x!，所有点的贡献就是 \prod_xdu'_ x!。

注意 du' _ x 表示除掉内向树上的边以外的出度，设原图节点 x 的出度为 du_x，发现不管内向树长什么样 du' 总不变，均为 du' _ x=du_x-[x\neq1]

所以 ans=\sum_{T\text{是原图的一棵内向树}}\prod_xdu'_ x!=(\text{内向树个数})\times(\prod_{x=2}^n{(du_x-1)!}\times du_1!)。

内向树个数可以用矩阵树定理求，这道题除了判断一开始是否为欧拉图外没什么坑点，随便写写就完了。

BEST 定理

讲了这么多不顺便把 \text{BEST} 定理讲了可惜了，这个定理求的是一个有向图的欧拉回路的数量。

和这道题有什么区别？没有从 1 出发的区别，即一个回路的边序列是循环同构的。

考虑以 1 为起点求出的回路被重复计数了多少次，我们取出一个欧拉回路的点序列（由于是回路最后回到 1 时 1 不加入点序列），发现如果有 k 个 1 我们将每个 1 旋到第一个位置得到的序列都对应了一个以 1 为起点出发形成的欧拉回路。

于是每条欧拉回路多算了 k 次，而一个点 x 会被经过 du_x 次，那么 k 显然就是 du_1，除以一个 du_1 即可。

那么有 sum=ans/du_1=(\text{内向树个数})\times(\prod_{x=2}^n({du_x-1})!\times du_1!)/du_1=(\text{内向树个数})\times(\prod_{x=1}^n({du_x-1})!)。

故 BEST 定理的表述就是：

一个有向图的欧拉回路的数量为

sum=(\text{内向树个数})\times(\prod_{x=1}^n({du_x-1})!)

挺好看的是吧。