Kreis/Adjazenzmatrix/Potenzen/Beispiel

Aus Wikiversity
Zur Navigation springen Zur Suche springen

Wir betrachten den Rundgang zur Vertexmenge in dieser Reihenfolge. Die Adjazenzmatrix ist

Die Wege der Länge 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 , zum übernächsten Punkt gibt es jeweils einen Weg der Länge . Entsprechend ist

Ab der Länge 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