原博客链接

老久没更了,冬令营也延期了(延期后岂不是志愿者得上学了?)

最近把之前欠了好久的债,诸如 FFT 和 Matrix-Tree 等的搞清楚了(啊我承认之前只会用,没有理解证明……),FFT 老多人写,而 MatrixTree 没人证我就写一下吧……

Matrix Tree 结论

Matrix Tree 的结论网上可多,大概一条主要的就是,图中生成树的数量等于 $V-E$ 的任一余子式,其中:

  • $V$ 为对角阵,第 $i$ 个元素为点 $i$ 的度数
  • $E$ 为对称阵,对角线为零且 $E_{i,j}$ 为点 $i$ 与点 $j$ 之间边的数量的相反数

这个结论众人皆知,但我好像没怎么搜到证明?

图的关联矩阵

为了求无向图中有多少组 $n-1$ 条边可以形成树,一般需要枚举所有的可能,无法在多项式内解决,但我们利用数学工具将其转换——引入关联矩阵

为了后面讨论我们给每条边随意分配一个方向。

图的邻接矩阵是一个 $n\times n$ 的用于存储图的矩阵。而关联矩阵 $A$ 则为 $n\times m$ 的矩阵,其中行对应点,列对应边,如果 $A_{i,j}$ 非零,则说明第 $j$ 条边的起点或终点为点 $i$(如 $i$ 为起点则为 $+1$,终点则为 $-1$,否则为 $0$)。如下图即为一张 $4$ 点 $5$ 边的图的关联矩阵:

$$
\begin{bmatrix}
+1&-1&+1&0&0\\
-1&0&0&+1&-1\\
0&+1&0&-1&0\\
0&0&-1&0&+1
\end{bmatrix}
$$

可以看到,如果只考虑这张图的结构的话,关联矩阵的行之间或列之间随意交换都是无所谓的(行交换代表点重新编号……)


我们可以证明一个结论,任意连通图的关联矩阵秩为 $n-1$。

有两种理解方式:

  • 按行来看:
    • 首先去掉任意一行都是可以复原的:因为每一列都是一个 $+1$ 一个 $-1$,可以轻松由其他 $n-1$ 行得到这一行。故去掉任意一行不会丢失信息,秩 $\le n-1$;
    • 其次去掉任意两行都是无法复原的:因为任意去掉两行 $x,y$,在这张连通图上找到一条 $x$ 到 $y$ 的路径,取其中 $x\to y$ 方向第一条边 $a$、$y\to x$ 方向第一条边 $b$,则在还原关联矩阵时无法确定非零位置是 $(x,a)\&(y,b)$ 还是 $(x,b)\&(y,a)$。故去掉任意两行都会丢失信息,秩 $\ge n-1$
  • 再按列来看更为显然:
    • 由于列对应边,故选取若干列,若这些列对应的边在图上组成了环,则一定线性相关(因为将环按一个方向捋一遍然后加起来一定为零)
    • 故要求 “最多的线性无关的列”,也即求 “在不出现环的前提下最多能找出多少边”,答案显然为 $n-1$

这下从行列两个方向证明了这个结论,但有何用处呢?

我们刚在从列的方向证明结论时用到了 “生成树” 的概念,仔细考虑一下,求 “图中有多少种 $n-1$ 条边的组合没有环”,等价于求 “关联矩阵中有多少种 $n-1$ 列的组合线性无关

同时我们证明了 $n$ 个行中总有一个是多余的,故考虑删去其中一行对答案无影响。

这下将图中的问题转化为了矩阵中的问题,但是否将过程复杂化了呢?

Binet-Cauchy 公式

为了解决这个问题,我们需要引入 Binet-Cauchy 公式:

若存在 $n\times m$ 的矩阵 $A$ 与 $m\times n$ 的矩阵 $B$,则矩阵 $AB$ 的行列式等于:从 $m$ 中任意选取 $n-1$ 个指标,并取出 $A$ 的这 $n$ 列得到 $A’$,和 $B$ 的这 $n$ 行的得到 $B’$,将它们行列式乘起来得到 $\det A’\times \det B’$,对所有共 $C_m^n$ 种选取情况求和。

数学表达:
$$
\det (AB)=\sum_{S\subseteq U,|S|=n}\det(A_S)\det(B_S)
$$
(其中 $U$ 表示集合 ${1,2,\dots,m}$,$A_S$ 表示取出 $S$ 中下标的列组成的矩阵,$B_S$ 表示取出 $S$ 中下标的行组成的矩阵)

可以发现其中几种特殊情况:

  • $n=1$:此时公式等价于计算两个 $m$ 维向量的点积
  • $n=m$:此时公式等价于表示 $\det(AB)=\det(A)\det(B)$ 的行列式可乘性质
  • $n>m$:此时公式中由于无法选出任何一组,故右边恒等于 $0$,其表达的其实是矩阵 $AB$ 不满秩

