矩阵树定理

概述

矩阵树定理又称 Kirchhoff 定理，把图的生成树个数写成基尔霍夫矩阵任一 n-1 阶主子式的行列式，其中基尔霍夫矩阵等于度数矩阵减邻接矩阵，主子式即划去任一行及对应列后剩下部分的行列式。对带权图，行列式给出的是所有生成树边权之积的和，是无权情形的自然推广。对有向图，按入度或出度构造基尔霍夫矩阵，就能分别对根向树形图与叶向树形图计数。文末附一道模板例题。

参考资料

• 矩阵树定理 - OI Wiki

简介

矩阵树定理（Kirchhoff 定理）把图的生成树个数表示为其基尔霍夫矩阵（度数矩阵减邻接矩阵）任一 $n-1$ 阶主子式的行列式。对带权图，行列式给出所有生成树「边权之积」的和；对有向图，按入度或出度构造可计数根向 / 叶向树形图。

例题

洛谷 P6178 【模板】Matrix-Tree 定理

给定一张带边权的无向图，求其所有生成树的边权乘积之和，对 $10^9+7$ 取模。