Die Adjazenzmatrix gibt die die Anzahl an Wegen von \( u \) nach \( v \) der Länge eins an (denn ein Eintrag ist ja genau dann eins, wenn eine Kante zwischen zwei Knoten existiert). Ich bezeichne die Einträge der Adjazenzmatrix jetzt mal mit \( a_{i, j} \), wobei \( a_{i, j}=1 \Longleftrightarrow \) es existiert eine Kante zwischen den Knoten \( i \) und \( j \). Möchtest du nun die Wege der Länge 2 zwischen zwei Knoten \( i \) und \( j \) bestimmen, so überprüfst du ja für jeden Nachbarn von \( i \) ob er auch ein Nachbar von \( j \) ist. Mithilfe der Einträge der Adjazenzmatrix ausgedrückt also
\( a_{i, 1} \cdot a_{1, j}+a_{i, 2} \cdot a_{2, j}+\ldots+a_{i, n} \cdot a_{n, j}=\sum \limits_{k=1}^{n} a_{i, k} \cdot a_{k, j} \)
wobei der Graph \( n \) Knoten hat. Wenn du mit Matrixmultiplikation vertraut bist erkennst du diese in der obigen Summe wieder, wenn \(\mathbf{A}\) also die Adjazenzmatrix ist dann zählt der Eintrag \( (i, j) \) der Matrix \( \mathbf{A}^{2} \) die Anzahl der Wege der Länge 2 von \( i \) nach \( j \). Man kann dann erkennen, dass der Eintrag \( (i, j) \) der Matrix \( \mathbf{A}^{r} \) die Anzahl der Wege der Länge \( r \) von \( i \) nach \( j \) enthält. In deinem Fall musst du also \( \mathbf{A}^{4} \) berechnen und dann den Eintrag \( (1,3) \) ablesen.
