Potenzen berechnen von Adjazenzmatrizen

Question

Was bringt es die Potenz einer Adjazenzmatrizen zu berechnen? Ich habe in einer Aufgabe eine Adjazenzmatrizen bis zur vierten Potenz ausgerechnet. A, A^2, A^3, A^4.

Die Matrix von A^4 ist leer. Was hat das nun zu bedeuten? Was genau bringt es das zu berechnen?

Answer 1

Für die n×n-Matrix A := (a_ij)_1≤i,j≤n mit  A² = B = (b_ij)_1≤i,j≤n gilt

        b_ij = ∑_k=1..n a_ika_kj.

Wenn a_ik aussagt, wie man von Knoten i zu Knoten k kommt, und a_kj aussagt, wie man von Knoten k zu Knoten j kommt, dann sagt a_ika_kj aus, wie man von Knoten i zu Knoten j kommt.

Für b_ij wird über alle k summiert. b_ij sagt aus, wie man auf Pfaden der Länge 2 von Knoten i zu Knoten j kommt. Bei ungewichteten Graphen ist das die Anzahl der Pfade der Länge zwei von Knoten i zu Knoten j.

Die Matrix von A⁴ ist leer.

Es gibt keine Kantenzüge der Länge 4. Insbesondere gibt es keine Kreise.