这个公式的证明过于繁琐,不予展开,但可以感性理解:$AB$ 是 $A$ 的以 $B$ 为系数的线性组合,将 $AB$ 的行列式展开后分离贡献,$\det (A_S)$ 的系数是 $\det(B_S)$

利用公式

为了解决这个问题引入这个公式,很明显是和其中的共同拥有的 “任意选取”、“线性无关” 两个因素有关。

很容易想到是想要将图的关联矩阵 $D$(去掉一行后)放入 $A$ 或 $B$ 的位置,但具体怎么放,另一个矩阵又是什么?

引理:连通图的关联矩阵中,任意一个子矩阵的行列式都为 $\pm 1$ 或 $0$

证明:

  • 若子矩阵不可逆,则行列式自然为零
  • 若子矩阵可逆,则不可能每一列都同时存在两个非零项(否则每一列都是一个 $+1$ 一个 $-1$,将所有行加起来一定是 $0$),故按只有一个非零项的列进行行列式展开,则可以归纳至低一阶的情况

有了这个引理,可以非常自然的考虑将 $A$ 设为 $D$,$B$ 设为 $D^T$,则 $A_S$ 和 $B_S$ 都是取 $D$ 的不同列向量组成的矩阵。

由于我们证明了,列线性无关的子矩阵行列式一定为 $\pm 1$,则平方后一定为 $1$。再利用上述公式,故原问题的的答案即为 $\det (AB)$ 。

至于 $AB$ 是啥?$AB=DD^T$

考虑下关联矩阵 $D$ 的定义,即可发现 $(AB)_{i,j}$:

当 $i=j$ 时:$(AB){i,i}$ 为 $D$ 第 $i$ 行与自己的点积,由于非零项都为 $\pm 1$,则 $(AB){i,i}$ 即为第 $i$ 行的非零项个数——即点 $i$ 的度数

当 $i\neq j$ 时:$(AB){i,j}$ 为 $D$ 第 $i$ 行与 $j$ 的点积,由于每一列都只有两个元素 (一个 $+1$ 一个 $-1$ ),故每个位置如果有值,则一定为 $-1$,$(AB){i,j}$ 即为它们求和——点 $i$ 与点 $j$ 之间边的数量的相反数

总结

回顾整个过程:

  • 问题一开始是 “有多少种选取 $n-1$ 条边的方式,使选出的边构成树

  • 然后引入图的关联矩阵,证明了其秩为 $n-1$,同时也发现问题等价于 “有多少种在关联矩阵中选取 $n-1$ 列的方式,使选出的列线性无关”(同时发现删去关联矩阵任意一行对答案无影响)

  • 针对 “任意选取” 和 “线性无关” 两个特点,引入了同样拥有这两个特点的 Binet-Cauchy 公式
    • 利用 Binet-Cauchy 任意选取的特点,和 “线性无关 $\iff$ 行列式非零” 的性质,希望将关联矩阵放入公式
  • 为了将关联矩阵放入公式,证明了关联矩阵中任意一个子矩阵行列式为 $\pm 1$ 或 $0$
  • 巧妙地将 $A$ 设为 $D$,$B$ 设为 $D^T$,则得到的结果 $\det(AB)$
    • 等价于:任取 $D$ 的 $n-1$ 列求出行列式,平方后求和。
    • 等价于:任取 $D$ 的 $n-1$ 列,行列式非零的方案数
  • 考虑 $AB=DD^T$ 的现实意义,得到开头提到的 Matrix Tree 定理

有向生成树的扩展

刚才讨论的都是无向生成树,可以考虑到有向生成树的情况:
– 由于点可以重新标号,我们只考虑以 $1$ 号点为根的情况
– 由于内向生成树可以将边取反后求外向生成树,故只考虑外向生成树的情况

考虑外向生成树关联矩阵的特点:除了根以外每一行都只有一个 $-1$(树上只有一个父亲)

而若生成树不是外向生成树,则一定存在一个点 $x$,关联矩阵中 $x$ 对应的那一行没有 $-1$

所以可以考虑将原来每条边 “一个 $+1$ 一个 $-1$” 中的 $+1$ 置为零,则在计算时:
– 如果这棵生成树不是外向生成树,则一定存在一行全为零,其行列式也为零
– 如果这棵树是外向生成树,由于每一行有一个 $-1$,故其行列式为 $(-1)^{n-1}$ 也只可能为 $\pm 1$

分类: 文章

[该用户已被删除]

不膜人不J人,共创和谐社会

1 条评论

boshi · 2021年2月2日 5:16 下午

“图中生成树的数量等于 V−E 的任一余子式” 这一句似乎与后文 “E 为对称阵,对角线为零且 Ei,j 为点 i 与点 j 之间边的数量的相反数” 矛盾。

另外真的任意余子式都可以吗,不一定非得是主子式吗?(虽然我也没细想,但感觉有点毛病)

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注