Satz von Kirchhoff-Trent

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 Ai ist gleich der Anzahl der Gerüste des Graphen. Die Matrix Ai 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 A3 berechnet werden. Als Lösung erhält man 11.


Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Liste mathematischer Sätze — Inhaltsverzeichnis A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A Satz von Abel Ruffini: eine allgemeine Polynomgleichung vom …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”