BEST定理

有向图欧拉回路数量计数。

为什么不是 $\prod_u (\deg_u!)$ 呢？因为任意的边排列顺序不一定能构造出对应的方案，比如

每个点的排列是：

1：红

2：橙

3：黄 粉

4：绿 蓝

5：紫

从 1 号点出发，发现构造不出合法的方案！

那么什么样的方案合法呢……只要每个点最后走的那条边不形成环就行了吧？

BEST 定理：有向图的欧拉回路数量等于 $t^{root}(G,k) \prod_{v\in V} (\deg_u -1)!$，其中 $t^{root}(G,k)$ 表示以 $k$ 为根的内向生成树的个数。

证明我参考了这个博客。