Kirchhoff的生成树算法

Question

最近我已经研究过 kirchhoff的生成树算法以计算图形的生成树数，其中有以下步骤：

1. 构建邻接矩阵

2. 用相应节点的度替换对角线条目

3. 替换所有其他排除在内的所有其他那些 对角线由 $ - 1 $

然后找到一个元素的未成年元素以获得答案。

这些所有步骤对我来说都是魔法。任何人都可以解释Kirchhoff如何派生它来获得跨越树的数量，我想知道该算法如何工作的逻辑，但我在YouTube中可以找到的只是上述步骤。

Answer 1

看起来像魔法，因为 kirchhoff的矩阵树定理是非虚幻的。 它依赖于在步骤1-3中构造的矩阵的若干代数属性，该属性被称为拉普拉斯矩阵图。 让 $ a $ 是邻接矩阵，让 $ d $ 是具有程度的对角矩阵对角线上的节点。步骤1-3构建矩阵 $ l= d-a $ ：这是图表的拉普拉斯矩阵。

所以问题变成了，为什么Laplacian矩阵的次要应该等于图形的生成树的数量？

要回答这个问题，我们需要使用 $ l $ 的其他属性。一个属性是我们也可以编写 $ l $ 作为 $ b \ cdot b ^ \ top $ 在哪里 $ b $ 是图形，即每个节点的一行的矩阵 $ u $ 和一个列每边 $ e $ ，其中条目 $ b_ {ue}= 1 $ 如果 $ e={u， v \} $ 使用 $ u ， $ b_ {ue}= - 1 $ 如果 $ e={u，v \} $ 带 $ v ，和 $ b_ {ue}= 0 $ 如果 $ e $ 不包含 $ U $ 。 例如，对于三角形图，拉普拉斯矩阵是 $$ l=left [\ begin {array} {ccc} 2＆-1＆-1 \\ -1＆2＆-1 \\ -1＆-1和2 \结束{array} \右] $$ 并且发生率矩阵是 $$ b=left [\ begin {array} {ccc} 1＆1＆0 \\ -1＆0＆0＆1 \\ 0＆0＆1 \\ 0＆-1＆-1 \ END {阵列} \右]。 $$ 请注意，两个不同行 $ b $ 的内部产品是 $ - 1 $ 如果相应的节点邻近，如果不是。一行 $ b $ 自身的内部产品等于相应节点的程度。 （只需使用 $ b $ 。）这就是为什么 $ l= b \ cdot b ^ \ top $ < / span>。

假设图形已连接， $ b $ 正好 $ n-1 $ 其中 $ n $ 是图表的节点数。它不是 $ n $ 因为如果你总和，你得到一个零矢量。它是 $ n-1 $ ，因为 $ b $ 的独立列数是 $ N-1 $ ：如果使用与图形的任何生成树的任何生成树的边缘对应的任何列的一组，则这些列将是独立的;具有依赖列一组列的唯一方法是选择的边缘包含一个周期。

如果我们删除行和相应的 $ l $ ，我们获取矩阵 $ m $ 。如果我们删除相应的 $ b $ ，我们获取矩阵 $ c $ 。现在 $ m= c \ cdot c ^ \ top $ 出于同样的原因 $ l= b \ cdot b ^ \ Top $ 。我们对 $ \ det（m）=det（cc ^ \ top）$ 。在上面三角形图的示例中， $$ m=left [\ begin {array} {cc} 2＆-1 \\ -1＆2 \ end {array} \ revally] $$ 和 $$ c=left [\ begin {array} {ccc} 1＆1＆0 \\ -1＆0＆0 \ end {array} \ revally]。 $$

最后一步是调用另一个代数事实， cauchy-binet公式。这表明，对于任何矩阵 $ c $ ，
$$ \ det（cc ^ \ top）=det（c_ {k_1}）\ det（c_ {k_1} ^ \ top）+ \ ldots + \ det（c_ {k_q }）\ det（c_ {k_q} ^ \ top）$$ 其中每个 $ c_ {k_i} $ 表示 $（n-1）\ times（n-1）$ $ c $ ，并且总和在所有此类子群体上运行。因此， $$ \ det（c c ^ \ top）=det（c_ {k_1}）^ 2 + ldots + \ det（c_ {k_q}）^ 2。 $$

但是，<跨度类

=“数学容器”> $ \ det（c_ {k_i}）=pm 1 $ 如果对应于 $ c_ {k_i} $ 包括生成树，而<跨度类=“math-container”> $ \ det（c_ {k_i}）= 0 $ 否则（因为那么该组包含一个周期，相应的列不是独立的）。因此，总和的值正好是跨越树的数量。