老久没更了, 冬令营也延期了 (延期后岂不是志愿者得上学了?)
最近把之前欠了好久的债, 诸如 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\sube 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\ne 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\)
来源: https://www.cnblogs.com/penth/p/12511855.html