Kirchoff matrix

Kirchoff matrix --- матрица Кирхгофа.

Let us consider the general problem of counting the number of spanning trees for an arbitrary multi-graph [math]\displaystyle{ G }[/math]. This requires that we first concen\-trate on digraphs and counting the number of spanning out-trees rooted at a particular vertex. We introduce the so-called Kirchoff or in-degree matrix [math]\displaystyle{ K(G) }[/math]. The elements of [math]\displaystyle{ K }[/math] are defined as follows:

[math]\displaystyle{ K(i,j) = \left\{ \begin{array}{ll} d_{-}(v_{i}), & i = j, \\ -k, & i \neq j \end{array}\right., }[/math]

where [math]\displaystyle{ k }[/math] is the number of edges from [math]\displaystyle{ i }[/math] to [math]\displaystyle{ j }[/math]. Thus, the number of spanning out-trees rooted at [math]\displaystyle{ r }[/math] in a finite digraph [math]\displaystyle{ G }[/math] is equal to [math]\displaystyle{ \det(K_{r}(G) }[/math].