Matrix-Gerüst-Satz

Es sei G=(V,E) ein Graph mit und Durch D=(d_ij) mit

wird eine Matrix vom Typ (n,n) definiert, die auch Valenzmatrix genannt wird. Die Differenz von Valenzmatrix und Adjazenzmatrix ist die Admittanzmatrix L von G:

Aus L erhält man durch Streichen der i-ten Zeile und der i-ten Spalte die Matrix Die Determinante von L_i ist gleich der Anzahl der Gerüste im Graphen

Beispiel

Die Adjazenzmatrix, die Valenzmatrix und die Admittanzmatrix zum Graphen in der Abbildung im Abschnitt Gerüste lauten:

Wegen detL₃=5 hat der Graph genau 5 Gerüste.