Satz von Kirchhoff-Trent

Der Satz von Kirchhoff-Trent, auch Matrix-Gerüst-Satz genannt, dient zur Berechnung der Anzahl der Gerüste in einem Graphen.

Graph mit elf Gerüsten

Aussage

Die Determinante der Matrix A_i ist gleich der Anzahl der Gerüste des Graphen. Die Matrix A_i entsteht aus der Admittanzmatrix des Graphen, aus der die i-te Zeile und die i-te Spalte gestrichen werden. Die Admittanzmatrix ist die Differenz zwischen der Valenzmatrix und der Adjazenzmatrix des Graphen.

Beispiel

Gegeben sei der Graph auf der Abbildung rechts. Die Adjazenzmatrix ist $B = \begin{pmatrix} 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \end{pmatrix}$.

In der ersten Zeile steht in der zweiten und fünften Spalte eine 1, da der Knoten 1 mit den Knoten 2 und 5 adjazent, also verbunden ist.

Die Valenzmatrix gibt die Anzahl der Nachbarknoten eines Knotens an. Daher sieht die Valenzmatrix folgendermaßen aus. $V = \begin{pmatrix} 2 & 0 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 & 0 \\ 0 & 0 & 4 & 0 & 0 \\ 0 & 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 0 & 2 \end{pmatrix}$

Da Knoten 2 mit drei anderen Knoten verbunden ist, steht in der zweiten Zeile in der zweiten Spalte der Matrix eine 3.

Berechnung der Admittanzmatrix: $V - B = A = \begin{pmatrix} 2 & -1 & 0 & 0 & -1 \\ -1 & 3 & -1 & -1 & 0 \\ 0 & -1 & 3 & -1 & -1 \\ 0 & -1 & -1 & 2 & 0 \\ -1 & 0 & -1 & 0 & 2 \end{pmatrix}$

Streicht man die dritte Zeile und Spalte erhält man die Matrix $A_3 = \begin{pmatrix} 2 & -1 & 0 & -1 \\ -1 & 3 & -1 & 0 \\ 0 & -1 & 2 & 0 \\ -1 & 0 & 0 & 2 \end{pmatrix}$. Auch durch Streichen anderer Zeilen und Spalten erhält man die korrekte Lösung.

Abschließend muss die Determinante der Matrix A₃ berechnet werden. Als Lösung erhält man 11.