标签：#代數圖論

矩阵树定理

在圖論中，矩陣樹定理（matrix tree theorem）或基爾霍夫定理（Kirchhoff theorem）是指圖的生成樹數量等於拉普拉斯矩陣的代數餘子式（所以可以在多項式時間內計算）。 若 G 有 n 個頂點，\lambda_1, \lambda_2, \dots, \lambda_{n-1} 是拉普拉斯矩陣的非零特徵值，則 : t(G)=\frac{1}{n} \lambda_1\lambda_2\cdots\lambda_{…