矩阵树定理(结论版)

技术文章 1年前 (2020) 完美者
1,569 0

标签:求值   class   分类   inline   str   无向图   要求   有向图   roo   

简介

矩阵树定理用于生成树计数。

高斯消元解行列式

行列式就是一个\(n\times n\)的矩阵。对行列式可以求值。

具体怎么做,就是行列式搞一次高斯消元,然后对角线乘起来就是行列式的值。

矩阵树定理

首先要求出“基尔霍夫矩阵”,这需要两个矩阵\(D\)\(A\),然后\(D-A\)就是它了。

接着把这个矩阵(这是行列式)求值,要丢掉一行一列。

这两个矩阵是什么,要丢掉哪一行/列,看要求什么:

无向图生成树:\(D\)为度数矩阵(存在对角线位置),\(A\)为邻接矩阵,一般丢最后一行一列(随便丢哪一行哪一列都行)。

有向图内向生成树:\(D\)出度矩阵,\(A\)为邻接矩阵,丢第\(root\)行第\(root\)列。

有向图外向生成树:\(D\)入度矩阵,\(A\)为邻接矩阵,丢第\(root\)行第\(root\)列。

带边权:\(D\)为出/入/出入边和(可以理解为带权的出入度,这里类比一下,懒得分类讨论了),\(A\)位带权的邻接矩阵,丢的行列同上。

矩阵树定理(结论版)

标签:求值   class   分类   inline   str   无向图   要求   有向图   roo   

原文地址:https://www.cnblogs.com/SKTT1Faker/p/13618234.html

版权声明:完美者 发表于 2020-09-17 14:10:20。
转载请注明:矩阵树定理(结论版) | 完美导航

暂无评论

暂无评论...