生成树计数和欧拉回路计数

矩阵树定理

给定一个 \(n\) 个点的简单有向图，边有边权，设 \(w(i,j)\) 为边 \(i\to j\) 的边权，\(deg_i\) 表示节点 \(i\) 的出边权值之和。定义一个矩阵如下：

\[ L= \begin{bmatrix} deg_1&-w(1,2)&-w(1,3)&\cdots&-w(1,n)\\ -w(2,1)&deg_2&-w(2,3)&\cdots&-w(2,n)\\ -w(3,1)&-w(3,2)&deg_3&\cdots&-w(3,n)\\ &\vdots&&\ddots&\vdots\\ -w(n,1)&-w(n,2)&-w(n,3)&\cdots&deg_n\\ \end{bmatrix} \]

矩阵树定理 对于任意 \(rt\in [1,n]\)，将 \(L\) 删去第 \(rt\) 行和 \(rt\) 列，得到一个 \((n-1)\times(n-1)\) 的子矩阵 \(L'\)；那么有 \(det(L')\) 等于以 \(rt\) 为根的内向生成树边权积的和。

证明

注意到我们可以为除了 \(rt\) 之外的每个节点分配一条出边，这样会形成一片内向基环树森林，和一棵以 \(rt\) 为根的内向树。考虑去除掉有环的情况。

考虑行列式中枚举置换环的组合意义。枚举的排列 \(p\) 中可能包含一些孤立点和一些置换环，置换环有系数 \(\prod w\) 和容斥系数 \((-1)^{cnt}\) 于是根据容斥原理最终统计到的显然就是不包含环的方案数。

对于无向图，定义 \(w(i,j)\) 为 \(i,j\) 之间的边权，\(deg_i\) 表示节点 \(i\) 的邻边权值之和，这样得到无向图的 \(L\) 矩阵。

推论 任意删去无向图 \(L\) 矩阵的一行一列，所得矩阵 \(L'\) 的行列式相等，为无向图生成树边权积的和。

证明

将每条无向边拆成两条有向边，发现此时以任意点为根的内向树都唯一对应一棵原图中的无向生成树。

为了刻画边权和，我们可以将边权用多项式 \(wx+1\) 代替，这样生成树的权值积的 \([x^1]\) 系数就是边权和。

欧拉回路计数

无向图的欧拉回路计数问题是 non-poly 的，此处我们研究有向图。

BEST 定理 给定一个有向图，其本质不同欧拉回路（不区分起点）的数量为

\[ tr(G)\prod_{i=1}^{n}(deg_i-1)! \]

其中 \(tr(G)\) 表示以任意一点为根的内向生成树数量。我们将证明 BEST 定理，以及选任意节点为根的内向树数量相等。

证明

任选 \(rt\in [1,n]\) 为欧拉路径的起点和终点。对每个点的所有出边选定一个顺序。我们首先证明，按照该顺序访问每一条出边可以得到欧拉回路 的充要条件是，每个节点（除了 \(rt\)）最后一条出边形成一棵以 \(rt\) 为根的内向树。

先证充分性，即证：若并非欧拉回路，即走到一半剩下的边构成一个和 \(rt\) 不连通的欧拉图，那么最后一条出边形成环（逆否命题）。考虑反证法，若为树，则剩下的某个连通块会存在一条树边连向某个孤立点，于是这个孤立点不是孤立点，矛盾。

再证必要性，即证：如果存在环，则并非欧拉回路（逆否命题）。考虑反证法，假设存在环并且路径为欧拉路径。考虑环上最先被访问的一条边 \((x,y)\)，于是此时 \(x\) 已成为孤立点。稍后将会访问到 \(y\) 的最后一条边，然后是下一个点，于是沿着环将会走回到 \(x\)，与 \(x\) 是孤立点矛盾。

于是，我们只需要构造一棵以 \(rt\) 为根的内向树，然后其它边随便排列即可，这样方案数显然是

\[ tr(G,rt)deg_{rt}\prod_{i=1}^{n}(deg_i-1)! \]

注意到一条欧拉回路会恰好经过 \(rt\) \(deg_{rt}\) 次，选其中某一次作为起点的欧拉回路都是本质相同的，也就是说方案数其实是

\[ tr(G,rt)\prod_{i=1}^{n}(deg_i-1)! \]

并且显然和 \(rt\) 无关。