Kreis/Adjazenzmatrix/Potenzen/Beispiel

Wir betrachten den Rundgang zur Vertexmenge ${}a,b,c,d,e$ in dieser Reihenfolge. Die Adjazenzmatrix ist

${}A={\begin{pmatrix}0&1&0&0&1\\1&0&1&0&0\\0&1&0&1&0\\0&0&1&0&1\\1&0&0&1&0\end{pmatrix}}\,.$

Die Wege der Länge ${}2$ kann man direkt so bestimmen: Es gibt zwei Wege von jedem Punkt zu sich selbst, nämlich zu den beiden Nachbarn und dann zurück. Zum Nachbarn gibt es keinen Weg der Länge ${}2$, zum übernächsten Punkt gibt es jeweils einen Weg der Länge ${}2$. Entsprechend ist

${}{\begin{aligned}A^{2}&={\begin{pmatrix}0&1&0&0&1\\1&0&1&0&0\\0&1&0&1&0\\0&0&1&0&1\\1&0&0&1&0\end{pmatrix}}{\begin{pmatrix}0&1&0&0&1\\1&0&1&0&0\\0&1&0&1&0\\0&0&1&0&1\\1&0&0&1&0\end{pmatrix}}\\&={\begin{pmatrix}2&0&1&1&0\\0&2&0&1&1\\1&0&2&0&1\\1&1&0&2&0\\0&1&1&0&2\end{pmatrix}}.\end{aligned}}$

Ab der Länge ${}3$ muss man bei der kombinatorischen Abzählung berücksichtigen, dass Wege mit unterschiedlichem Umlaufsinn sich überlagern und das gleiche Ergebnis haben können. Mit der Matrixregel aus Fakt muss man einfach nur multiplizieren, es ist

${}{\begin{aligned}A^{3}&={\begin{pmatrix}0&1&0&0&1\\1&0&1&0&0\\0&1&0&1&0\\0&0&1&0&1\\1&0&0&1&0\end{pmatrix}}{\begin{pmatrix}2&0&1&1&0\\0&2&0&1&1\\1&0&2&0&1\\1&1&0&2&0\\0&1&1&0&2\end{pmatrix}}\\&={\begin{pmatrix}0&3&1&1&3\\3&0&3&1&1\\1&3&0&3&1\\1&1&3&0&3\\3&1&1&3&0\end{pmatrix}}.\end{aligned}}$