Theorem - Anzahl der Spaziergänge zwischen zwei Knoten durch Matrizenmultiplikation

• Involvierte Definitionen:
  • Spaziergang
  • Knoten
  • Matrizenmultiplikation
  • Adjazenzmatrix
• Veranstaltung: AlMa
• Referenz: @herzogWiSe22

⠀

Theorem: Anzahl der Spaziergänge zwischen zwei Knoten durch Matrizenmultiplikation

Sei ein Graph.
Sei die Adjazenzmatrix von .

Dann gilt:
Von nach gibt es genau Spaziergänge der Länge .

(Wobei den Eintrag an der Stelle der Matrix bezeichne.)