Adjazenzmatrix/Potenzen/Interpretation/Fakt

Satz über Potenzen der Adjazenzmatrix

Es sei $G = (V, E)$ ein Graph mit zugehöriger Adjazenzmatrix $A$ .

Dann ist die Anzahl der Wege von $u$ nach $v$ der Länge $ℓ$ gleich dem Eintrag an der Stelle $(u, v)$ zur Matrixpotenz $A^{ℓ}$ .