BEST 定理 / 有向图欧拉回路计数

无向图欧拉回路计数是 NPC 的。有向图欧拉回路计数则可使用 BEST 定理求解。

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

这是因为，不妨令 $k$ 为起点，同时钦定走的第一条边（否则一个回路会被计算多次），那么每个非根顶点的最后一条出边一定构成了一棵内向生成树，否则回到起点后图中还有完整的回路没有走到，除此之外，每条边的顺序可以任意确定。

$t^{root}(G,k)$ 可由矩阵树定理计算。

如果求给定起点 $s$ 的欧拉回路数量，$s$ 的每条出边都可以成为回路的第一条边，答案乘 $deg_s$。

如果求 $s\rightsquigarrow t$ 的欧拉路径数量，可连边 $t\to s$ 后求欧拉回路数量，然后钦定 $t\to s$ 为回路的最后一条边即可，答案乘 $t\to s$ 的边数。