矩阵树定理 在图论中矩阵树定理matrix tree theorem或基尔霍夫定理Kirchhoff theorem是指图的生成树数量等于调和矩阵的余子式所以需要时间多项式计算 若 G 有 n 个顶点λ λ  λn 是拉普拉斯矩阵的非零特征值则 t  G    n λ  λ   λ n    displaystyle tGfrac nlambda lambda cdots lambda n 这个定理以古斯塔夫基爾霍夫名字命名 这也是凯莱公式的推广若图是完全图