矩阵树定理及其应用(未完成)

这个东西首次出现在周冬的国家集训队论文里面,解决的问题叫做生成树计数问题。
顾名思义,就是让你求一张无向图中生成树的个数。
首先我们要知道三个概念。

  1. 邻接矩阵A
    这个东西不用我说了吧,就是对于每一条边$Edge_{ij}$,矩阵的$i$行$j$列和$j$行$i$列设为1,其他设为0。
  2. 度数矩阵D
    啥意思呢,就是将每一个点的度数,其中对于每一个不相等的$i,j$有$D[i][j] = 0$
  3. 基尔霍夫矩阵C
    $C = D - A$

而Matrix-Tree定理就是说这个无向图的生成树个数就等于基尔霍夫矩阵的任意一个$N - 1$阶主子式的行列式的绝对值。

本文标题:矩阵树定理及其应用(未完成)

文章作者:Sue Shallow

发布时间:2019年04月04日 - 19:25:59

最后更新:2019年11月11日 - 19:55:39

原始链接:http://Yeasion.github.io/2019/04/04/矩阵树定理及其应用/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。