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 ${}\ell$ gleich dem Eintrag an der Stelle ${}(u,v)$ zur Matrixpotenz ${}A^{\ell }$ .