查看“︁矩阵树定理”︁的源代码

{{Rough translation|time=2021-04-07T02:38:54+00:00}}
在[[图论]]中，'''矩阵树定理'''（matrix tree theorem）或'''基尔霍夫定理'''（Kirchhoff theorem）是指[[图 (数学)|图]]的[[生成树]]数量等于[[调和矩阵]]的[[行列式|余子式]]（所以可以在[[时间复杂度|多项式时间]]内计算）。

若 ''G'' 有 ''n'' 个[[顶点 (图论)|顶点]]，''λ''<sub>1</sub>,&nbsp;''λ''<sub>2</sub>,&nbsp;...,&nbsp;''λ<sub>n</sub>''<sub>-1</sub> 是[[拉普拉斯矩阵]]的非零[[特征值和特征向量|特征值]]，则

: <math>t(G)=\frac{1}{n} \lambda_1\lambda_2\cdots\lambda_{n-1}.</math>

这个定理以[[古斯塔夫·基爾霍夫]]名字命名。 这也是凯莱公式的推广（若图是[[完全圖|完全图]]）。

== 举例 ==
[[File:Graph_with_all_its_spanning_trees.svg|缩略图|L是这个钻石图的[[拉氏矩阵]]]]

对于右图的例子，首先求出调和矩阵 <math>Q</math>: 

: <math>Q = \left[\begin{array}{rrrr}
2 & -1 & -1 & 0 \\
-1 & 3 & -1 & -1 \\
-1 & -1 & 3 & -1 \\
0 & -1 & -1 & 2
\end{array}\right].</math>

随后求出余子式，也即删除任何一个行和一个列，例如第一行和第一列：

: <math>Q^\ast =
\left[\begin{array}{rrr}
3 & -1 & -1 \\
-1 & 3 & -1 \\
-1 & -1 & 2
\end{array}\right].</math>

则

<math>\det(Q^*) = 8 = t(G)</math>.

=== [[凯莱公式]] ===
完全图 ''K<sub>n</sub>'' 的调和矩阵是

: <math>
\begin{bmatrix}
 n-1 & -1   & \cdots & -1   \\
 -1 & n-1   & \cdots & -1   \\
 \vdots & \vdots& \ddots & \vdots \\
 -1 & -1   & \cdots & n-1   \\
\end{bmatrix}.
</math>

任何[[餘因子矩陣|餘因子]]的行列式是 ''n<sup>n-</sup>''<sup>2</sup> 。再说L的所有特征值是n，而且L只有n-1个[[特征向量]]。所以生成树的总数又是 ''n<sup>n-</sup>''<sup>2</sup> 。

== 证明大纲 ==
[[拉普拉斯矩阵|拉氏矩阵]]有这个属性：任何行或列的元素总和等于0。所以，无论删除什么行或列，<math>\det(L^*)</math>都是不变的。或者说L的任何[[餘因子矩陣|餘因子]]有同样的行列式。

若<math>K</math>是[[接续矩阵]]，则拉普拉斯矩阵 <math>L = KK^T</math>。在矩阵<math>K</math>中，删除任何一个行或列得到矩阵<math>F</math>，那么<math>M_{11} = FF^T</math>，其中 <math>M_{11}</math> 表示 <math>L</math> 删除第一行第一列后得到的余因子矩阵。

使用[[柯西–比内公式|柯西-比内公式]]<ref>{{Cite web|title=Graphs, Matrices, Isomorphism|url=http://math.fau.edu/locke/Graphmat.htm|accessdate=2020-02-14|work=math.fau.edu|archive-date=2009-03-04|archive-url=https://web.archive.org/web/20090304210807/http://math.fau.edu/locke/Graphmat.htm|dead-url=no}}</ref>

: <math>\det\left(M_{11}\right) = \sum_S \det\left(F_S\right)\det\left(F^T_S\right) = \sum_S \det\left(F_S\right)^2</math>

可以表示这个行列式给予生成树的数量。

== 参见 ==

* [[普吕弗序列]]
* [[最小生成树]]

== 阅读 ==

* {{Citation|last=Harris|first=John M.|last2=Hirst|first2=Jeffry L.|last3=Mossinghoff|first3=Michael J.|edition=2nd|publisher=Springer|series=[[Undergraduate Texts in Mathematics]]|title=Combinatorics and Graph Theory|year=2008}}
* {{Citation|last=Maurer|first=Stephen B.|number=1|journal=SIAM Journal on Applied Mathematics|mr=0392635|pages=143–148|title=Matrix generalizations of some theorems on trees, cycles and cocycles in graphs|volume=30|year=1976|doi=10.1137/0130017}}.
* {{Citation|last=Tutte|first=W. T.|isbn=978-0-521-79489-3|page=138|publisher=Cambridge University Press|title=Graph Theory|year=2001}}.
* {{Citation|title=Matrix Tree Theorems|journal=Journal of Combinatorial Theory, Series A|volume=24|number=3|pages=377–381|year=1978|issn=0097-3165|last=Chaiken, S.|last2=Kleitman, D.|doi=10.1016/0097-3165(78)90067-5}}

== 参考文献 ==
[[Category:代数图论]]